什么是find重叠矩形区域的高效algorithm

我的情况

  • input:一组矩形
  • 每个矩形包含4个双打,如下所示:(x0,y0,x1,y1)
  • 它们不是以任何angular度“旋转”,它们都是相对于屏幕“上/下”和“左/右”的“普通”矩形
  • 他们被随机放置 – 他们可能在边缘触摸,重叠,或没有任何接触
  • 我将有几百个矩形
  • 这是在C#中实现的

我需要find

  • 由它们重叠形成的区域 – canvas中多于一个矩形“覆盖”的所有区域(例如,具有两个矩形,这将是交叉点)
  • 我不需要重叠的几何形状 – 只是区域(例如:4平方英寸)
  • 重叠不应该被多次计算 – 例如,想像3个尺寸和位置相同的交叉 – 它们彼此重叠 – 这个区域应该被计算一次(而不是三次)

  • 下面的图片包含三个矩形:A,B,C
  • A和B重叠(如虚线所示)
  • B和C重叠(如虚线所示)
  • 我正在寻找的是显示破折号的地方

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA--------------BBB AAAAAAAAAAAAAAAA--------------BBB AAAAAAAAAAAAAAAA--------------BBB AAAAAAAAAAAAAAAA--------------BBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBB-----------CCCCCCCC BBBBBB-----------CCCCCCCC BBBBBB-----------CCCCCCCC CCCCCCCCCCCCCCCCCCC CCCCCCCCCCCCCCCCCCC CCCCCCCCCCCCCCCCCCC CCCCCCCCCCCCCCCCCCC 

15 Solutions collect form web for “什么是find重叠矩形区域的高效algorithm”

计算这个区域的有效方法是使用扫描algorithm。 让我们假设我们通过矩形U:的联合扫描垂直线L(x)

  • 首先,你需要build立一个事件队列Q,在这个例子中,这个matrix的所有x坐标(左和右)的有序列表。
  • 在扫描期间,你应该保持一维数据结构,它应该给出L(x)和U的交集的总长度。重要的是这个长度在Q的两个连续事件q和q'之间是恒定的。如果l(q)表示q与q相交的L(q +)的总长度(即q恰好在q的右侧),则事件q与q'之间扫过L的区域恰好为l(q)*(q' – q)。
  • 你只需要总结所有这些扫描区域就可以得到全部扫描区域。

我们仍然需要解决一维问题。 你需要一个一维结构,dynamic计算(垂直)段的联合。 dynamic地,我的意思是你有时候会添加一个新的段,有时候会删除一个。

我已经详细的回答了这个折叠范围问题,如何以静态的方式来实现(实际上是一维扫描)。 所以如果你想简单一些,你可以直接应用(通过重新计算每个事件的联合)。 如果你想要更有效的东西,你只需要适应一下:

  • 假设你知道段S 1 … S n的并集由不相交的段D 1 … D k组成 。 添加S n + 1非常容易,只需要在D 1 … D k的两端之间findS n + 1的两端即可。
  • 假设你知道段S 1 … S n的联合由不相交段D 1 … D k组成 ,去掉段S i (假定S i包含在D j中 )意味着重新计算D j除了S i之外(使用静态algorithm)组成。

这是你的dynamicalgorithm。 假设您将使用具有日志时间位置查询的sorting集合来表示D 1 … D k ,这可能是您可以获得的最有效的非专用方法。

一种出路的方法是将其绘制到canvas上! 使用半透明颜色绘制每个矩形。 .NET运行库将在优化的本机代码中执行绘图 – 甚至使用硬件加速器。

然后,你必须回读像素。 每个像素是背景颜色,矩形颜色还是其他颜色? 唯一的办法可以是另一种颜色,如果两个或更多的矩形重叠…

如果这太欺骗了,我会推荐四叉树作为另一个回答者,或者r-tree 。

这是我在TopCoder SRM 160 Div 2中使用的一些快速而脏的代码。

t =顶部
b = bottom
l =离开
r =正确

 public class Rect { public int t, b, l, r; public Rect(int _l, int _b, int _r, int _t) { t = _t; b = _b; l = _l; r = _r; } public bool Intersects(Rect R) { return !(l > Rr || Rl > r || Rb > t || b > Rt); } public Rect Intersection(Rect R) { if(!this.Intersects(R)) return new Rect(0,0,0,0); int [] horiz = {l, r, Rl, Rr}; Array.Sort(horiz); int [] vert = {b, t, Rb, Rt}; Array.Sort(vert); return new Rect(horiz[1], vert[1], horiz[2], vert[2]); } public int Area() { return (t - b)*(rl); } public override string ToString() { return l + " " + b + " " + r + " " + t; } } 

这是我头顶的东西听起来像是可能的:

  1. 用双键创build一个字典,以及一个矩形+布尔值列表,如下所示:

    Dictionary <Double,List <KeyValuePair <Rectangle,Boolean >>>矩形;

  2. 对于您的集合中的每个矩形,findx0和x1值的相应列表,并将该矩形添加到该列表中,x0的布尔值为true,x1为false。 这样,您现在可以得到每个矩形input(true)或离开(false)x方向的所有x坐标的完整列表

  3. 从字典中获取所有关键字(所有不同的x坐标),对它们进行sorting,然后按顺序遍历它们,确保既可以获得当前的x值,也可以获得下一个x值(您需要它们) )。 这给你个别的矩形条

  4. 维护一组当前正在查看的矩形,它从空白处开始。 对于在第3点迭代的每个x值,如果矩形注册为真值,则将其添加到集合中,否则将其删除。
  5. 对于条,按y坐标对矩形进行sorting
  6. 循环穿过长条的长方形,计算重叠距离(至今还不清楚如何有效地做到这一点)
  7. 计算重叠距离的条带宽度高度以获得区域

