什么是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 计算这个区域的有效方法是使用扫描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; } }
这是我头顶的东西听起来像是可能的：
-
用双键创build一个字典，以及一个矩形+布尔值列表，如下所示：
Dictionary <Double，List <KeyValuePair <Rectangle，Boolean >>>矩形;
-
对于您的集合中的每个矩形，findx0和x1值的相应列表，并将该矩形添加到该列表中，x0的布尔值为true，x1为false。 这样，您现在可以得到每个矩形input（true）或离开（false）x方向的所有x坐标的完整列表
-
从字典中获取所有关键字（所有不同的x坐标），对它们进行sorting，然后按顺序遍历它们，确保既可以获得当前的x值，也可以获得下一个x值（您需要它们） ）。 这给你个别的矩形条
- 维护一组当前正在查看的矩形，它从空白处开始。 对于在第3点迭代的每个x值，如果矩形注册为真值，则将其添加到集合中，否则将其删除。
- 对于条，按y坐标对矩形进行sorting
- 循环穿过长条的长方形，计算重叠距离（至今还不清楚如何有效地做到这一点）
- 计算重叠距离的条带宽度高度以获得区域
例如，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的变化也是可行的：
- 对我们当前正在分析的矩形进行sorting，从顶部到底部，对于具有相同顶部坐标的矩形，按底部坐标sorting
- 遍历y坐标，当你input一个矩形时，将它添加到集合中，当你离开一个矩形时，将它从集合中移除
- 每当该集合有多个矩形时，就会有重叠（如果您确保添加/删除具有相同顶部/底部坐标的所有矩形，则您正在查看的是多个重叠的矩形，这不会成为问题
对于上面的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)是重叠的面积。 这个例子可以很容易地推广到多个矩形。
对于每对连续的垂直扫描线，可以扩展上述解决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
