Метод объединения плиточных квадратов, определенных как точки, в векторы

Question

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

Answer 1

Первое, о чем я могу подумать (вероятно, не самый эффективный способ):

1) Получите ограничивающую рамку всей плитки - от мин (х), мин (у) до макс (х), макс (у) для всех х и у ваших тайлов

2) Для каждой строки начните с STATE == EMPTY, итерируйте по каждому столбцу: STATE изменяется на FULL, когда вы нажимаете на квадрат, и на EMPTY, когда вы находите отверстие. Каждый раз, когда STATE переходит от ПУСТОГО к ПОЛНОМУ, сохраняйте левый сегмент линии этого квадрата, и каждый раз, когда СОСТОЯНИЕ переходит от ПОЛНОГО к ПУСТОЙ, сохраняйте правый отрезок этого квадрата.

3) Повторите выше по оси Y

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

Это будет работать для невыпуклых фигур, а также если у вас есть отверстия в плитке.