例如,5个矩形,彼此重叠,从a到e:

 aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb aaaaaaaadddddddddddddddddddddddddddddbbbbbb aaaaaaaadddddddddddddddddddddddddddddbbbbbb ddddddddddddddddddddddddddddd ddddddddddddddddddddddddddddd ddddddddddddddeeeeeeeeeeeeeeeeee ddddddddddddddeeeeeeeeeeeeeeeeee ddddddddddddddeeeeeeeeeeeeeeeeee ccccccccddddddddddddddeeeeeeeeeeeeeeeeee ccccccccddddddddddddddeeeeeeeeeeeeeeeeee cccccccccccc eeeeeeeeeeeeeeeeee cccccccccccc eeeeeeeeeeeeeeeeee cccccccccccc cccccccccccc 

这是x坐标列表:

 vvvvvvvvv |aaaaaaa|aa|aaaa | bbbbbbbbbb|bb|bbb |aaaaaaa|aa|aaaa | bbbbbbbbbb|bb|bbb |aaaaaaa|aa|aaaa | bbbbbbbbbb|bb|bbb |aaaaaaa|aa|aaaa | bbbbbbbbbb|bb|bbb |aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb |aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb | ddd|dddddddddd|dddddddddddddd | | ddd|dddddddddd|dddddddddddddd | | ddd|ddddddddddeeeeeeeeeeeeeeeeee | ddd|ddddddddddeeeeeeeeeeeeeeeeee | ddd|ddddddddddeeeeeeeeeeeeeeeeee ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee cccccccccccc eeeeeeeeeeeeeeeeee cccccccccccc eeeeeeeeeeeeeeeeee cccccccccccc cccccccccccc 

该列表将是(每个v只是简单地给出一个坐标从0开始,并上升):

 0: +a, +c 1: +d 2: -c 3: -a 4: +e 5: +b 6: -d 7: -e 8: -b 

因此,每个条将(从上到下排列的矩形):

 0-1: a, c 1-2: a, d, c 2-3: a, d 3-4: d 4-5: d, e 5-6: b, d, e 6-7: b, e 7-8: b 

