問題與重疊的水平矩形

所以我試圖解決圖形問題。基本上有一個容器，假設它的寬度爲600px。如果該容器中只有一個矩形（沒有重疊的矩形），它將佔用它的寬度。但是，問題是當這些矩形重疊時，寬度必須相應縮小。我們給出這個矩形的左上角和左下角的y座標。（比如它開始60px下來，結束120px大容器）問題與重疊的水平矩形

所以我寫了一個重疊算法，檢查是否存在重疊並計算該矩形重疊的矩形的數量（包括它本身）。然後我將容器寬度除以重疊元素的最大數量，以獲得較小矩形的寬度。

for (i = 0; i < events.length; i++) { 
     var event = events[i]; 
     var numCollisions = 0; 
     for (j = 0; j < events.length; j++) { 
      var eventCmp = events[j]; 
      if (event.start <= eventCmp.start && event.end > eventCmp.start || 
       event.start < eventCmp.end && event.end >= eventCmp.end) { 
      numCollisions++; 
     } 
    }

但是，我注意到了這個問題。如果你看下面這張圖片，最右邊的矩形有兩個重疊的矩形。通過我的算法，你會得到容器寬度/ 3（包括矩形本身），這是不正確的。實際的答案是容器寬度/ 2。

enter image description here

所以，問題是（本長篇大論的解釋後），我需要找到，如果兩個矩形水平對齊。幾個小時以來，我一直在嘲笑我。有關我如何做到這一點的任何提示？

來源

2013-02-18 user1054740

你能顯示輸入和期望輸出的圖片嗎？我不確定你的照片是目標還是問題。 – 2013-02-18 01:15:00

顯示的圖片是所需的輸出。我目前使用我的代碼的圖片與左側的兩個矩形相同，但右側的寬度略小（因爲它計算爲容器寬度的1/3而不是1/2） – user1054740 2013-02-18 01:16:18

如果第一個矩形的右側座標大於第二個矩形的左側，您只嘗試增加「numCollisions」？ – bfavaretto 2013-02-18 01:34:35

那麼，最簡單的答案是divide by 2 IF you have a collision（不關心你實際有多少次碰撞）。如果你需要更復雜的東西，你能展示一個更復雜的案例嗎？

來源

2013-02-18 01:19:47

但是可能有多達200個矩形可能以任何方式相撞。例如，淺綠色旁邊可能會有另一個矩形，它會將深綠色，淺綠色和新的縮小爲容器寬度/ 3。基本上這個過程可以重複，不僅僅是容器寬度的一半。 – user1054740 2013-02-18 01:22:14

不是最佳，但易少實現算法中應該是：

foreach y coord in the main container 
    rects = find all rects which contain this y coord 
    foreach rects as rect 
     rect.maxHorizNeighbors = max(rects.length, rect.maxHorizNeighbors)

依然孤單你會需要解決其他一些問題，但這應該讓你開始你的家庭作業。特別是，您可能會遇到橫向差距的情況。生病讓你自己找到。

來源

2013-02-18 01:34:18 goat

問題與重疊的水平矩形

回答

相關問題