非重疊的非凸多邊形

假設一組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

非重疊的非凸多邊形

回答

相關問題