对于每个条,重叠将是:

 0-1: none 1-2: a/d, d/c 2-3: a/d 3-4: none 4-5: d/e 5-6: b/d, d/e 6-7: none 7-8: none 

我可以想象,顶部检查的sorting+进入/离开algorithm的变化也是可行的:

  1. 对我们当前正在分析的矩形进行sorting,从顶部到底部,对于具有相同顶部坐标的矩形,按底部坐标sorting
  2. 遍历y坐标,当你input一个矩形时,将它添加到集合中,当你离开一个矩形时,将它从集合中移除
  3. 每当该集合有多个矩形时,就会有重叠(如果您确保添加/删除具有相同顶部/底部坐标的所有矩形,则您正在查看的是多个重叠的矩形,这不会成为问题

对于上面的1-2条,你可以像这样迭代:

 0. empty set, zero sum 1. enter a, add a to set (1 rectangle in set) 2. enter d, add d to set (>1 rectangles in set = overlap, store this y-coordinate) 3. leave a, remove a from set (now back from >1 rectangles in set, add to sum: y - stored_y 4. enter c, add c to set (>1 rectangles in set = overlap, store this y-coordinate) 5. leave d, remove d from set (now back from >1 rectangles in set, add to sum: y - stored_y) 6. multiply sum with width of strip to get overlapping areas 

你实际上并不需要在这里维护一个实际的集合,只要你在里面的矩形的数量,每当这个从1到2,存储y,每当它从2下降到1,计算当前y – 存储y,并总结这个差异。

希望这是可以理解的,正如我所说,这是我的头顶,没有任何testing。

使用示例:

  1 2 3 4 5 6

 1 + --- + --- +
    |  |   
 2 + A + --- + --- +
    |  |  B |
 3 + + + --- + --- +
    |  |  |  |  |
 4 + --- + --- + --- + --- ++
                |  |
 5 + C +
                |  |
 6 + --- + --- +

1)将所有的x坐标(包括左和右)收集到列表中,然后对其进行sorting并删除重复项

  1 3 4 5 6 

2)将所有y坐标(顶部和底部)收集到列表中,然后对其进行sorting并删除重复项

  1 2 3 4 6 

3)通过唯一x坐标*唯一y坐标之间的间隔数量之间的间隔数量来创build二维数组。

  4 * 4 

4)将所有矩形绘制到这个网格中,增加它发生的每个单元的计数:

    1 3 4 5 6

 1 + --- +
    |  1 |  0 0 0
 2 + --- + --- + --- +
    |  1 |  1 |  1 |  0
 3 + --- + --- + --- + --- +
    |  1 |  1 |  2 |  1 |
 4 + --- + --- + --- + --- +
      0 0 |  1 |  1 |
 6 + --- + --- +

5)网格中具有大于1的单元的区域的总和是重叠区域。 为了在稀疏使用情况下提高效率,每次将单元格从1移动到2时,可以在绘制矩形时实际上保持该区域的总计。


在这个问题中,矩形被描述为四个双打。 加倍通常包含舍入误差,并且误差可能会蔓延到您计算的重叠区域。 如果合法坐标位于有限点处,请考虑使用整数表示。


PS使用硬件加速器在我的其他答案是不是这样一个简单的想法,如果分辨率是可以接受的。 与上面概述的方法相比,它的代码很less实现。 马的课程。

