-1

我对一种算法有疑问。我想计算 2 个矩形的相交面积（都与 OX 和 OY 平行）。矩形（我们称之为A）由（x1，y1，x2，y2）左上角（x1，y1）和右下角（x2，y2）描述，第二个将是B（x3，y3，x4， y4)。我想到了一种算法，但它似乎很蹩脚。

if(all of the points of rectangle A are inside of rectangle B)
     calculate(A);
else if(all of points the points of rectangle B are in A)
     calculate(B);
else if(x1 y1 is inside rectangle B)
        if(x1 is on the left from x3){
            if(y1 is under the y3)
         else
        }

等等它会很长很傻。

4

1 回答 1

1

是的，这似乎有点低效，因为我认为，问题是可分离的，可以扩展到3维或更多维。

计算维度 x 中的重叠宽度和维度 y 中的重叠高度并将它们相乘就足够了。

（如果矩形在某个维度上不重叠，则该值为 0）

通过比较每个矩形的 min_x、max_x 值来进行重叠检测：

 <------>  <------->   vs.  <-----> <----->
 a      b  c       d        c     d a     b
 Thus if b<=c OR a>=d, then no overlapping length = 0

 <------------->   or   <------------->
 a    <---->   b        a       <------------->
      c    d                    c     b       d
 + the 2 symmetric cases (swap ab & cd)

从最后几行开始，公共区域的端点是d & b 的最小值；公共区域的起点是 a & c 的最大值。

那么公共区域是 min(d,b) - max (a,c) - 如果这是负数怎么办？好吧，您刚刚检查了第一行的条件...

于 2012-10-23T18:44:23.970 回答