Расчет границы вокруг нескольких связанных прямоугольников

Простая уловка должна быть такой:

1. Создайте область из первого прямоугольника
2. Добавьте другие прямоугольники в область
3. Получить границу региона (как-нибудь?: P)

Поразмыслив, я могу сделать что-то вроде этого:

Псевдокод:

 LinkRectsConnectedTo(Rectangle rectangle,Edge startEdge) // Edge can be West,North,East,South 
    for each edge in rectangle starting with the edge facing last rectangle
       add vertices in the edge to the final boundary polygon
       if edge is connected to another rectangle
          if edge not equals startEdge
             recursively call LinkRectsConnectedTo(rectangle,startEdge)

Очевидно, этот псевдокод придется немного доработать, и он может не охватывать все случаи, но я думаю, что мог бы решить свою проблему.

Я не обдумал это полностью, но мне интересно, не могли бы вы сделать что-то вроде:

• Составьте список всех краев.
• Получите все ребра, где P1.X = P2.X
• В этом списке найдите пары, в которых X равны
• Для каждой пары замените одну или две кромки частей, где они НЕ перекрываются.
• Сделайте что-нибудь умное, чтобы расположить края в правильном порядке

Будут ли ваши прямоугольники всегда выровнены по горизонтали, если нет, вам нужно будет сделать то же самое, но и для Y? И всегда ли они будут трогательными? В противном случае алгоритм не был бы нарушен, но «правильный порядок» не был бы определен.

1. Вычислить сумму границ всех трех прямоугольников по отдельности.
2. вычислить перекрывающийся прямоугольник A и B и вычесть его из суммы
3. Сделайте то же самое для перекрывающегося прямоугольника B и C.

(чтобы получить перекрывающийся прямоугольник из A и B, займите 2 средние позиции X вместе со средними 2 положениями Y)

Пример (x1, y1) - (x2, y2):

• Прямоугольник A: (1,1) - (3,4)
• Прямоугольник B: (3,2) - (5,4)
• Прямоугольник C: (4,3) - (6,6)

Расчет:

1. 10 + 8 + 10 = 28
2. Координаты X заказаны = 1,3,3,5, две средние - 3 и 3
   . Заказанные координаты Y = 1,2,4,4, две средние - 2 и 4
   . так: (3,2) - (3,4): boundery = 4
3. Заказанные координаты X = 3,4,5,6, две средние - 4 и 5
   . Заказанные координаты Y = 2,3,4,6, две средние - 3 и 4
   . так: (4,3) - (5,4): boundery = 4
4. 28 - 4 - 4 = 20

Это мой визуализированный пример:

   1   2   3   4   5   6

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

Обобщенное решение этой проблемы - реализовать логические операции в терминах строки развертки. Вы можете найти краткое обсуждение здесь, чтобы начать работу. Из текста:

«Основа логических алгоритмов - строки развертки. По основным принципам очень хороша книга: Вычислительная геометрия - введение Франко П. Препарата и Майкла Яна Шамоса».

У меня есть эта книга, хотя сейчас она находится в офисе, поэтому я не могу найти номера страниц, которые вам следует прочитать, хотя глава 8 о геометрии прямоугольников, вероятно, является лучшей отправной точкой.

Используя пример, где прямоугольники перпендикулярны друг другу и поэтому могут быть представлены четырьмя значениями (двумя координатами x и двумя координатами y):

   1   2   3   4   5   6

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

1) собрать все координаты x (как слева, так и справа) в список, затем отсортировать его и удалить дубликаты

1 3 4 5 6

2) соберите все координаты y (как верхние, так и нижние) в список, затем отсортируйте его и удалите дубликаты

1 2 3 4 6

3) создать 2D-массив по количеству промежутков между уникальными координатами x * количеству промежутков между уникальными координатами y. Это должен быть только один бит на ячейку, поэтому в С ++ вектор <bool>, вероятно, даст вам очень эффективную с точки зрения памяти версию этого

4 * 4

4) закрасьте все прямоугольники в эту сетку

   1   3   4   5   6

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

5) для каждой ячейки в сетке, для каждого края, если ячейка рядом с ней в этом кардинальном направлении не закрашена, проведите граничную линию для этого края.

В вопросе прямоугольники описываются как четыре вектора, каждый из которых представляет собой угол. Если каждый прямоугольник может вращаться произвольно и отличаться от других, то описанный выше подход не будет работать. Проблема поиска пути вокруг сложного многоугольника регулярно решается растеризаторами векторной графики, и хороший подход к решению проблемы - использование библиотеки, такой как Cairo, которая сделает всю работу за вас!