非重叠非凸多边形

Question

假设一组n个随机分布的非凸多边形P={Pi}，n = |P|，在平面上，它们中的一些重叠（大约50%的非凸多边形相互重叠）。

1] 移动多边形，避免重叠。

2]只允许"small"次移位（尽量保留对象Pi的相对位置）。

在我看来，这个问题是NP难的。我尝试了几种方法（随机优化最小化重叠区域+偏移），将所有方法合而为一（随机摇动），在凸包外添加（适用于凸多边形但对于非凸多边形会发生大偏移），...

最有前途的是使用简单启发式的增量方法（在 2 个方向上移动）。

0] Compute minimum bounding boxes (MBB) for all Pi. Sort Pi by area.
1] Add a Pi to the solution S and check for overlaps
    1.a] Test intersection  Pi vs. all Pj in S.
    1.b] If MBB(Pj) vs. MBB(Pi) overlap, check the polygons Pi vs. Pj: 
        1.b.1] If Pi, Pj overlap, moving Pi perpendicular to Pj (left, right) by s may help
        1.b.2] Suppose Pi1=Pi(sl), Pi2=Pi(sr) to be shifted Pi, shifts sl=s, sr=-s
        1.b.3] Check, which direction is more perspective:
        1.b.4] While intersections Pi1 vs. Pj exist //Left
           1.b.4.a] Preselect collisions Pi1 vs. all Pj by MBB.
           1.b.4.b] If MBB(Pi1) and MBB(Pj) overlap, check Pi1 vs. Pj
           1.b.4.c] If overlap found sl = sl + s;
           1.b.4.c] Shift Pi1(sl);
        1.b.5] While intersections Pi1 vs. Pj exist //Right
           1.b.5.a] Preselect collisions Pi1 vs.all Pj by MBB.
           1.b.5.b] If MBB(Pi1) and MBB(Pj) overlap, check Pi1 vs. Pj
           1.b.5.c] If overlap found sr = sr + s;
           1.b.5.d] Shift Pi2(sr);
        1.b.6] Assign Pi = Pi1 or Pi = Pi2 (the faster).

不幸的是，对于大 n（千）增量方法很慢。是否有可能提高速度或存在更好的方法？大部分精力都花在了不必要的轮班和检查上...

多边形的 Voronoi 镶嵌可能有助于单元内多边形的移动...我们还可以检查哪些 Voronoi 单元受到添加新单元的影响（生成器由多边形表示）...也许，移动可以计算为受影响单元中 Pi 质心和多边形质心的平均向量。

非常感谢您的帮助。

Answer 1

为每个多边形选择一个顶点，确保 none 个所选顶点重合。（如果这不可能，你就有麻烦了。）确定所有多边形的最紧密边界正方形，并将最大正方形的边除以所选顶点之间的最短 horizontal/vertical 距离。

将所有选定顶点的坐标乘以该系数，并相应地平移其余顶点（不重新缩放）。这将把所有多边形分开，同时保持它们的位置非常相似。

也许这个解决方案太"sparse"您的口味；它可以用作重新打包的起点，而不会再次产生重叠。

非重叠非凸多边形

Non-overlapping non-convex polygons

algorithm

computational-geometry

np