Добавить квадрат в многоугольник, состоящий из квадратов

Question

У меня есть коллекция из 1 * 1 полигонов, каждый из которых определяется своей границей (набор из четырех точек), и я использую функцию area () ниже в моем примере кода, чтобы создать эти , Я хочу объединить такие смежные квадраты в один многоугольник, причем этот многоугольник также определяется в терминах его граничных точек.

Я хочу сделать это методом грубой силы, где я начну с добавления двух смежных квадратов 1 * 1, чтобы создать больший многоугольник, используя функцию join () ниже, и продолжу таким образом, чтобы вырастить многоугольник. Итак, первый аргумент объединения - это пока полигон, а второй аргумент - это квадрат 1 * 1, который я хочу добавить к многоугольнику. Возвращаемое значение является границей нового многоугольника, current , соединенного с новым 1 * 1.

Вот что я получил до сих пор:

def join(current, new):
    """ current is the polygon, new the 1*1 square being added to it"""
    return get_non_touching_part_of_boundary(current, new)  + get_non_touching_part_of_boundary(new, current)

def get_non_touching_part_of_boundary(this, other):
    for i,point in enumerate(this):
        if point not in other and this[i-1] in other:
            break # start of non touching boundary from a clockwise perspective
    non_touching_part_of_boundary = []
    for point in this[i:] + this[:i]:
        if not point in other:
            non_touching_part_of_boundary.append(point)
    return non_touching_part_of_boundary    

def area(point):
    """ boundary defined in a clockwise fashion """
    return [point,(point[0],point[1]+1),(point[0]+1,point[1]+1),(point[0]+1,point[1])]

a = area((0,1))            # a assigned a 1*1 polygon
a = join(a, area((0,2)))   # a assigned a 2*1 polygon
a = join(a, area((1,2)))    
a = join(a, area((2,2)))    
a = join(a, area((2,1)))    
a = join(a, area((2,0)))    

print(a)

Это дает мне следующую форму многоугольника (с числами, представляющими порядок, в котором добавляются ее составные квадраты):

234
1 5
  6

Вывод кода, приведенного выше, дает:

[(2, 2), (1, 2), (1, 1), (0, 1), (0, 3), (3, 3), (3, 0), (2, 0)]

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

Но если я добавлю еще один квадрат к этой форме через a = join (a, area ((1,0))) и, тем самым, создав дыру, мой алгоритм распадется на части:

234
1 5
 76

Вот еще один многоугольник, который не может обработать мой алгоритм:

123
 64
  5

Кто-нибудь может мне помочь? Я хотел бы, чтобы отверстия в многоугольнике были перечислены в отдельном списке.

Спасибо!

Answer 1

Я думаю, что ваш алгоритм трудно исправить. Учтите, что, например, добавление одного квадрата к многоугольнику может создать несколько отверстий:

  xxx
  x x
xxx xxx
x  y  x
xxx xxx
  x x
  xxx

представьте, например, что все x являются "текущим многоугольником", и вы затем andd y ...

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

1. цикл на каждом квадрате и для каждого:
2. если квадрат находится внутри, а квадрат слева отсутствует (или наоборот), то вы знаете, что вам нужна стена слева
3. если квадрат находится внутри, а квадрат выше отсутствует (или наоборот), то вы знаете, что вам нужна стена выше
4. собрать все ребра в словаре, где для каждой пары координат вы ведете список всех стен, начинающихся или доходящих до этого ребра
5. как только сканирование завершено, вы можете перестроить получившиеся петли, начав с любой стены и продолжая следовать цепочке, пока не вернетесь к начальной точке ... в случае, если при достижении точки есть несколько вариантов выбора, из которых стена, которую можно использовать для продолжения прогулки, затем выберите любую из них.

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

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

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

EDIT

Следующее изображение является результатом полной реализации этого алгоритма , включающего логику правого поворота во время сбора циклов, чтобы избежать самопересекающихся циклов. Различные цвета были назначены выходным полигонам, а углы обрезаны, чтобы сделать повороты очевидными.