非重叠的非凸多边形

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

1]移动多边形，使其不发生重叠。

2]只允许“小”换档（尽可能保留对象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质心和质心的平均向量。

非常感谢您的帮助。

来源

2015-12-05 justik

你是什么意思的小班？ –

@ n.m为避免物体的重新洗牌，应尽可能保留它们的相对位置。使用差分进化，我试图最小化包含平移和重叠区域平方的目标函数。 – justik

@ nm一个简单的方法，在S的凸包外部添加Pi导致旧位置和新位置之间的较大残差... – justik

选择每个多边形的一个顶点，确保没有选定的顶点重合。（如果这不可行，则遇到问题。）确定所有多边形的最窄边界平方，并将最大平方的边除以所选顶点之间的最短水平/垂直距离。

将所有选定顶点的坐标乘以该因子，并相应地转换剩余的顶点（不重新缩放）。这将使所有多边形分开，同时保持其位置非常相似。

也许这个解决方案对您的口味来说太“稀疏”了;它可以作为重新包装的起点，而不会再次产生重叠。

来源

2015-12-08 09:41:11

非重叠的非凸多边形

回答

相关问题