以下是我为区域扫描algorithm编写的代码:

 #include <iostream> #include <vector> using namespace std; class Rectangle { public: int x[2], y[2]; Rectangle(int x1, int y1, int x2, int y2) { x[0] = x1; y[0] = y1; x[1] = x2; y[1] = y2; }; void print(void) { cout << "Rect: " << x[0] << " " << y[0] << " " << x[1] << " " << y[1] << " " <<endl; }; }; // return the iterator of rec in list vector<Rectangle *>::iterator bin_search(vector<Rectangle *> &list, int begin, int end, Rectangle *rec) { cout << begin << " " <<end <<endl; int mid = (begin+end)/2; if (list[mid]->y[0] == rec->y[0]) { if (list[mid]->y[1] == rec->y[1]) return list.begin() + mid; else if (list[mid]->y[1] < rec->y[1]) { if (mid == end) return list.begin() + mid+1; return bin_search(list,mid+1,mid,rec); } else { if (mid == begin) return list.begin()+mid; return bin_search(list,begin,mid-1,rec); } } else if (list[mid]->y[0] < rec->y[0]) { if (mid == end) { return list.begin() + mid+1; } return bin_search(list, mid+1, end, rec); } else { if (mid == begin) { return list.begin() + mid; } return bin_search(list, begin, mid-1, rec); } } // add rect to rects void add_rec(Rectangle *rect, vector<Rectangle *> &rects) { if (rects.size() == 0) { rects.push_back(rect); } else { vector<Rectangle *>::iterator it = bin_search(rects, 0, rects.size()-1, rect); rects.insert(it, rect); } } // remove rec from rets void remove_rec(Rectangle *rect, vector<Rectangle *> &rects) { vector<Rectangle *>::iterator it = bin_search(rects, 0, rects.size()-1, rect); rects.erase(it); } // calculate the total vertical length covered by rectangles in the active set int vert_dist(vector<Rectangle *> as) { int n = as.size(); int totallength = 0; int start, end; int i = 0; while (i < n) { start = as[i]->y[0]; end = as[i]->y[1]; while (i < n && as[i]->y[0] <= end) { if (as[i]->y[1] > end) { end = as[i]->y[1]; } i++; } totallength += end-start; } return totallength; } bool mycomp1(Rectangle* a, Rectangle* b) { return (a->x[0] < b->x[0]); } bool mycomp2(Rectangle* a, Rectangle* b) { return (a->x[1] < b->x[1]); } int findarea(vector<Rectangle *> rects) { vector<Rectangle *> start = rects; vector<Rectangle *> end = rects; sort(start.begin(), start.end(), mycomp1); sort(end.begin(), end.end(), mycomp2); // active set vector<Rectangle *> as; int n = rects.size(); int totalarea = 0; int current = start[0]->x[0]; int next; int i = 0, j = 0; // big loop while (j < n) { cout << "loop---------------"<<endl; // add all recs that start at current while (i < n && start[i]->x[0] == current) { cout << "add" <<endl; // add start[i] to AS add_rec(start[i], as); cout << "after" <<endl; i++; } // remove all recs that end at current while (j < n && end[j]->x[1] == current) { cout << "remove" <<endl; // remove end[j] from AS remove_rec(end[j], as); cout << "after" <<endl; j++; } // find next event x if (i < n && j < n) { if (start[i]->x[0] <= end[j]->x[1]) { next = start[i]->x[0]; } else { next = end[j]->x[1]; } } else if (j < n) { next = end[j]->x[1]; } // distance to next event int horiz = next - current; cout << "horiz: " << horiz <<endl; // figure out vertical dist int vert = vert_dist(as); cout << "vert: " << vert <<endl; totalarea += vert * horiz; current = next; } return totalarea; } int main() { vector<Rectangle *> rects; rects.push_back(new Rectangle(0,0,1,1)); rects.push_back(new Rectangle(1,0,2,3)); rects.push_back(new Rectangle(0,0,3,3)); rects.push_back(new Rectangle(1,0,5,1)); cout << findarea(rects) <<endl; } 

如果将每个矩形分割成更小的矩形,可以简化这个问题。 收集所有矩形的所有X和Y坐标,这些将成为您的分割点 – 如果一个矩形穿过线,将它分成两部分。 当你完成后,你有一个重叠0%或100%的矩形列表,如果你sorting他们应该很容易find相同的。

