Существует ли эффективный способ хранения монотонных многоугольников после разделения основного многоугольника по диагон ⇐ Python

[Anonymous]

(https://i.sstatic.net/rUIgPAlk.png)
Я работаю над задачей триангуляции простого многоугольника (у которого нет пересекающихся ребер друг друга), шаг которого включает в себя разложение всего многоугольника на монотонные многоугольники (многоугольник, который пересекается не более двух раз с нарисованной на нем горизонтальной или вертикальной линией).
Мой алгоритм разложения работает с набором ребер многоугольника и приводит к диагональным ребрам в формате:

Код: Выделить всё

diagonals = [
{'source': {'X': -2.5, 'Y': 7.8}, 'end': {'X': -5.6, 'Y': 13.6}},
{'source': {'X': 8.9, 'Y': 5.5}, 'end': {'X': 8.3, 'Y': 10.9}},
{'source': {'X': -5.5, 'Y': 0.9}, 'end': {'X': -5.6, 'Y': 13.6}},
{'source': {'X': 4.4, 'Y': -3.8}, 'end': {'X': 8.3, 'Y': 10.9}},
{'source': {'X': 4.0, 'Y': 1.9}, 'end': {'X': 1.9, 'Y': -7.7}},
{'source': {'X': 4.4, 'Y': -3.8}, 'end': {'X': 4.0, 'Y': 1.9}}
]

Формат краев (с учетом тестового примера изображения) следующий:

Код: Выделить всё

edges =
[
[{'X': -6.8, 'Y': 4.1}, {'X': -9.1, 'Y': 1.6}], [{'X': -9.1, 'Y': 1.6}, {'X': -8.7, 'Y': -3.9}], [{'X': -8.7, 'Y': -3.9}, {'X': -5.5, 'Y': 0.9}], [{'X': -5.5, 'Y': 0.9}, {'X': -6.4, 'Y': -6.5}], [{'X': -6.4, 'Y': -6.5}, {'X': -3.4, 'Y': -11.7}], [{'X': -3.4, 'Y': -11.7}, {'X': -2.5, 'Y': 7.8}], [{'X': -2.5, 'Y': 7.8}, {'X': 1.9, 'Y': -7.7}], [{'X': 1.9, 'Y': -7.7}, {'X': 4.4, 'Y': -3.8}], [{'X': 4.4, 'Y': -3.8}, {'X': 6.7, 'Y': -11.7}], [{'X': 6.7, 'Y': -11.7}, {'X': 8.9, 'Y': 5.5}], [{'X': 8.9, 'Y': 5.5}, {'X': 12.9, 'Y': 2.9}], [{'X': 12.9, 'Y': 2.9}, {'X': 12.5, 'Y': 8.1}], [{'X': 12.5, 'Y': 8.1}, {'X': 8.3, 'Y': 10.9}], [{'X': 8.3, 'Y': 10.9}, {'X': 4.0, 'Y': 1.9}], [{'X': 4.0, 'Y': 1.9}, {'X': -1.1, 'Y': 12.6}], [{'X': -1.1, 'Y': 12.6}, {'X': -5.6, 'Y': 13.6}], [{'X': -5.6, 'Y': 13.6}, {'X': -9.3, 'Y': 9.3}], [{'X': -9.3, 'Y': 9.3}, {'X': -6.8, 'Y': 4.1}]
]

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

Код: Выделить всё

[
{'sub-polygon1': [{'X': value, 'Y': value}, {'X': value, 'Y': value}, {'X': value, 'Y': value}, ..]},
{'sub-polygon2': [{'X': value, 'Y': value}, {'X': value, 'Y': value}, {'X': value, 'Y': value}, ..]},
.
.
.
.
]

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

Подробнее здесь: https://stackoverflow.com/questions/790 ... the-main-p