多边形图像
所有的多边形都很简单，没有洞。
板多边形（P0到P7）
红色多边形（R0到R6）
绿色多边形（g0 g1 p2 g3）
黄色多边形（y0到y3）
我想得到新的四个多边形标记为1到4，多边形1的坐标是（J7 J10 R5 R4）。
当我使用多边形裁剪算法时，我可以很容易地得到结果，板差（红并绿并黄）。但是当我有超过10000个多边形时，我需要很长时间才能得到结果。我的多边形很简单，结果多边形也很简单，结果多边形中也没有洞。
你知道我可以很容易地用眼睛找到图像中的四个多边形，但是如何用算法找到它们。
谢谢。
最佳答案
如果计算的黑色多边形的所有顶点在顶点处相交的边不超过2条，则可能有比更通用的工具更快的方法。
由于多边形的数量约为10000，首先尝试计算所有多边形对的交点，希望交点的数量足够小（比如1000万或更少）。然后，对每个交点进行测试，以查看它是否包含在另一个多边形的内部（如果有多个多边形共同重叠）。测试一个点是否包含在多边形的内部可以很快完成，你可以在线阅读。然后，所有不包含在另一个多边形中的交点，其中还包含不包含在多边形内部的所有原始多边形顶点，这些是要计算的“黑色”多边形的顶点。这些点应与二级结构一起存储，对于每个多边形边，二级结构按排序顺序存储沿该边存储的所有交点同样，对于每个存储的顶点和交点，您应该存储在该点相交的边，以及该交点在上一个结构中的位置。因此，然后选择任何尚未在黑色多边形中使用的存储交点，并选择一条定义交点的边。然后沿边移动到相邻的交点，该交点的特性是两个交点之间的边的一部分不通过多边形内部。然后继续沿着定义相邻交点的另一条边进行类似的移动。继续，直到到达开始的顶点；这将定义一个黑色多边形。然后，可以选择一个新的未使用的存储交点并重复。因为你的多边形没有洞，这将找到所有的黑色多边形。
关于algorithm - 如何有效地从现有多边形中提取新多边形，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17639979/