最简单的解决scheme

 import numpy as np A = np.zeros((100, 100)) B = np.zeros((100, 100)) A[rect1.top : rect1.bottom, rect1.left : rect1.right] = 1 B[rect2.top : rect2.bottom, rect2.left : rect2.right] = 1 area_of_union = np.sum((A + B) > 0) area_of_intersect = np.sum((A + B) > 1) 

在这个例子中,我们创build了两个零matrix,它们是canvas的大小。 对于每个矩形,填充其中一个矩形占据空间的matrix。 然后总结matrix。 现在sum(A+B > 0)是联合的面积, sum(A+B > 1)是重叠的面积。 这个例子可以很容易地推广到多个矩形。

在链接http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html上列出了一个解决scheme,用于查找多个矩形的总面积,使得重叠区域仅计算一次&#x3002;

对于每对连续的垂直扫描线,可以扩展上述解决scheme以仅计算重叠区域(并且即使重叠区域被多个矩形覆盖也仅一次)。

如果瞄准只是找出所有矩形所覆盖的总面积,则不需要水平扫描线,只需要将两条垂直扫描线之间的所有矩形合并即可得到该面积。

另一方面,如果只想计算重叠区域,则需要水平扫描线来确定垂直(y1,y2)扫描线之间有多less个矩形重叠。

