问题与重叠的水平矩形

所以我试图解决图形问题。基本上有一个容器，假设它的宽度为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

问题与重叠的水平矩形

回答

相关问题