Найти контур объединения выровненных по сетке квадратов

Question

Как получить координаты формы контура, сформированной с использованием меньших блоков сетки.

Например, если я использовал 32x32 единичных блоков для построения фигуры (любой фигуры). Тогда как я могу получить общие координаты фигуры, включая отрицательные пробелы.

Например: Можно расположить блоки так: (каждый блок имеет размер 32x32, а координаты относятся к левому нижнему углу блока)

Block 1 - (0,0)
BLock 2 - (32,0)
Block 3 - 64,0)
Block 4 - (64,32)
Block 5 - (64, 64)
BLock 6 - (32, 64)
BLock 6 - (0 64)
Block 7 - (0, 32)

Теперь вы можете видеть, что это создаст пустое пространство посередине.

Итак, я хотел бы знать, как получить координаты вышеуказанной фигуры так, чтобы я получил:

Main Block = (0,0), (96,0), (0,96)
Empty space = (32,32), (64,32), (64,64), (32,64)

Есть ли математическое решение для этого?

Со временем я буду делать сложные фигуры.

спасибо

******** Редактировать **** Привет,

Как бороться с этим условием?

<------------------^<----^
|                  ||    |
V------------------>|    |
<------^          /^|    |
|      |<------^ / ||    |
|      ||      |/  ||    |
V------>V------>V-->V---->

я бы хотел, чтобы результат был таким

<-------------------<----^
|                        |
V      ^----------->     |
|      |          /      |
|      <-------^ /       |
|              |/        |
V------>------->--->----->

Answer 1

Думайте о каждом квадрате как обводке, состоящей из четырех векторов, идущих в цепочке против часовой стрелки.

<-----^
|     |
|     |
V----->

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

Например, для двух соседних квадратов объединение составляет 8 векторов

<-----^<-----^
|     ||     |
|     ||     |
V----->V----->

, что уменьшает до 6 векторов, потому что два вертикальных вектора в середине отменяются:

<-----<-----^
|           |
|           |
V----->----->

Для приведенного вами примера результат будет (после отмены):

<-----<-----<-----^
|                 |
|                 |
V     ^----->     ^
|     |     |     |
|     |     |     |
V     <-----V     ^
|                 |
|                 |
V----->----->----->

Вам просто нужно соединить векторы в окончательном сокращенном объединении, чтобы считывать контуры контура. Обратите внимание, что внутренний контур («отверстие») проходит по часовой стрелке.

Answer 2

Вы, вероятно, должны сосредоточиться на Boolean Polygon Operations, профсоюзы в вашем случае. Существует множество работ, посвященных операциям с двумерным булевым многоугольником и конструктивной плоской геометрии, см. Википедию: http://en.wikipedia.org/wiki/Boolean_operations_on_polygons.