7

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

4

4 回答 4

3

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

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

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

于 2012-06-27T17:50:43.277 回答
2

通常，此类问题可以通过扫描线算法轻松解决。然而，使用扫描线方法的主要目的和好处是，当输入由两组相对较大的多边形组成时，它可以有效地解决问题。一旦实施扫描线解决方案，如果需要，它也可以有效地应用于一对多边形。也许你应该考虑朝那个方向前进，以防你将来需要解决一个大问题。

但是，如果您确定需要两个且仅两个多边形的解决方案，则可以通过顺序点对多边形和分段对多边形测试来解决。

于 2012-06-28T00:08:02.523 回答
0

这是一个简单的算法，可以知道给定点是在给定多边形内部还是外部：

bool isInside(point a, polygon B)
{
    double angle = 0;
    for(int i = 0; i < B.nbVertices(); i++)
    {
        angle += angle(B[i],a,B[i+1]);
    }
    return (abs(angle) > pi);
}
  • 如果 A 的线段与 B 的线段相交，则这两个多边形彼此相交。
  • 否则，如果多边形 A 的所有点都在多边形 B 内，则 A 在 B 内。
  • 否则，如果多边形 B 的所有点都在多边形 A 内，则 B 在 A 内。
  • 否则，如果多边形 A 的所有点都在多边形 B 之外，那么 A 在 B 之外。
  • 否则这两个多边形相互交叉。
于 2012-06-27T14:10:34.403 回答
0

有一种简单的方法可以检查一个点是否位于多边形中。根据这篇Wikipedia 文章，它被称为光线投射算法。

该算法的基本思想是，您从正在测试的点向某个任意方向投射光线，并计算它与多边形相交的边数。如果这个数字是偶数，则该点位于多边形之外，否则，如果它是奇数，则该点位于多边形内。

这个算法有很多问题我不会深入研究（它们在我之前链接的 Wikipedia 文章中讨论过），但它们是我称这个算法为 easyish 的原因。但是为了给您一个想法，您必须处理涉及光线与顶点相交的极端情况，光线平行运行并与边缘相交以及与靠近边缘的点相交的数值稳定性问题。

然后，您可以按照 Thomas 在他的回答中描述的方式使用此方法来测试两个多边形是否相交。这应该为您提供一个O(NM)算法，其中两个多边形分别具有N和M顶点。

于 2012-06-28T00:05:03.240 回答