computational-geometry - 找到两个多边形的共同内点

Question

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

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

Answer 1

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