Что такое эффективный алгоритм для нахождения области перекрывающихся прямоугольников
Моя ситуация
- Вход: набор прямоугольников
- каждый прямоугольник состоит из 4 двойных типов: (x0,y0,x1,y1)
- они не "повернуты" ни под каким углом, все они являются "нормальными" прямоугольниками, которые идут "вверх / вниз" и "влево / вправо" относительно экрана
- они расположены случайным образом - они могут касаться краев, перекрываться или не иметь никакого контакта
- У меня будет несколько сотен прямоугольников
- это реализовано в C#
Мне нужно найти
- Область, которая образована их перекрытием - вся область холста, которую "покрывает" более одного прямоугольника (например, двумя прямоугольниками это будет пересечение)
- Мне не нужна геометрия перекрытия - только площадь (пример: 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 ответов
Эффективным способом вычисления этой области является использование алгоритма развертки. Предположим, что мы проходим вертикальную линию L(x) через объединение прямоугольников U:
- Прежде всего, вам нужно построить очередь событий Q, которая в данном случае представляет собой упорядоченный список всех x-координат (слева и справа) прямоугольников.
- во время развертки вы должны поддерживать одномерную структуру данных, которая должна давать вам общую длину пересечения L(x) и U. Важно то, что эта длина постоянна между двумя последовательными событиями q и q'Q. Так что, если l(q) обозначает общую длину L(q+) (т. е. L только на правой стороне q), пересекаемого с U, площадь, охватываемая L между событиями q и q', равна точно l(q)*(q' - д).
- вам просто нужно сложить все эти области, чтобы получить общую.
Нам еще предстоит решить проблему 1D. Вам нужна одномерная структура, которая динамически вычисляет объединение (вертикальных) сегментов. Под динамически я подразумеваю, что вы иногда добавляете новый сегмент, а иногда удаляете один.
Я уже подробно изложил в своем ответе на этот вопрос о том, как сделать это статическим образом (что на самом деле является 1D-разверткой). Поэтому, если вы хотите что-то простое, вы можете применить это непосредственно (пересчитав объединение для каждого события). Если вы хотите что-то более эффективное, вам просто нужно немного его адаптировать:
- предполагая, что вы знаете, объединение сегментов S1... Sn состоит из разъединяющих сегментов D1... Dk. Добавление Sn + 1 очень просто, вам просто нужно найти оба конца Sn + 1 среди концов D1... Dk.
- при условии, что вы знаете, что объединение сегментов S1... Sn состоит из разъединяющих сегментов D1... Dk, удаление сегмента Si (при условии, что Si был включен в Dj) означает пересчет объединения сегментов, в котором Dj состоял из, кроме Si (с использованием статического алгоритма).
Это ваш динамический алгоритм. Предполагая, что вы будете использовать отсортированные наборы с запросами местоположения во время регистрации для представления D1... Dk, это, вероятно, самый эффективный неспецифический метод, который вы можете получить.
Один из подходов состоит в том, чтобы построить его на холсте! Нарисуйте каждый прямоугольник, используя полупрозрачный цвет. Среда выполнения.NET будет рисовать в оптимизированном, собственном коде - или даже с использованием аппаратного ускорителя.
Затем вы должны перечитать пиксели. Является ли каждый пиксель цветом фона, цветом прямоугольника или другим цветом? Единственный способ, которым это может быть другим цветом, - это если два или более прямоугольника перекрываются...
Если это слишком много читов, я бы порекомендовал квад-дерево, как это сделал другой ответчик, или r-дерево.
Самое простое решение
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)
В этом примере мы создаем две нулевые матрицы размером с холст. Для каждого прямоугольника заполните одну из этих матриц теми, где прямоугольник занимает место. Затем сложите матрицы. Сейчас sum(A+B > 0) является областью союза, и sum(A+B > 1) это область перекрытия. Этот пример может легко обобщаться на несколько прямоугольников.
Это быстрый и грязный код, который я использовал в TopCoder SRM 160 Div 2.
т = верх
b = нижняя часть
л = слева
г = право
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 > R.r || R.l > r || R.b > t || b > R.t);
}
public Rect Intersection(Rect R)
{
if(!this.Intersects(R))
return new Rect(0,0,0,0);
int [] horiz = {l, r, R.l, R.r};
Array.Sort(horiz);
int [] vert = {b, t, R.b, R.t};
Array.Sort(vert);
return new Rect(horiz[1], vert[1], horiz[2], vert[2]);
}
public int Area()
{
return (t - b)*(r-l);
}
public override string ToString()
{
return l + " " + b + " " + r + " " + t;
}
}
Вот что-то, что вне моей головы звучит так, как будто это может сработать:
Создайте словарь с двойным ключом и списком прямоугольных + логических значений, например:
Словарь
Для каждого прямоугольника в вашем наборе найдите соответствующий список для значений x0 и x1 и добавьте прямоугольник в этот список с логическим значением true для x0 и false для x1. Таким образом, теперь у вас есть полный список всех x-координат, которые каждый прямоугольник либо вводит (true), либо оставляет (false) x-direction
Возьмите все ключи из этого словаря (все отдельные x-координаты), отсортируйте их и выполните цикл по ним в порядке, убедитесь, что вы можете получить как текущее значение x, так и следующее (вам нужны оба)). Это дает вам отдельные полосы прямоугольников
- Сохраняйте набор прямоугольников, которые вы сейчас просматриваете, которые начинаются пустыми. Для каждого значения x, которое вы повторяете в точке 3, если прямоугольник зарегистрирован с истинным значением, добавьте его в набор, в противном случае удалите его.
- Для полосы отсортируйте прямоугольники по их координате y
- Проходите по прямоугольникам в полосе, считая перекрывающиеся расстояния (пока неясно, как это сделать эффективно)
- Рассчитайте ширину полосы, умноженную на высоту перекрывающихся расстояний, чтобы получить области
Пример, 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-координат:
v v v v v v v v v
|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
Я полагаю, что вариант алгоритма сортировки + ввода / вывода для проверки сверху вниз также будет выполнимым:
- Сортируйте прямоугольники, которые мы сейчас анализируем в полосе сверху вниз, для прямоугольников с одинаковыми координатами сверху, а также сортируем их по нижней координате.
- итерируйте по y-координатам, и когда вы вводите прямоугольник, добавляете его в набор, когда вы покидаете прямоугольник, удаляете его из набора
- всякий раз, когда набор имеет более одного прямоугольника, у вас есть перекрытие (и если вы убедитесь, что добавляете / удаляете все прямоугольники, которые имеют ту же самую верхнюю / нижнюю координату, на которую вы сейчас смотрите, множественные перекрывающиеся прямоугольники не будут проблемой
Для вышеприведенной 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 - хранится у, и сложить эту разницу.
Надеюсь, это было понятно, и, как я уже сказал, это не в моей голове, ни в коем случае не проверено.
Вот код, который я написал для алгоритма развертки области:
#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;
}
Используя пример:
1 2 3 4 5 6
1 + --- + --- +
| |
2 + A + --- + --- +
| | Б |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + С +
| |
6 + --- + --- +
1) собрать все координаты х (как левые, так и правые) в список, затем отсортировать и удалить дубликаты
1 3 4 5 6
2) собрать все координаты y (как верхнюю, так и нижнюю) в список, затем отсортировать и удалить дубликаты
1 2 3 4 6
3) создать двумерный массив по количеству промежутков между уникальными координатами x * числу промежутков между уникальными координатами y.
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 на 2.
В этом вопросе прямоугольники описываются как четыре двойных. Двойные значения обычно содержат ошибки округления, и ошибка может заползти в вашу вычисленную область перекрытия. Если правовые координаты находятся в конечных точках, рассмотрите возможность использования целочисленного представления.
PS Использование аппаратного ускорителя, как в моем другом ответе, не такая уж и плохая идея, если разрешение приемлемо. Его также легко реализовать в гораздо меньшем количестве кода, чем описанный выше подход. Лошади на курсы.
Существует решение, указанное по ссылке http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html для определения общей площади нескольких прямоугольников, чтобы перекрывающаяся область учитывалась только один раз.,
Вышеупомянутое решение может быть расширено для вычисления только перекрытой области (и то же самое только один раз, даже если перекрытая область покрыта несколькими прямоугольниками) с горизонтальными линиями развертки для каждой пары последовательных вертикальных линий развертки.
Если цель состоит в том, чтобы просто определить общую площадь, покрытую всеми прямоугольниками, то горизонтальные линии развертки не требуются, и только объединение всех прямоугольников между двумя вертикальными линиями развертки даст область.
С другой стороны, если вы хотите вычислить только перекрывающуюся область, необходимы горизонтальные линии развертки, чтобы выяснить, сколько прямоугольников перекрывается между вертикальными (y1, y2) линиями развертки.
Вот рабочий код для решения, которое я реализовал на Java.
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 o.x == this.x && o.y == 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 && o.r.equals(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 o.l == this.l && o.u == 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.r.x;
}else{
x1 = rw1.r.x + rw1.r.dx;
}
if(rw2.start){
x2 = rw2.r.x;
}else{
x2 = rw2.r.x + 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.r.y;
}else{
y1 = rw1.r.y + rw1.r.dy;
}
if(rw2.start){
y2 = rw2.r.y;
}else{
y2 = rw2.r.y + 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].r.x : rws[i].r.x + rws[i].r.dx): (rws[i].start ? rws[i].r.y : rws[i].r.y + 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();
}
Вы можете немного упростить эту проблему, если разделите каждый прямоугольник на меньшие прямоугольники. Соберите все координаты X и Y всех прямоугольников, и они станут вашими точками разделения - если прямоугольник пересекает линию, разделите ее на две части. Когда вы закончите, у вас есть список прямоугольников, которые перекрывают или 0% или 100%, если вы сортируете их, должно быть легко найти идентичные.
Следующий ответ должен дать общую площадь только один раз. это приходит к предыдущим ответам, но теперь реализовано в C#. Он также работает с плавающей точкой (или двойной, если вам нужно [это не влияет на значения).
Кредиты: http://codercareer.blogspot.co.il/2011/12/no-27-area-of-rectangles.html
РЕДАКТИРОВАТЬ: ОП попросил перекрытия области - это, очевидно, очень просто:
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://stackru.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
Если ваши прямоугольники будут разреженными (в основном не пересекающимися), то, возможно, стоит взглянуть на рекурсивную размерную кластеризацию. В противном случае, кажется, что нужно использовать квад-дерево (как уже упоминалось другими авторами.
Это распространенная проблема обнаружения столкновений в компьютерных играх, поэтому нет недостатка в ресурсах, предлагающих способы ее решения.
Вот хороший пост в блоге с кратким описанием RCD.
Вот статья Dr.Dobbs, в которой обобщены различные алгоритмы обнаружения столкновений, которые подойдут.
Учитывая, что у нас есть два прямоугольника (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;
}
Сообщение от user3048546 содержит ошибку в логике по линиям 12-17. Вот рабочая реализация:
int rectoverlap (int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
int width, height, 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;
} else if (bx2>=ax2 && ax1>=bx1) {
width=ax2-ax1;
} else if (ax2>bx2) {
width=bx2-ax1;
} else {
width=ax2-bx1;
}
if (ay2>=by2 && by1>=ay1){
height=by2-by1;
} else if (by2>=ay2 && ay1>=by1) {
height=ay2-ay1;
} else if (ay2>by2) {
height=by2-ay1;
} else {
height=ay2-by1;
}
area = heigh*width;
return (area);
}
Я нашел другое решение, чем алгоритм развертки.
Поскольку все ваши прямоугольники размещены прямоугольными, горизонтальные и вертикальные линии прямоугольников будут образовывать прямоугольную неправильную сетку. Вы можете "нарисовать" прямоугольники на этой сетке; Это означает, что вы можете определить, какие поля сетки будут заполнены. Поскольку линии сетки формируются из границ данных прямоугольников, поле в этой сетке всегда будет либо полностью пустым, либо полностью заполненным прямоугольником.
Мне пришлось решить проблему в Java, так что вот мое решение: http://pastebin.com/03mss8yf
Эта функция вычисляет всю площадь, занимаемую прямоугольниками. Если вас интересует только "перекрывающаяся" часть, вы должны расширить блок кода между строками 70 и 72. Возможно, вы можете использовать второй набор для хранения полей сетки, которые используются более одного раза. Ваш код между строками 70 и 72 должен быть заменен на такой блок:
GridLocation gl = new GridLocation(curX, curY);
if(usedLocations.contains(gl) && usedLocations2.add(gl)) {
ret += width*height;
} else {
usedLocations.add(gl);
}
Здесь используется переменная usedLocations2 того же типа, что и usedLocations; он будет построен в той же точке.
Я не очень знаком с вычислениями сложности; поэтому я не знаю, какое из двух решений (развертка или мое сеточное решение) будет работать / масштабироваться лучше.
Вы можете найти перекрытие по осям x и y и умножить их.
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);
}