找到相交线之间的所有四边形？
Find all quadrilaterals between intersecting lines?
如何找到几条相交线之间的所有四边形？唯一的条件是四边形的每一边都是一条线。
我找到了 this 理论解释，但没有代码。
到目前为止，我还处于起步阶段。我有我的线（每条线有两个 x，y 点）并找到它们的所有交点（x，y 点）。如果您对该脚本感兴趣，请参阅 here。
到目前为止，我的脚本基于 php，但我非常感谢您的建议，也使用不同的语言。
例子
这里是一组台词。
line 715.341 0 757.297 600,
line 0 249.169 800 179.178,
line 0 256.196 800 186.205,
line 0 284.225 800 200.142,
line 396.716 0 481.041 600,
line 0 311.374 800 227.29,
line 0 355.76 800 229.053,
line 0 521.525 800 437.442,
line 696.134 0 611.809 600
在我的示例中，交点如下所示。每个点都有一个数字、x 和 y 坐标以及两条线 id。
Point 1. 728.309, 185.45, 0, 1
Point 2. 728.797, 192.434, 0, 2
Point 3. 729.852, 207.515, 0, 3
Point 4. 731.736, 234.465, 0, 5
Point 5. 732.11, 239.806, 0, 6
Point 6. 746.324, 443.084, 0, 7
Point 7. 426.491, 211.856, 1, 4
Point 8. 669.346, 190.609, 1, 8
Point 9. 427.466, 218.798, 2, 4
Point 10. 668.346, 197.723, 2, 8
Point 11. 430.305, 238.998, 3, 4
Point 12. 666.027, 214.223, 3, 8
Point 13. 434.065, 265.752, 4, 5
Point 14. 436.988, 286.548, 4, 6
Point 15. 463.17, 472.844, 4, 7
Point 16. 662.154, 241.778, 5, 8
Point 17. 660.845, 251.093, 6, 8
Point 18. 632.176, 455.081, 7, 8
convert -size 800x600 xc:skyblue \
-fill red -stroke red -strokewidth 2 \
-draw "line 715.341 0 757.297 600, line 0 249.169 800 179.178, line 0 256.196 800 186.205, line 0 284.225 800 200.142, line 396.716 0 481.041 600, line 0 311.374 800 227.29, line 0 355.76 800 229.053, line 0 521.525 800 437.442, line 696.134 0 611.809 600" \
-font Courier -pointsize 14 -draw "fill none stroke blue circle 728.309,185.45 726.309,183.45 circle 728.797,192.434 726.797,190.434 circle 729.852,207.515 727.852,205.515 circle 731.736,234.465 729.736,232.465 circle 732.11,239.806 730.11,237.806 circle 746.324,443.084 744.324,441.084 circle 426.491,211.856 424.491,209.856 circle 669.346,190.609 667.346,188.609 circle 427.466,218.798 425.466,216.798 circle 668.346,197.723 666.346,195.723 circle 430.305,238.998 428.305,236.998 circle 666.027,214.223 664.027,212.223 circle 434.065,265.752 432.065,263.752 circle 436.988,286.548 434.988,284.548 circle 463.17,472.844 461.17,470.844 circle 662.154,241.778 660.154,239.778 circle 660.845,251.093 658.845,249.093 circle 632.176,455.081 630.176,453.081" \
-draw "fill blue stroke blue text 738.309,190.45 '1' text 738.797,197.434 '2' text 739.852,212.515 '3' text 741.736,239.465 '4' text 742.11,244.806 '5' text 756.324,448.084 '6' text 436.491,216.856 '7' text 679.346,195.609 '8' text 437.466,223.798 '9' text 678.346,202.723 '10' text 440.305,243.998 '11' text 676.027,219.223 '12' text 444.065,270.752 '13' text 446.988,291.548 '14' text 473.17,477.844 '15' text 672.154,246.778 '16' text 670.845,256.093 '17' text 642.176,460.081 '18'" \
lines-intersection.jpg
所以现在最大的问题是，我如何使用这些信息来找到每条边都是一条线的点之间的所有四边形...
我要找的四边形之一是点 13、4、6 和 15:
我建议这样分解问题：
- 求出习题集中的基本四边形
- 找出这些基本四边形的公共边
- 生成允许组合的列表或矩阵以显示所有可能的四边形
求基本四边形：
我建议首先使用 Voronoi/Delaunay 过程来查找 Voronoi 图。
如果您不熟悉（或者遇到这个问题的其他人不熟悉），您得到的是来自一组线的一组图形点（和连接边）。 Voronoi 图定义了一组与最近的当前点等距的点——基本上，您将找到封闭区域的中心，再加上一些额外的东西。 （更详细的解释在 Wikipedia）。
您想要的封闭区域（矩形、三角形等）由 Voronoi 点的子集标识，您可以执行其他测试以编程方式找到该子集。从您的示例中，您可能想要也可能不想丢弃生成的三角形；如果你这样做，那么一旦你确定了封闭区域，你就可以计算周围的 edges/faces。
我不是 PHP 专家，但我的 Google-fu 在 GitHub 显示了 PHP 实现。我自己的研究工作是图结构和机器人，这种用法经常出现。
Voronoi 图的一种解释是，新点基于 "nearest neighbors"--每个点位于由原始点创建的固定或无限多边形内。
如果你正在寻找四边形，那么找到离每个 Voronoi 点最近的 4 个点。如果有一组边直接连接 4 个点 (pt1-pt2-pt3-pt4-pt1)，则您位于四边形内。如果不是，那么您在另一个形状内或在导致无穷大的外部区域之一上。
（这就是大锤方法，正如我的老航空航天讲师过去所说的那样。我敢肯定，还有更优雅的解决方案，但我没有涉及对形状进行分类。如果我发现 - 或者有人建议——更好的答案，我会更新这个。）
找出这些基本四边形的公共边
对于 "stacked" 四边形，如更新后的问题所示，您可以在基本四边形中找到公共边，然后生成组合列表。例如，如果四边形 A 与四边形 B 有公共边，那么您将生成一个更大的四边形四边形 AB。
生成允许组合的列表或矩阵 之后，您可能必须重新测试，直到用尽所有可能的组合。您必须测试的一件事是，额外的形状仍然是四边形——如果您向上添加一行，向左或向右添加一行，您将得到一个不再有效的 "L" 类型的形状。
不漂亮也不优雅，但可能有效。
好的，我找到了一个解决方案。不幸的是，我无法使用
推荐的 Voronoi 图来解决这个问题
我的想法是，利用这个事实，每个 四边形的总角必须为 360°。
基本上我是按以下方式做的：
- 创建一个包含链中 4 个交点的所有可能组合的列表。
- 然后我只是使用每一个两点在一条线上的组合。为了对此进行过滤，我使用了为每个点保存的线 ID。
- 在点之间创建向量并计算角度。每个角度必须大于0°且小于180°
- 将4个角求和，看是否为360°
结果
如果有人对代码细节感兴趣，请告诉我...
如何找到几条相交线之间的所有四边形？唯一的条件是四边形的每一边都是一条线。
我找到了 this 理论解释，但没有代码。
到目前为止，我还处于起步阶段。我有我的线（每条线有两个 x，y 点）并找到它们的所有交点（x，y 点）。如果您对该脚本感兴趣，请参阅 here。
到目前为止，我的脚本基于 php，但我非常感谢您的建议，也使用不同的语言。
例子
这里是一组台词。
line 715.341 0 757.297 600,
line 0 249.169 800 179.178,
line 0 256.196 800 186.205,
line 0 284.225 800 200.142,
line 396.716 0 481.041 600,
line 0 311.374 800 227.29,
line 0 355.76 800 229.053,
line 0 521.525 800 437.442,
line 696.134 0 611.809 600
在我的示例中，交点如下所示。每个点都有一个数字、x 和 y 坐标以及两条线 id。
Point 1. 728.309, 185.45, 0, 1
Point 2. 728.797, 192.434, 0, 2
Point 3. 729.852, 207.515, 0, 3
Point 4. 731.736, 234.465, 0, 5
Point 5. 732.11, 239.806, 0, 6
Point 6. 746.324, 443.084, 0, 7
Point 7. 426.491, 211.856, 1, 4
Point 8. 669.346, 190.609, 1, 8
Point 9. 427.466, 218.798, 2, 4
Point 10. 668.346, 197.723, 2, 8
Point 11. 430.305, 238.998, 3, 4
Point 12. 666.027, 214.223, 3, 8
Point 13. 434.065, 265.752, 4, 5
Point 14. 436.988, 286.548, 4, 6
Point 15. 463.17, 472.844, 4, 7
Point 16. 662.154, 241.778, 5, 8
Point 17. 660.845, 251.093, 6, 8
Point 18. 632.176, 455.081, 7, 8
convert -size 800x600 xc:skyblue \
-fill red -stroke red -strokewidth 2 \
-draw "line 715.341 0 757.297 600, line 0 249.169 800 179.178, line 0 256.196 800 186.205, line 0 284.225 800 200.142, line 396.716 0 481.041 600, line 0 311.374 800 227.29, line 0 355.76 800 229.053, line 0 521.525 800 437.442, line 696.134 0 611.809 600" \
-font Courier -pointsize 14 -draw "fill none stroke blue circle 728.309,185.45 726.309,183.45 circle 728.797,192.434 726.797,190.434 circle 729.852,207.515 727.852,205.515 circle 731.736,234.465 729.736,232.465 circle 732.11,239.806 730.11,237.806 circle 746.324,443.084 744.324,441.084 circle 426.491,211.856 424.491,209.856 circle 669.346,190.609 667.346,188.609 circle 427.466,218.798 425.466,216.798 circle 668.346,197.723 666.346,195.723 circle 430.305,238.998 428.305,236.998 circle 666.027,214.223 664.027,212.223 circle 434.065,265.752 432.065,263.752 circle 436.988,286.548 434.988,284.548 circle 463.17,472.844 461.17,470.844 circle 662.154,241.778 660.154,239.778 circle 660.845,251.093 658.845,249.093 circle 632.176,455.081 630.176,453.081" \
-draw "fill blue stroke blue text 738.309,190.45 '1' text 738.797,197.434 '2' text 739.852,212.515 '3' text 741.736,239.465 '4' text 742.11,244.806 '5' text 756.324,448.084 '6' text 436.491,216.856 '7' text 679.346,195.609 '8' text 437.466,223.798 '9' text 678.346,202.723 '10' text 440.305,243.998 '11' text 676.027,219.223 '12' text 444.065,270.752 '13' text 446.988,291.548 '14' text 473.17,477.844 '15' text 672.154,246.778 '16' text 670.845,256.093 '17' text 642.176,460.081 '18'" \
lines-intersection.jpg
所以现在最大的问题是，我如何使用这些信息来找到每条边都是一条线的点之间的所有四边形...
我要找的四边形之一是点 13、4、6 和 15:
我建议这样分解问题：
- 求出习题集中的基本四边形
- 找出这些基本四边形的公共边
- 生成允许组合的列表或矩阵以显示所有可能的四边形
求基本四边形： 我建议首先使用 Voronoi/Delaunay 过程来查找 Voronoi 图。
如果您不熟悉（或者遇到这个问题的其他人不熟悉），您得到的是来自一组线的一组图形点（和连接边）。 Voronoi 图定义了一组与最近的当前点等距的点——基本上，您将找到封闭区域的中心，再加上一些额外的东西。 （更详细的解释在 Wikipedia）。
您想要的封闭区域（矩形、三角形等）由 Voronoi 点的子集标识，您可以执行其他测试以编程方式找到该子集。从您的示例中，您可能想要也可能不想丢弃生成的三角形；如果你这样做，那么一旦你确定了封闭区域，你就可以计算周围的 edges/faces。
我不是 PHP 专家，但我的 Google-fu 在 GitHub 显示了 PHP 实现。我自己的研究工作是图结构和机器人，这种用法经常出现。
Voronoi 图的一种解释是，新点基于 "nearest neighbors"--每个点位于由原始点创建的固定或无限多边形内。
如果你正在寻找四边形，那么找到离每个 Voronoi 点最近的 4 个点。如果有一组边直接连接 4 个点 (pt1-pt2-pt3-pt4-pt1)，则您位于四边形内。如果不是，那么您在另一个形状内或在导致无穷大的外部区域之一上。
（这就是大锤方法，正如我的老航空航天讲师过去所说的那样。我敢肯定，还有更优雅的解决方案，但我没有涉及对形状进行分类。如果我发现 - 或者有人建议——更好的答案，我会更新这个。）
找出这些基本四边形的公共边 对于 "stacked" 四边形，如更新后的问题所示，您可以在基本四边形中找到公共边，然后生成组合列表。例如，如果四边形 A 与四边形 B 有公共边，那么您将生成一个更大的四边形四边形 AB。
生成允许组合的列表或矩阵 之后，您可能必须重新测试，直到用尽所有可能的组合。您必须测试的一件事是，额外的形状仍然是四边形——如果您向上添加一行，向左或向右添加一行，您将得到一个不再有效的 "L" 类型的形状。
不漂亮也不优雅，但可能有效。
好的，我找到了一个解决方案。不幸的是，我无法使用
我的想法是，利用这个事实，每个 四边形的总角必须为 360°。
基本上我是按以下方式做的：
- 创建一个包含链中 4 个交点的所有可能组合的列表。
- 然后我只是使用每一个两点在一条线上的组合。为了对此进行过滤，我使用了为每个点保存的线 ID。
- 在点之间创建向量并计算角度。每个角度必须大于0°且小于180°
- 将4个角求和，看是否为360°
结果
如果有人对代码细节感兴趣，请告诉我...