Главная » C++ » Союз прямоугольников в двумерном мире

Союз прямоугольников в двумерном мире

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

Обрабатывая ячейки в цикле for и используя свойство окрестности соседних ячеек, я мог бы удалить все внутренние ребра и сохранить остальные ребра.
Ребра хранятся в std :: vector;

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

Пожалуйста, помогите найти способ сделать это возможным.

2

Решение

Я думаю, что это простой алгоритм для достижения этой цели.

Считайте, что у нас есть это как вход:

 |   |   |   |   |   |
-+---+---+---+---+---+-
|   |   |   |   |   |
-+---+---+---+---+---+-
|   |   | a |   |   |
-+---+---+---+---+---+-
|   | b | c | d |   |
-+---+---+---+---+---+-
|   |   | e |   |   |
-+---+---+---+---+---+-
|   |   |   |   |   |

куда a, b, c, d, а также e хранятся ли наши входные тайлы как вектор пар (координаты):

std::vector<std::pair<unsigned,unsigned>> tiles;

То, что мы хотим, это:

 |   |   |   |   |   |
-+---+---+---+---+---+-
|   |   |   |   |   |
-+---+---*---*---+---+-
|   |   |   |   |   |
-+---*---*   *---*---+-
|   |           |   |
-+---*---*   *---*---+-
|   |   |   |   |   |
-+---+---*---*---+---+-
|   |   |   |   |   |

Алгоритм работает следующим образом:

  1. Создайте массив логических значений, охватывающих весь набор плиток. Вы должны пересечь набор, чтобы найти границы этого прямоугольника. Установите как истину позиции массива, которые представляют плитку набора, и как ложь в противном случае.
    Выход в примере будет (T true и е это false):

    +---+---+---+
| f | T | f |
+---+---+---+
| T | T | T |
+---+---+---+
| f | T | f ]
+---+---+---+

  2. Теперь вам нужно пересечь границу многоугольника корпуса. Начните с первого элемента, отмеченного как true в массиве флагов и перемещайте вершины в одном и том же направлении, пока не достигнете первой вершины, используя следующие правила:

    • Если две плитки перед текущим направлением / положением ложные, поверните по часовой стрелке и добавить вершину в список вывода (полигон):
      (* вершины добавлены в многоугольник, X текущая вершина, стрелка текущего направления)

      +---+---+---+
| f | f | f |
*---+---X---+ --->
| T | T | f |
*---+---+---+
| f | T | f ]
+---+---+---+

goes to

+---+---+---+
| f | f | f |  |
*---+---*---+  |
| T | T | f |  v
*---+---X---+
| f | T | f ]
+---+---+---+

    • Если одна плитка ложна, а другая — правда, двигайтесь в том же направлении (обратите внимание, что истина-ложь или ложь-истина означает, что вы находитесь в рамке):

      +---+---+---+
| f | f | f | |
*---+---*---+ |
| T | T | f | v
*---+---X---+
| f | T | f ]
+---+---+---+

goes to

+---+---+---+
| f | f | f |  |
*---+---*---+  |
| T | T | f |  v
*---+---+---+
| f | T | f ]
+---+---X---+

    • Если обе плитки верны, поверните против часовой стрелки и добавить вершину в список вывода (Обратите внимание, что true-true означает, что вы достигли части набора плиток, «стены»):

      +---+---+---+
| f | f | f | |
*---+---*---+ |
| T | T | f | v
*---+---X---+
| f | T | T ]
+---+---+---+

goes to

+---+---+---+
| f | f | f |
+---+---*---+
| T | T | f |  --->
+---+---*---X
| f | T | T ]
+---+---+---+

координаты тайлакарты против координат массива флагов

Массив flag представляет область прямоугольника карты тайлов, в которой размещены тайлы. Таким образом, tilemap-координаты его первого элемента (плитки) (left,top) где left минимальная x-координата выбранного набора плиток, и top минимальная y-координата выбранного набора плиток.

На втором шаге агорифма вы пересекаете границу (границу) набора плиток, используя массив в качестве ориентира. Обратите внимание, что вы действительно проходите через этот массив, поэтому Вы должны перевести координаты из флаг-координаты (логические координаты) в tilemap-координаты (физические координаты) хранить вершины многоугольника. Конечно, это просто.

Также обратите внимание, что алгоритм абстрактных шагов trasverse вершины ребер (физические координаты тайла), а не логические координаты. Вы должны быть уверены, что «Я в этой вершине» значит и что «Вперед» а также «очередь«означает в терминах координат массива флагов.

Граничные условия и проверка фасадной плитки

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

Например:

+---+---+---+
| f | f | f |  |
*---+---*---+  |
| T | T | f |  v
*---+---+---+
| f | T | f ]
+---+---X---+

идет к

+---+---+---+
| f | f | f |
*---+---*---+  <--
| T | T | f |
*---+---+---+
| f | T | f ]
+---X---*---+

точно так, как если бы это было так:

+---+---+---+
| f | f | f |  |
*---+---*---+  |
| T | T | f |  v
*---+---+---+
| f | T | f ]
+---+---X---+
| f | f | f |
*---*---*---+

Возможные оптимизации

Первый шаг вычисляет массив флагов, потому что алгоритм принимает набор плиток, выбранных в качестве вектора. Если ваш движок плиток поддерживает это, вы можете добавить свойство к плиткам (bool selected) и передать карту тайла напрямую, избегая вычисления и преобразования координат вершин.

Учитывая этот флаг-массив:

+---+---+---+
| T | f | f |
+---+---+---+
| T | T | T |
+---+---+---+
| f | T | T |
+---+---+---+

