Проверить ближайшие прямоугольниками

Question

Описание

Пусть координаты 4 стороны прямоугольника, обозначенного (x1, y1), (x2, y2), (х3, у3) и (x4, y4). Как это Изображение-

И у меня есть набор координат 100000 прямоугольников, сохраненных в текстовом файле. Например здесь значения координат 16 прямоугольников, порожденных моей code-

#Rect x1  y1  x2  y2  x3  y3  x4  y4  area 

1  0.0000 0.0000 0.8147 0.0000 0.8147 0.1355 0.0000 0.1355 0.1104 
2  0.8147 0.0000 1.0000 0.0000 1.0000 0.1355 0.8147 0.1355 0.0251 
3  0.8147 0.1355 0.9058 0.1355 0.9058 0.8350 0.8147 0.8350 0.0637 
4  0.0000 0.1355 0.1270 0.1355 0.1270 0.9689 0.0000 0.9689 0.1058 
5  0.9058 0.1355 0.9134 0.1355 0.9134 0.2210 0.9058 0.2210 0.0006 
6  0.9058 0.8350 1.0000 0.8350 1.0000 1.0000 0.9058 1.0000 0.0155 
7  0.8147 0.8350 0.9058 0.8350 0.9058 1.0000 0.8147 1.0000 0.0150 
8  0.1270 0.1355 0.6324 0.1355 0.6324 0.3082 0.1270 0.3082 0.0873 
9  0.1270 0.9689 0.8147 0.9689 0.8147 1.0000 0.1270 1.0000 0.0214 
10 0.0000 0.9689 0.1270 0.9689 0.1270 1.0000 0.0000 1.0000 0.0040 
11 0.9134 0.1355 1.0000 0.1355 1.0000 0.2210 0.9134 0.2210 0.0074 
12 0.9134 0.2210 1.0000 0.2210 1.0000 0.8350 0.9134 0.8350 0.0532 
13 0.9058 0.2210 0.9134 0.2210 0.9134 0.8350 0.9058 0.8350 0.0047 
14 0.6324 0.1355 0.8147 0.1355 0.8147 0.3082 0.6324 0.3082 0.0315 
15 0.6324 0.3082 0.8147 0.3082 0.8147 0.9689 0.6324 0.9689 0.1205 
16 0.1270 0.3082 0.6324 0.3082 0.6324 0.9689 0.1270 0.9689 0.3339 

Этих координаты разбивает единичный квадрат на подразделы прямоугольников, как этот изображе-

Примеров Ближайших прямоугольников

На рисунке изображены ближайшие прямоугольники для прямоугольника № 3 - 9,15,14,1,2,5,13,6 и 7.

Для прямоугольника # 9 они - 10,4,16, 15,3 и 7.

Моя проблема

Теперь я хотел бы, чтобы вычислить число ближайших прямоугольников для каждого из прямоугольников, используя C/C++. Как мне это сделать?

Edit: На основе ответов

#include <iostream> 
#include <vector> 
#include <fstream> 

using namespace std; 


struct Rectangle { 
    double x1, y1; 
    double x2, y2; 
    double x3, y3; 
    double x4, y4; 
}; 




vector<double> get_touching_rectangles(Rectangle base, vector<Rectangle> rectangles) { 


    for (auto it = rectangles.begin(); it != rectangles.end(); it++) { 
     Rectangle other = *it; 
     if (base == other) { 
      continue; // This is our rectangle... skip it 
     } 
     // Top or bottom 
     if ((other.x2 >= base.x1 && other.x1 <= base.x2) && (other.y1 == base.y3 || other.y3 == base.y1)) { 
      ret.push_back(other); 
      continue; 
     } 
     // Left or right 
     if ((other.y3 >= base.y2 && other.y2 <= base.y3) && (other.x1 == base.x3 || other.x3 == base.x1)) { 
      ret.push_back(other); 
      continue; 
     } 
    } 
    return ret; 
} 

int main(int argc, char const *argv[]) 
{ 
vector<Rectangle> rectangles; 

//parse_txt_file(file, &rectangles); // Or whateer I need to do to parse that .txt file 
ifstream inputFile; 
inputFile.open("RectCoordinates.txt"); 

//std::vector<Rectangle> touching = 
get_touching_rectangles(rectangles.at(2) /* Rectangle #3 */, rectangles); 

inputFile.close(); 
    return 0; 
} 

