algorithm - 将多边形随机放置在多边形内部

Question

我有两个定义为一系列二维浮点值的多边形。它们不能保证是凹的或凸的。他们不跨越自己。他们不能旋转。如果可能的话，我想根据它的大小将一个随机放置在另一个里面。主要问题是效率。我必须在几秒钟内执行大约 200 次左右。

我已经研究了几天了，但没有取得明显的进展。任何线索将不胜感激。

Answer 1

^{免责声明: 如果您尝试将多个多边形打包到一个更大的多边形中，那么我认为，this problem is NP hard因此不太可能开发出一种有效且精确的算法来解决这个问题。多边形可以在一个平面内连续平移和旋转，这意味着放置可以是无限的，这使得问题的解空间也是无限的。如果您只是想找出较小的多边形是否可以放入较大的多边形中，我没有一个有效的答案，但正如您所问的 - “任何线索都将不胜感激” - 这里有一个。}

---

设较大的多边形为 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 唯一地定义线，线的端点将成为关键 ( <Point, Point> ) 的 HashMap。

---

算法:

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

1. 读取S的点并确定构成S的线
2. 对于 S 的每一行，查看它是否与 B^† 的任何一行相交(它们已经存储在 HashMap 中)
3. 如果没有交点，S 在 B 里面，您只需画线即可，无需担心交点。

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

---

^†_{这一步是暴力编写的，目的是让算法易于理解。否则，这里可能会进行关键优化，以更快地给出结果。可以过滤B的线。如果B的线的端点在S的最左边点的左边，或者在S的最右边的点的右边或上面，则不需要考虑与S相交的B线S或低于S。这样可以节省很多计算。}