将一个多边形随机放置在另一个多边形内部

Question

我有两个由一系列二维浮点数值定义的多边形。它们不保证是凸多边形或凹多边形。它们不会相互交叉，也不能旋转。如果可能的话，我想将一个随机放置在另一个内部，基于它们的大小。主要问题在于效率。我需要在几秒钟内完成大约200次这样的操作。

我已经研究了几天，但没有取得任何实质性进展。如果您有任何线索，请告诉我。

- ZachLHelms

---

你想对这两个多边形做什么？ - Thomas

抱歉，标题中已经指定了，但是没有在正文中添加。现在已更新。 - ZachLHelms

为了提出一种高效的算法，我们可能需要更多了解您尝试解决的问题，特别是我们可以依靠的多边形的任何定义特征。 - Michael Petito

除了定义多边形的典型特征之外，实际上并没有什么特别的。至少需要3个点，不会交叉等。它们的大小和形状基本上是任意的。 - ZachLHelms

Answer 1

^{免责声明：如果您试图将多个多边形放入一个更大的多边形中，那么我认为，这个问题是NP难问题，因此不太可能开发出高效且准确的算法来解决这个问题。多边形可以在平面内连续平移和旋转，这意味着放置位置可能是无限的，这使得问题的解空间也是无限的。如果您只是想找出小多边形是否适合放在大多边形内部，我缺乏有效的答案，但由于您的要求 -“任何线索都会受到赞赏”- 这里有一个。}

---

让更大的多边形为B，较小的多边形（要插入的）为S。B共有b个点，S共有s个点。

---

下面的图片展示了一个边界框和一个最小边界矩形。我们使用它来获取“快速失败过滤器”（非常简单的想法...在下一段中定义）。下面显示的框（a）计算速度更快，而框（b）对于过滤更准确。绘制那个框可以为您的情况带来更好的回报。尽管在下面的图中它们都将椭圆框起来而不是多边形，但您已经有了想法。

^{(图片来源: http://portal.ku.edu.tr/~cbasdogan/Tutorials/imageU21.JPG)}

关键点: 如果B的任何一条线与S的任何一条线相交，或者S的所有线都在B的外部，则B不能包含S。

快速失败过滤器: 获取B和S的边界矩形。如果不能将S的边界矩形放置在B的边界矩形内，则无法将多边形S放入多边形B中。这样，如果B无法包含S，则可以更快地失败。下面的图片说明了三种情况。

^{(图片来自：http://www.cs.berkeley.edu/~ug/slide/pipeline/assignments/as4/figures/boundcull.gif)}

---

预处理：确定构成B的线的方程。将它们存储在HashMap<<Point, Point>, Line>中，以备后续步骤使用。您可以通过斜率m和截距c来唯一定义该线，而您线的端点将成为HashMap的键（<Point, Point>）。

---

算法：

对于通过上述过滤器的每个S：

1. 读取S的点并确定形成S的线
2. 对于S的每条线，查看它是否与B的任何一条线相交（它们已经存储在HashMap中）
3. 如果没有交集，则S在B内部，您只需绘制线而不必担心交集。

在最坏的情况下，该算法的复杂度为每个多边形绘制的O(bs)。

---

^†_{这一步是采用暴力方法来保证算法易于理解。否则，这里可能存在一种关键的优化，可以更快地得出结果。您可以过滤B的行。如果B的行的端点位于S的最左边或最右边，或者位于S上方或下方，则无需考虑B的行与S的交点。这可以节省很多计算。}

- displayName

---

我认为您可能误解了问题，它是这样写的：“我有两个多边形，定义为一系列 2D 浮点值。”您仍然可以以某种方式使用您的算法（例如生成一堆随机旋转和平移版本的多边形 S，并找到第一个通过过滤器的版本），但作者可能更需要一种更有效的算法。 - Michael Petito

@MichaelPetito：你说得对。我正在尝试是否仍然可以编辑并回答这个问题。如果不行，我会删除我的回答。 - displayName

我不会删除你的回答，因为它可能提供了一个合理的替代方案或者有用的信息。 - Michael Petito

@MichaelPetito：已修改文本以保持其有用性，并在顶部添加了有用的免责声明。再次感谢您指出错误。 - displayName

Answer 2

如果其他答案有用，这是它的补充。它展示了另一种方法来判断较小多边形是否被包含在较大多边形中。

为了测试一个多边形的包含关系，您需要检查多边形的所有边缘是否被包含在内。为了测试所有边缘，需要测试每条边缘上的所有点是否被包含。

1. 通过在现有顶点之间添加顶点来密集化较小的多边形。下面的图像显示了线的密集化。
2. 现在针对密集化后的多边形，测试其所有点是否都位于外部多边形内部。可以通过从该点向两侧发出无限远的线段并计算该线段与较大多边形交点的数量来进行此测试。
3. 如果所有点都在内部，则多边形在内部。

---

_{第一张图片来源。}

^{第二张图片来源。}

- displayName