Ok я пишу код выше на основе ответов. Но он показывает следующее сообщение об ошибке -

g++ -std=c++11 st5.cpp -o ssst5.cpp: In function ‘std::vector<double> get_touching_rectangles(Rectangle, std::vector<Rectangle>)’: 
    st5.cpp:23:21: error: no match for ‘operator==’ in ‘base == other’ 
    st5.cpp:23:21: note: candidates are: 
    In file included from /usr/include/c++/4.7/iosfwd:42:0, 
        from /usr/include/c++/4.7/ios:39, 
        from /usr/include/c++/4.7/ostream:40, 
        from /usr/include/c++/4.7/iostream:40, 
        from st5.cpp:1: 
    /usr/include/c++/4.7/bits/postypes.h:218:5: note: template<class _StateT> bool std::operator==(const std::fpos<_StateT>&, const std::fpos<_StateT>&) 
    /usr/include/c++/4.7/bits/postypes.h:218:5: note: template argument deduction/substitution failed: 

st5.cpp:28:13: error: ‘ret’ was not declared in this scope 
st5.cpp:33:13: error: ‘ret’ was not declared in this scope 
st5.cpp:37:12: error: ‘ret’ was not declared in this scope 

Что я делаю неправильно?

Answer 1

В вашем случае, каждый из ближайших прямоугольников должен разделять общую сторону или часть его (как и в случае прямоугольника 9 с прямоугольником. 3)

1. Рассмотрит, что и хочет узнать ближайшие прямоугольники для прямых.
2. Вы знаете (х, у) координаты его уголки
3. Вы знаете, что координаты изменяются вдоль краев
4. Для примера рассмотрим краевую A (x3, y3) до A (x4, y4)
5. Рассмотрим прямоугольник сказать B и проверить, если он соответствует любому из следующих критериев

в (х2, у2) между A (x3, y3) и а (x4, у4)
44445164106 (X3, y2) и B (x1, y1)
A (x4, y3) , у4) находится между B (x2, y2) и B (x1, y1)
Рассмотрен угловой (ы) B совпадает с направлением A

Край описываемой углами а (х3, у3) и A (x4, y4) является верхним краем прямоугольника A, и вы хотите увидеть, находится ли над ним прямоугольник B и, следовательно, рассмотрим ребро B, описываемое B (x1, y1) и B (x2, y2)

Некоторые из вышеперечисленных критериев перекрываются в некоторых случаях.

Сделайте то же самое для остальных сторон, соответствующих координатам углов. (Например, учитывая B (x1, y1) и B (x4, y4) при рассмотрении ребра A, описываемого A (x3, y2) и A (x2, y2))

Рассмотрите все прямоугольники. Считайте их и вуаля!

EDIT: Помните, что A является прямым. для которого вы хотите найти ближайших членов. B является прямым. для которого вы проверяете, удовлетворяет ли данный критерий заданным критериям.

Answer 2

Итак, в основном, что вы ищете, это найти прямоугольники, которые касаются прямоугольника, о котором идет речь? Если да, то я думаю, что-то вроде этого нужно сделать (я не проверял, хотя):

struct Rectangle { 
    int x1, y1; 
    int x2, y2; 
    int x3, y3; 
    int x4, y4; 
}; 

// This is why I hate C++ :/ 
bool operator==(const Rectangle& lhs, const Rectangle& rhs) { 
    return lhs.x1 == rhs.x1 && lhs.y1 == rhs.y1 && 
      lhs.x2 == rhs.x2 && lhs.y2 == rhs.y2 && 
      lhs.x3 == rhs.x3 && lhs.y3 == rhs.y3 && 
      lhs.x4 == rhs.x4 && lhs.y4 == rhs.y4; 
} 

