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

Question

Я работаю над проектом, в котором мне нужно создать границу вокруг группы прямоугольников.

Давайте использовать эту картинку как пример того, чего я хочу достичь.

РЕДАКТИРОВАТЬ: Не удалось заставить тег изображения работать должным образом, поэтому вот полная ссылка: http://www.flickr.com/photos/21093416@N04/3029621742/

У нас есть прямоугольники A и C, которые связаны специальным прямоугольником связи B. Это можно представить как два узла в графе (A, C) и ребро между ними (B). Это означает, что прямоугольники имеют указатели друг на друга следующим образом: A-> B, A <-B-> C, C-> B

Каждый прямоугольник имеет четыре вершины, хранящиеся в массиве, где индекс 0 находится внизу слева, а индекс 3 внизу справа.

Я хочу "пересечь" эту связанную структуру и вычислить вершины, составляющие границу (красную линию) вокруг нее. У меня уже есть несколько небольших идей о том, как этого добиться, но я хочу знать, есть ли у некоторых из вас более склонных к математике какие-то изящные хитрости в ваших рукавах.

Причина, по которой я публикую это здесь, заключается в том, что кто-то мог решить подобную проблему раньше, и у меня есть некоторые идеи, которые я мог бы использовать. Я не ожидал, что кто сесть и обдумать долго и упорно. Я собираюсь поработать над решением параллельно, ожидая ответов.

Любой вклад приветствуется.

Answer 1

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

   1   2   3   4   5   6

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

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

1 3 4 5 6

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

1 2 3 4 6

3) создать двумерный массив по количеству промежутков между уникальными координатами x * числу промежутков между уникальными координатами y. Он должен быть только один бит на ячейку, поэтому в c ++ вектор с вероятностью даст вам очень эффективную для памяти версию этого

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, для выполнения работы за вас!

Answer 2

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

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

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

Answer 3

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): прыгунья = 4
3. X координат упорядочено = 3,4,5,6, средние два - 4 и 5
   Y координаты упорядочены = 2,3,4,6, средние два - 3 и 4
   итак: (4,3) - (5,4): прыгунья = 4
4. 28 - 4 - 4 = 20

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

   1   2   3   4   5   6

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

Answer 4

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

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

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

Answer 5

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

Псевдокод:

 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)

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

Answer 6

Простой трюк должен быть:

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