Исполнение работает следующим образом (Обратите внимание, что чертежи находятся в состоянии ПОСЛЕ выполнения шага):

  1. Найди первый true плитка. В этом случае (0,0), Поэтому мы начинаем с одной из ее вершин (например, нижней левой вершины, глядя вверх). Обратите внимание, что, поскольку она является первой истинной плиткой, вы можете использовать эту вершину, будучи уверенной, что она принадлежит многоугольнику. добавить эту первую вершину к многоугольнику):

    Current position: (0,1)
Polygon: {(0,1)}

+---+---+---+ ^
| T | f | f | |
X---+---+---+ |
| T | T | T |
+---+---+---+
| f | T | T |
+---+---+---+

  2. Начать траверс. В этом случае передние плитки false-true, так продвижение:

    Current position: (0,0)
Polygon: {(0,1)}

X---+---+---+ ^
| T | f | f | |
*---+---+---+ |
| T | T | T |
+---+---+---+
| f | T | T |
+---+---+---+

  3. Лицевая плитка false-false (Мы на границе), так поверните по часовой стрелке и добавьте вершину:

    Current position: (1,0)
Polygon: {(0,1),(0,0)}

*---X---+---+
| T | f | f |
*---+---+---+
| T | T | T | --->
+---+---+---+
| f | T | T |
+---+---+---+

  4. Теперь фасадные плитки false-false (Один из массива, а другой false). поверните по часовой стрелке и добавьте вершину:

    Current position: (1,1)
Polygon: {(0,1),(0,0),(1,0)}

*---*---+---+
| T | f | f | |
*---X---+---+ |
| T | T | T | v
+---+---+---+
| f | T | T |
+---+---+---+

  5. Две передние плитки true: Поверните против часовой стрелки и добавьте вершину:

    Current position: (1,2)
Polygon: {(0,1),(0,0),(1,0),(1,1)}

*---*---+---+
| T | f | f |
*---*---X---+
| T | T | T | --->
+---+---+---+
| f | T | T |
+---+---+---+

  6. Одна плитка false а другой true: авансировать:

    Current position: (1,3)
Polygon: {(0,1),(0,0),(1,0),(1,1)}

*---*---+---+
| T | f | f |
*---*---+---X
| T | T | T | --->
+---+---+---+
| f | T | T |
+---+---+---+

  7. Два false плитки (оба из массива): Поверните по часовой стрелке и добавьте вершину:

    Current position: (2,3)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1)}

*---*---+---+
| T | f | f | |
*---*---+---* |
| T | T | T | v
+---+---+---X
| f | T | T |
+---+---+---+

  8. Один true и один false(Вне массива): авансировать:

    Current position: (3,3)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1)}

*---*---+---+
| T | f | f | |
*---*---+---* |
| T | T | T | v
+---+---+---+
| f | T | T |
+---+---+---X

  9. Два false(Из массива) front-плитки: Поверните по часовой стрелке и добавьте вершину:

    Current position: (2,3)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3)}

*---*---+---+
| T | f | f |
*---*---+---*
| T | T | T | <---
+---+---+---+
| f | T | T |
+---+---X---*

  10. true-false (Один true и один за пределами): авансировать:

    Current position: (1,3)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3)}

*---*---+---+
| T | f | f |
*---*---+---*
| T | T | T | <---
+---+---+---+
| f | T | T |
+---X---+---*

  11. false-false (Один false и один за пределами): Поверните по часовой стрелке и добавьте вершину:

    Current position: (1,2)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3),(1,3)}

*---*---+---+
| T | f | f | ^
*---*---+---* |
| T | T | T | |
+---X---+---+
| f | T | T |
+---*---+---*

  12. true-true Фронт-плитка: Поверните против часовой стрелки и добавьте вершину:

    Current position: (0,2)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3),(1,3),(1,2)}

*---*---+---+
| T | f | f |
*---*---+---*
| T | T | T | <---
X---*---+---+
| f | T | T |
+---*---+---*

  13. false-false Фронт-плитка: Поверните по часовой стрелке и добавьте вершину:

    Current position: (0,1)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3),(1,3),(1,2),(0,2)}

*---*---+---+
| T | f | f | ^
X---*---+---* |
| T | T | T | |
*---*---+---+
| f | T | T |
+---*---+---*

  14. Текущая вершина является первой вершиной многоугольника: Исполнение закончено. Результат выглядит следующим образом:

    Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3),(1,3),(1,2),(0,2)}

*---*
|   |
*   *-------*
|           |
*---*       |
|       |
*-------*
2

Другие решения

Из-за тайлов это «особый случай» поиска граничного многоугольника. Я бы пошел с некоторым простым подходом.

Плитка (x, y) состоит из вершин [(x, y), (x + 1, y), (x + 1, y + 1), (x, y + 1)]. Вершина является частью граничного многоугольника, если она находится в 1, 2 или 3 тайлах. Чтобы найти вершины на границе, достаточно подсчитать количество плиток, в которых он находится. Для этого достаточно пройти через плитки и увеличить счетчик появления вершин для вершин тайла 4. Вершины с количеством плиток 1, 2 или 3 находятся на граничном многоугольнике.

Чтобы упорядочить вершины, достаточно начать с некоторой вершины на границе и искать соседнюю вершину, которая также находится на границе. Чтобы пересечь вершины в одном направлении, важно позаботиться о порядке направления соседних вершин для проверки. Например. если последняя вершина находится на -x, то порядок проверяемых направлений равен + y, + x, -y.

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

На данный момент у нас нет гарантии, что заказ по часовой стрелке. Это можно проверить, проверив (некоторые) самый верхний край (ы) по часовой стрелке. Если это не так, то обратный многоугольник.

0

Источник
Web-Answers © 2024 Наверх