找到两个多边形的公共内点

Question

假设我有重叠的多边形。两者都不一定是凸的。什么是找到它们内部而不是任何边界上的点的有效算法？

假设它们重叠，并且我们的多边形由它们在 3D 中的顶点集定义。

Answer 1

可以使用 Vatti polygon clipping algorithm 的变体。 Vatti 的算法是一种扫描线算法，基本上意味着从（比方说）从左到右扫描两个多边形的顶点，以及它们边界之间的任何交点。在穿过这些 "events" 中任何连续两个的垂直线之间，然后检查由多边形创建的 trapezoids/triangles。一旦你找到一个属于两者的梯形，你就可以输出它的质心。