// Returns all rectangles in `rectangles` that touch `base` 
std::vector<int> get_touching_rectangles(Rectangle base, 
     std::vector<Rectangle> rectangles) { 

    // Create the array that we will return, 
    // i.e. the touching rectangles 
    std::vector<Rectangle> ret; 

    // Iterate through each rectangle 
    for (auto it = rectangles.begin(); it != rectangles.end(); it++) { 
     Rectangle other = *it; 

     // If this (`other`) is our rectangle (`base`) 
     // i.e. the one we are trying to find rectangles that touch it, 
     // skip it 
     if (base == other) { 
      continue; 
     } 

     // If `other` touches the top or bottom sides of `base`, add it 
     if ((other.x2 >= base.x1 && other.x1 <= base.x2) && 
       (other.y1 == base.y3 || other.y3 == base.y1)) { 
      ret.push_back(other); 
      continue; 
     } 

     // If `other` touches the left or right sides of `base`, add it 
     if ((other.y3 >= base.y2 && other.y2 <= base.y3) && 
       (other.x1 == base.x3 || other.x3 == base.x1)) { 
      ret.push_back(other); 
      continue; 
     } 

    } 

    return ret; 
} 

И затем использовать его как это:

std::vector<Rectangle> rectangles; 
parse_txt_file(file, &rectangles); // Or whatever you do to parse that .txt file 
std::vector<Rectangle> touching = get_touching_rectangles(rectangles.at(2) /* Rectangle #3 */, rectangles); 

И тогда touching должен содержать, как вы сказали , прямоугольники 9, 15, 14, 1, 2, 5, 13, 6 и 7 (он вернет Rectangle, а не номер).

Answer 3

Инвертировать проблему. Когда вы создаете прямоугольники, поддерживайте множество J n-кортежей (где n изменяется от 2 до 4), которые обозначают «точки соединения», то есть угол, состоящий из 2, 3 или 4 прямоугольников. Для изображения выше {1,4} будет обозначаться (левый) угол прямоугольников 1 и 4, {1,4,8} - угол прямоугольников 1, 4 и 8. Для вашего изображения имеется 25 таких n-кортежей ,

Если вы хотите выполнить ближайший прямоугольный запрос для прямоугольника R, вам нужно найти все вхождения R в J, что легко, если вы упорядочиваете элементы J в классы эквивалентности на основе отношения «прямоугольник R» появляется в n -tuple 'и проиндексировать вектор с номером прямоугольника. Тогда поиск соседей R является O (1).

Answer 4

Скажем, ваш прямоугольник имеет координаты x и y как xleft, xright, ybottom, ytop.
Сортируйте прямоугольник и храните его отдельно в разных массивах.

• ybottomarray: Сортировка прямоугольников в порядке возрастания ybottom затем xleft.

• ytoparray: Сортировка в порядке возрастания ytop затем xleft.

• xleftarray: Сортировка по заказу xleft затем ytop.

• xrightarray: Сортировка по порядку из xright затем ytop.

Теперь перебрать каждый прямоугольник.

Шаг 1: Найдите количество соседних прямоугольников над ним, то есть прямоугольники, у которых ybottom равен ytop текущего прямоугольника.

• Двоичный поиск в ybottomarray найти первые и последние индексы которых ybottom равно ytop текущего прямоугольника. Скажем, диапазон составляет range_y.

• В range_y бинарного поиска индекса прямоугольника которого xleft является чуть менее xleft текущим прямоугольником сказать idx1. Это дает крайний левый прямоугольник над текущим прямоугольником.

• Снова бинарный поиск прямоугольника с наибольшим xleft значением, которое меньше или равно xright текущего прямоугольника say idx2. Это дает самый правый прямоугольник над текущим прямоугольником.

Таким образом, прямоугольники, лежащие от idx1 до idx2, находятся рядом с текущим прямоугольником над ним. Так idx2-idx1+1 даст прямоугольники над ним. Аналогичным образом найдите прямоугольники со всех четырех сторон.

Шаг 2: Найдите прямоугольники справа.
Шаг 3: Найдите прямоугольники внизу.
Шаг 4: Найдите прямоугольники слева.

Также необходимо, чтобы угловые шкафы обрабатывались тщательно, чтобы ни один прямоугольник не подсчитывался дважды, и ни один из них не учитывается.

Сложность

Этап сортировки имеют сложности О (Nlog п).
Каждый шаг в итерациях требует двух бинарных поиска для нахождения range_y и двоичного поиска для поиска idx1 и idx2 каждый. Итак, четыре бинарных поиска для каждого шага, и есть четыре шага. Таким образом, всего 16 двоичных поисков, которые составляют O (logn) сложности для каждой итерации.

Таким образом, для всех итераций сложность будет O (n logn).
Таким образом, общая сложность этого решения составляет O (n logn).