这是我在Java中实现的解决scheme的工作代码。

 import java.io.*; import java.util.*; class Solution { static class Rectangle{ int x; int y; int dx; int dy; Rectangle(int x, int y, int dx, int dy){ this.x = x; this.y = y; this.dx = dx; this.dy = dy; } Range getBottomLeft(){ return new Range(x, y); } Range getTopRight(){ return new Range(x + dx, y + dy); } @Override public int hashCode(){ return (x+y+dx+dy)/4; } @Override public boolean equals(Object other){ Rectangle o = (Rectangle) other; return ox == this.x && oy == this.y && o.dx == this.dx && o.dy == this.dy; } @Override public String toString(){ return String.format("X = %d, Y = %d, dx : %d, dy : %d", x, y, dx, dy); } } static class RW{ Rectangle r; boolean start; RW (Rectangle r, boolean start){ this.r = r; this.start = start; } @Override public int hashCode(){ return r.hashCode() + (start ? 1 : 0); } @Override public boolean equals(Object other){ RW o = (RW)other; return o.start == this.start && orequals(this.r); } @Override public String toString(){ return "Rectangle : " + r.toString() + ", start = " + this.start; } } static class Range{ int l; int u; public Range(int l, int u){ this.l = l; this.u = u; } @Override public int hashCode(){ return (l+u)/2; } @Override public boolean equals(Object other){ Range o = (Range) other; return ol == this.l && ou == this.u; } @Override public String toString(){ return String.format("L = %d, U = %d", l, u); } } static class XComp implements Comparator<RW>{ @Override public int compare(RW rw1, RW rw2){ //TODO : revisit these values. Integer x1 = -1; Integer x2 = -1; if(rw1.start){ x1 = rw1.rx; }else{ x1 = rw1.rx + rw1.r.dx; } if(rw2.start){ x2 = rw2.rx; }else{ x2 = rw2.rx + rw2.r.dx; } return x1.compareTo(x2); } } static class YComp implements Comparator<RW>{ @Override public int compare(RW rw1, RW rw2){ //TODO : revisit these values. Integer y1 = -1; Integer y2 = -1; if(rw1.start){ y1 = rw1.ry; }else{ y1 = rw1.ry + rw1.r.dy; } if(rw2.start){ y2 = rw2.ry; }else{ y2 = rw2.ry + rw2.r.dy; } return y1.compareTo(y2); } } public static void main(String []args){ Rectangle [] rects = new Rectangle[4]; rects[0] = new Rectangle(10, 10, 10, 10); rects[1] = new Rectangle(15, 10, 10, 10); rects[2] = new Rectangle(20, 10, 10, 10); rects[3] = new Rectangle(25, 10, 10, 10); int totalArea = getArea(rects, false); System.out.println("Total Area : " + totalArea); int overlapArea = getArea(rects, true); System.out.println("Overlap Area : " + overlapArea); } static int getArea(Rectangle []rects, boolean overlapOrTotal){ printArr(rects); // step 1: create two wrappers for every rectangle RW []rws = getWrappers(rects); printArr(rws); // steps 2 : sort rectangles by their x-coordinates Arrays.sort(rws, new XComp()); printArr(rws); // step 3 : group the rectangles in every range. Map<Range, List<Rectangle>> rangeGroups = groupRects(rws, true); for(Range xrange : rangeGroups.keySet()){ List<Rectangle> xRangeRects = rangeGroups.get(xrange); System.out.println("Range : " + xrange); System.out.println("Rectangles : "); for(Rectangle rectx : xRangeRects){ System.out.println("\t" + rectx); } } // step 4 : iterate through each of the pairs and their rectangles int sum = 0; for(Range range : rangeGroups.keySet()){ List<Rectangle> rangeRects = rangeGroups.get(range); sum += getOverlapOrTotalArea(rangeRects, range, overlapOrTotal); } return sum; } static Map<Range, List<Rectangle>> groupRects(RW []rws, boolean isX){ //group the rws with either x or y coordinates. Map<Range, List<Rectangle>> rangeGroups = new HashMap<Range, List<Rectangle>>(); List<Rectangle> rangeRects = new ArrayList<Rectangle>(); int i=0; int prev = Integer.MAX_VALUE; while(i < rws.length){ int curr = isX ? (rws[i].start ? rws[i].rx : rws[i].rx + rws[i].r.dx): (rws[i].start ? rws[i].ry : rws[i].ry + rws[i].r.dy); if(prev < curr){ Range nRange = new Range(prev, curr); rangeGroups.put(nRange, rangeRects); rangeRects = new ArrayList<Rectangle>(rangeRects); } prev = curr; if(rws[i].start){ rangeRects.add(rws[i].r); }else{ rangeRects.remove(rws[i].r); } i++; } return rangeGroups; } static int getOverlapOrTotalArea(List<Rectangle> rangeRects, Range range, boolean isOverlap){ //create horizontal sweep lines similar to vertical ones created above // Step 1 : create wrappers again RW []rws = getWrappers(rangeRects); // steps 2 : sort rectangles by their y-coordinates Arrays.sort(rws, new YComp()); // step 3 : group the rectangles in every range. Map<Range, List<Rectangle>> yRangeGroups = groupRects(rws, false); //step 4 : for every range if there are more than one rectangles then computer their area only once. int sum = 0; for(Range yRange : yRangeGroups.keySet()){ List<Rectangle> yRangeRects = yRangeGroups.get(yRange); if(isOverlap){ if(yRangeRects.size() > 1){ sum += getArea(range, yRange); } }else{ if(yRangeRects.size() > 0){ sum += getArea(range, yRange); } } } return sum; } static int getArea(Range r1, Range r2){ return (r2.u-r2.l)*(r1.u-r1.l); } static RW[] getWrappers(Rectangle []rects){ RW[] wrappers = new RW[rects.length * 2]; for(int i=0,j=0;i<rects.length;i++, j+=2){ wrappers[j] = new RW(rects[i], true); wrappers[j+1] = new RW(rects[i], false); } return wrappers; } static RW[] getWrappers(List<Rectangle> rects){ RW[] wrappers = new RW[rects.size() * 2]; for(int i=0,j=0;i<rects.size();i++, j+=2){ wrappers[j] = new RW(rects.get(i), true); wrappers[j+1] = new RW(rects.get(i), false); } return wrappers; } static void printArr(Object []a){ for(int i=0; i < a.length;i++){ System.out.println(a[i]); } System.out.println(); } 

如果你的矩形要稀疏(大部分不相交),那么值得一看recursion维聚类。 否则四叉树似乎是要走的路(正如其他海报所提到的那样。

这是计算机游戏中碰撞检测中的一个常见问题,所以不乏资源提出解决的办法。

这是一个很好的博客文章,总结RCD。

这里有一篇Dr.Dobbs的文章总结了各种碰撞检测algorithm,这将是合适的。

这种types的碰撞检测通常被称为AABB(Axis Aligned Bounding Box),这对于谷歌search来说是一个很好的起点。

您可以在x和y轴上find重叠部分并将其相乘。

 int LineOverlap(int line1a, line1b, line2a, line2b) { // assume line1a <= line1b and line2a <= line2b if (line1a < line2a) { if (line1b > line2b) return line2b-line2a; else if (line1b > line2a) return line1b-line2a; else return 0; } else if (line2a < line1b) return line2b-line1a; else return 0; } int RectangleOverlap(Rect rectA, rectB) { return LineOverlap(rectA.x1, rectA.x2, rectB.x1, rectB.x2) * LineOverlap(rectA.y1, rectA.y2, rectB.y1, rectB.y2); } 

我发现了一个不同于扫描algorithm的解决scheme。

由于你的矩形都是矩形放置的,矩形的水平和垂直线将形成一个矩形的不规则的网格。 您可以在此网格上“绘制”矩形; 这意味着,您可以确定网格的哪些字段将被填写。 由于网格线是由给定矩形的边界形成的,因此此网格中的字段将始终完全为空或由矩形完全填充。

我必须用Java解决这个问题,所以这里是我的解决scheme: http : //pastebin.com/03mss8yf

该function计算矩形占用的完整区域。 如果您只对“重叠”部分感兴趣,则必须在第70行和第72行之间扩展代码块。也许可以使用第二组来存储哪些网格域被多次使用。 第70行和第72行之间的代码应该replace为如下代码块:

 GridLocation gl = new GridLocation(curX, curY); if(usedLocations.contains(gl) && usedLocations2.add(gl)) { ret += width*height; } else { usedLocations.add(gl); } 

这里的usedLocations2variables与usedLocationstypes相同; 它将在同一点build造。

我并不十分熟悉复杂度计算。 所以我不知道两个解决scheme(扫描或我的网格解决scheme)中的哪一个会更好地执行/缩放。

考虑到我们有两个矩形(A和B),我们有它们的左下(x1,y1)和右上(x2,y2)的协调。 使用下面的一段代码可以计算C ++中的重叠区域。

  #include <iostream> using namespace std; int rectoverlap (int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) { int width, heigh, area; if (ax2<bx1 || ay2<by1 || ax1>bx2 || ay1>by2) { cout << "Rectangles are not overlapped" << endl; return 0; } if (ax2>=bx2 && bx1>=ax1){ width=bx2-bx1; heigh=by2-by1; } else if (bx2>=ax2 && ax1>=bx1) { width=ax2-ax1; heigh=ay2-ay1; } else { if (ax2>bx2){ width=bx2-ax1; } else { width=ax2-bx1; } if (ay2>by2){ heigh=by2-ay1; } else { heigh=ay2-by1; } } area= heigh*width; return (area); } int main() { int ax1,ay1,ax2,ay2,bx1,by1,bx2,by2; cout << "Inter the x value for bottom left for rectangle A" << endl; cin >> ax1; cout << "Inter the y value for bottom left for rectangle A" << endl; cin >> ay1; cout << "Inter the x value for top right for rectangle A" << endl; cin >> ax2; cout << "Inter the y value for top right for rectangle A" << endl; cin >> ay2; cout << "Inter the x value for bottom left for rectangle B" << endl; cin >> bx1; cout << "Inter the y value for bottom left for rectangle B" << endl; cin >> by1; cout << "Inter the x value for top right for rectangle B" << endl; cin >> bx2; cout << "Inter the y value for top right for rectangle B" << endl; cin >> by2; cout << "The overlapped area is " << rectoverlap (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) << endl; } 

下面的答案应该只给总面积一次。 它来以前的答案,但现在在C#中实现。 它也适用于浮点数(或者,如果你需要的话,它也是双倍的(它不会超过VALUES)。

积分: http : //codercareer.blogspot.co.il/2011/12/no-27-area-of-rectangles.html

编辑:OP要求重叠区域 – 这显然非常简单:

 var totArea = rects.Sum(x => x.Width * x.Height); 

然后答案是:

 var overlappingArea =totArea-GetArea(rects) 

这里是代码:

  #region rectangle overlapping /// <summary> /// see algorithm for detecting overlapping areas here: https://stackoverflow.com/a/245245/3225391 /// or easier here: /// http://codercareer.blogspot.co.il/2011/12/no-27-area-of-rectangles.html /// </summary> /// <param name="dim"></param> /// <returns></returns> public static float GetArea(RectangleF[] rects) { List<float> xs = new List<float>(); foreach (var item in rects) { xs.Add(item.X); xs.Add(item.Right); } xs = xs.OrderBy(x => x).Cast<float>().ToList(); rects = rects.OrderBy(rec => rec.X).Cast<RectangleF>().ToArray(); float area = 0f; for (int i = 0; i < xs.Count - 1; i++) { if (xs[i] == xs[i + 1])//not duplicate continue; int j = 0; while (rects[j].Right < xs[i]) j++; List<Range> rangesOfY = new List<Range>(); var rangeX = new Range(xs[i], xs[i + 1]); GetRangesOfY(rects, j, rangeX, out rangesOfY); area += GetRectArea(rangeX, rangesOfY); } return area; } private static void GetRangesOfY(RectangleF[] rects, int rectIdx, Range rangeX, out List<Range> rangesOfY) { rangesOfY = new List<Range>(); for (int j = rectIdx; j < rects.Length; j++) { if (rangeX.less < rects[j].Right && rangeX.greater > rects[j].Left) { rangesOfY = Range.AddRange(rangesOfY, new Range(rects[j].Top, rects[j].Bottom)); #if DEBUG Range rectXRange = new Range(rects[j].Left, rects[j].Right); #endif } } } static float GetRectArea(Range rangeX, List<Range> rangesOfY) { float width = rangeX.greater - rangeX.less, area = 0; foreach (var item in rangesOfY) { float height = item.greater - item.less; area += width * height; } return area; } internal class Range { internal static List<Range> AddRange(List<Range> lst, Range rng2add) { if (lst.isNullOrEmpty()) { return new List<Range>() { rng2add }; } for (int i = lst.Count - 1; i >= 0; i--) { var item = lst[i]; if (item.IsOverlapping(rng2add)) { rng2add.Merge(item); lst.Remove(item); } } lst.Add(rng2add); return lst; } internal float greater, less; public override string ToString() { return $"ln{less} gtn{greater}"; } internal Range(float less, float greater) { this.less = less; this.greater = greater; } private void Merge(Range rng2add) { this.less = Math.Min(rng2add.less, this.less); this.greater = Math.Max(rng2add.greater, this.greater); } private bool IsOverlapping(Range rng2add) { return !(less > rng2add.greater || rng2add.less > greater); //return // this.greater < rng2add.greater && this.greater > rng2add.less // || this.less > rng2add.less && this.less < rng2add.greater // || rng2add.greater < this.greater && rng2add.greater > this.less // || rng2add.less > this.less && rng2add.less < this.greater; } } #endregion rectangle overlapping 
  • 旋转图像并裁剪黑色边框
  • 我应该购买哪些数据结构和algorithm书?
  • 哪种并行sortingalgorithm具有最好的平均情况下的性能?
  • 如何将表格旋转45度并将结果保存到另一个表格中?
  • Prim和Dijkstraalgorithm之间的区别?
  • 何时使用遗传algorithm与什么时候使用neural network?
  • 为什么迭代k路合并O(nk ^ 2)?
  • 带数组结构的数组
  • 如何使用合并sortingalgorithm就地sorting?
  • 树的深度和高度有什么区别?
  • 什么是2048年游戏的最佳algorithm?