多边形的交点

Question

给出了两个多边形.如何确定一个多边形是在另一个多边形的内部,外部还是相交？多边形可以是凹面或凸面.

Answer 1

您想要对凸多边形使用分离轴定理。基本上，对于每个多边形的每个面，您将每个多边形投影到该面的法线上，然后查看这些投影是否相交。

您可以执行各种技巧来减少必须执行的计算数量 - 例如，您可以在对象周围绘制一个矩形，并假设如果两个对象的矩形不相交，则它们本身也不相交。（这更容易，因为检查这些框的交集的计算成本较低，并且通常非常直观。）

凹多边形更难。我认为您可以将多边形分解为一组凸多边形，并尝试检查每个交集的组合，但我不认为自己在这方面有足够的技能来尝试它。