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

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

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

^{Disclaimer: If you are trying to pack multiple polygons inside a bigger polygon then I think, this problem is NP hard https://www.researchgate.net/publication/2632474_Translational_Polygon_Containment_and_Minimal_Enclosure_using_Geometric_Algorithms_and_Mathematical_Programming so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. The polygon can continuously translate and rotate in a plane, which means the placements may be infinite and this makes the solution space of the problem also infinite. If you are just trying to find if the smaller polygon can fit inside the bigger one, I am short of an efficient answer, but as you have asked - "Any leads would be appreciated" - here is one.}

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

下图显示了边界框和最小边界矩形。我们用它来获得快速失败过滤器（非常简单的想法......在下一段中定义）。下面显示的框 (a) 计算速度更快，而框 (b) 的过滤更准确。画出那个可以为您的案例带来更好投资回报的方框。尽管在下图中，它们都围绕椭圆而不是多边形，但您明白了。

^{(Image taken from: http://portal.ku.edu.tr/~cbasdogan/Tutorials/imageU21.JPG http://portal.ku.edu.tr/~cbasdogan/Tutorials/imageU21.JPG)}

Crux:如果 B 的任意直线与 S 的任意直线相交，或者 S 的所有直线都在 B 之外，则 B 不能将 S 纳入其中。

快速失败过滤器：获取 B 和 S 的外接矩形。如果您无法将 S 的外接矩形放置在 B 的外接矩形内，则您无法将多边形 S 放置在多边形 B 内。这样，如果没有机会，您会失败得更快。 B 包围 S。下图说明了这三种情况。

^{(Image taken from: http://www.cs.berkeley.edu/~ug/slide/pipeline/assignments/as4/figures/boundcull.gif 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. For every line of S, see if it intersects with any line of B^† (they are stored in the HashMap already)
3. 如果没有交点，S就在B的内部，你所要做的就是画线，不用担心交点。

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

^†_{This step is written brute-force to keep the algo easy to understand. Otherwise a critical optimization that will give result faster is possible here. You can filter lines of B. You need not consider a line of B for intersection with S if the endpoints of the line of B are to the left of the leftmost point of S, or to the right of the rightmost point of S or above S or below S. This can save a lot of calculations.}