在多边形内部随机放置一个多边形 [英] Randomly placing a polygon inside of polygon

问题描述

我有两个定义为一系列2D浮点值的多边形.不保证它们是凹的或凸的.他们不会跨过自己.他们不能旋转.我想根据其大小将一个随机放置在另一个中.主要问题是效率.我必须在几秒钟内执行大约200次左右.

我已经研究了几天，并且没有明显的进展.任何线索将不胜感激.

解决方案

^{免责声明: 如果您要在一个较大的多边形内打包多个多边形，那么我认为，此问题是NP难题，因此不太可能开发出高效且精确的算法来解决此问题.多边形可以在平面中连续平移和旋转，这意味着放置可能是无限的，这也使问题的解决空间也变得无限大.如果您只是想寻找较小的多边形是否可以放入较大的多边形中，则我没有一个有效的答案，但是正如您所问的那样-任何线索都将受到赞赏"-这是一个.}

---

让较大的多边形为B，较小的多边形(要插入的多边形)为S.B总共有b个点，S总共有s个点.

---

下图显示了边界框和最小边界矩形.我们使用它来获取快速失败过滤器(非常简单的主意...在下一段中定义).下面显示的框(a)的计算速度更快，而框(b)的过滤精度更高.画一个盒子，可以为您的案件提供更好的投资回报.尽管在下图中，它们都以椭圆而不是多边形为边界，但是您知道了.

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

Crux::如果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> ).

---

算法:

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

1. 读取S的点并确定形成S的线
2. 对于S的每一行，看看它是否与B的任何行相交 ^† (它们已存储在HashMap中)
3. 如果没有交集，则S在B内，而您所要做的就是画线而不必担心交集.

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

---

^† _{此步骤被编写为蛮力以使算法易于理解.否则，可以在此处进行关键的优化，以更快地获得结果.您可以过滤B线.如果B线的端点在S的最左点的左侧或S的最右点的右侧或上方，则无需考虑B线与S的交点. S或S以下.这样可以节省大量计算.}

I have two polygons defined as a series of 2D floating point values. They are not guaranteed to be concave or convex. They do not cross over themselves. They cannot rotate. I want to place one randomly inside the other should it be possible based on it's size. The main problem is efficiency. I have to do this about 200 or so times in a few seconds.

I've been looking into this for a couple of days now, and have made no discernible headway. Any leads would be appreciated.

解决方案

^{Disclaimer: If you are trying to pack multiple polygons inside a bigger polygon then I think, this problem is NP hard 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.}

---

Let the bigger polygon be B and smaller polygon (the one to be inserted) is S. B has a total of b points and S has a total of s points.

---

The image below shows a Bounding Box and a Minimum Bounding Rectangle. We use this to get the Fast Fail Filter (very simple idea... defined in next para). The box (a) shown below is faster to compute while box (b) is more accurate for filtering. Draw that box which gives better return on investment for your case. Though in the figure below they both are bounding an ellipse instead of a polygon but you get the idea.

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

Crux: If any line of B intersects with any line of S, or if all lines of S are outside B, B cannot take S in.

Fast fail filter: Get the bounding rectangles of B and S. If you are not able to place the bounding rectangle of S inside the bounding rectangle of B, then you cannot place the polygon S inside polygon B. This way you fail faster if there is no chance of B to enclose S. Following image illustrates the three cases.

^{(Image taken from: http://www.cs.berkeley.edu/~ug/slide/pipeline/assignments/as4/figures/boundcull.gif)}

---

Preprocessing: Determine the equation of lines that form B. Store them in a HashMap<<Point, Point>, Line> for a step that will be done later. You can uniquely define the line by slope m and intercept c and the end points of your line are going to be the key (<Point, Point>) of the HashMap.

---

The Algorithm:

For every S which has passed the above filter:

1. Read the points of S and determine the lines that form S
2. For every line of S, see if it intersects with any line of B^† (they are stored in the HashMap already)
3. If there is no intersection, S is inside B and all you have to do is just draw the lines without any worry of intersection.

In the worst case, the complexity of this algorithm will be O(bs) for drawing each polygon.

---

^†_{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.}

这篇关于在多边形内部随机放置一个多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！