如何找到几条相交线之间的所有四边形？唯一的条件是四边形的每一边都是一条线。
我找到了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:
最佳答案
我建议以这种方式分解问题:
- 找出问题集中的基本四边形
- 找到这些基本四边形之间的公共(public)边
- 生成允许组合的列表或矩阵，以显示所有可能的四边形
找到基本四边形: 我建议首先使用 Voronoi/Delaunay 过程来查找 Voronoi 图。
如果您不熟悉(或者其他不熟悉的人遇到这个问题)，您所得到的是一组线的一组图点(和连接边)。 Voronoi 图定义了一组与最近的当前点等距的点 - 基本上，您将找到封闭区域的中心，以及一些额外的内容。 (更详细的解释请参见Wikipedia)。
您想要的封闭区域(矩形、三角形等)由 Voronoi 点的子集标识，您可以执行其他测试以编程方式找到该子集。从您的示例来看，您可能想也可能不想丢弃生成的三角形；如果这样做，那么一旦确定了封闭区域，您可能就可以计算周围的边缘/面。
我不是 PHP 专家，但我的 Google-fu 在 GitHub 显示了 PHP 实现。我自己的研究工作是图结构和机器人技术，这种用法经常出现。
对 Voronoi 图的一种解释是，新点基于“最近邻居”——每个点位于由原始点创建的固定或无限多边形内。
如果您正在寻找四边形，则找到距离每个 Voronoi 点最近的 4 个点。如果有一组边直接连接这 4 个点 (pt1-pt2-pt3-pt4-pt1)，则您位于四边形内部。如果不是，那么您就位于另一个形状内，或者位于通向无穷大的外部区域之一。
(这就是大锤方法，正如我以前的航空航天教练所说的那样。我确信还有更优雅的解决方案，但对形状进行分类并不是我所涉及的内容。如果我发现——或者有人建议—— -更好的答案，我会更新。)
找到这些基本四边形之间的公共(public)边 对于“堆叠”四边形，如更新的问题所示，您可以找到基本四边形之间的公共(public)边，然后生成组合列表。例如，如果四边形 A 与四边形 B 具有公共(public)边，则将生成一个更大的四边形四边形 AB。
生成允许组合的列表或矩阵 之后，您可能需要重新测试，直到用尽所有可能的组合。您必须测试的一件事是附加形状仍然是四边形 - 如果您向上添加一行并向左或向右添加一行，您将得到一个不再有效的“L”型形状。
不漂亮或优雅，但可能有效。
关于php - 找到相交线之间的所有四边形？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32275419/