0

我想通过给出每个顶点的点数组来确定一个多边形是否在另一个多边形内。有什么简单的方法可以做到这一点吗？ 编辑：检查内部的最小点是否大于外部以及外部的最大点是否小于内部是不够的。这不是充分条件。证明： 在此处输入图像描述

4

5 回答 5

1

一旦您检查了多边形 A 的最小边界框位于多边形 BI 的边界框内，您就认为您将不得不检查 A 的每条边是否与 B 的所有边不相交。

我认为这是一种简单的方法，但我怀疑您确实想要一种更有效的聪明方法。

于 2012-08-23T09:33:38.433 回答
0

我使用 Java2D 做了一些非常相似的事情，尤其是 Area 类。如果您想复制该功能，该类的代码是免费提供的。一个更简单的选择可能是查看这个库：http ://www.cs.man.ac.uk/~toby/alan/software/它应该允许你做你想做的事或给你起点。

于 2012-08-23T09:45:27.603 回答
0

  1. 多边形 1 的某个点位于多边形 2 内

    你可以在这里使用光线投射

  2. 多边形之间没有边-边相交

    对于大量边空间分区树可能会提高速度，对于少量边 N*M 枚举是可以的

于 2012-08-23T15:15:09.160 回答
0

首先，使用轴对齐的边界框来查看它们是否彼此靠近。（基本上，在每个框周围绘制一个 XY 对齐的框，看看它们是否相交。这比多边形的情况要容易得多，并且通常可以节省大量时间。）

如果方框相交，您现在应该执行详细的相交测试。您需要绘制一条垂直于“外部”多边形的每一侧的线，并将它们的所有点都投影到线上。然后，检查内部多边形的结果点是否在从外部多边形投影的点之间。

我知道这个例子一开始很难形象化——我向对此领域感兴趣的人推荐这个关于碰撞检测的教程：

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

但是，如上所述，您的任务略有不同，因为您将投影到每一侧的垂直线上，并且您需要所有这些都包含该段。如果你想做很多这样的事情，我还建议你对投影和线性代数的概念有所了解。

于 2012-08-24T05:38:35.947 回答
-1

您的问题尚未确定-仅给出每个顶点的坐标不足以指定多边形。示例：画一个正方形并填充对角线。您的五个顶点是正方形的角和对角线交点处的点。从这些顶点可以构造四个不同的多边形：每一个都是使用原始图形的边构造的，同时从正方形中删除一条边并限制对角线（我希望这足够清楚）。

编辑：显然还不够清楚。令 a1、a2、a3、a4 为对应于正方形四个点的顶点（例如，从左上角顺时针方向），令 a5 为对应于正方形对角线交点的顶点。仅出于示例的目的，这里有两个适合上述顶点的多边形：1. (a1,a2),(a2,a5),(a5,a3),(a3,a4),(a4,a1)。这应该看起来像一个面向右侧的吃豆人。2. (a1,a2),(a2,a3),(a3,a4),(a4,a5),(a5,a1)。这应该看起来像一个面向左的吃豆人。

于 2012-08-23T10:22:27.843 回答