Существует ли реализация геодезической диаграммы Вороного в простом многоугольнике, который можно использовать в Python? ⇐ Python

[Anonymous]

Как следует из названия, я пытаюсь найти реализацию геодезической диаграммы Вороного в простом многоугольнике. В идеале его можно было бы использовать из Python. Иногда ее называют диаграммой кратчайшего пути Вороного.
Это диаграмма Вороного, состоящая из точек, содержащихся внутри невыпуклого ограничивающего многоугольника, где кратчайшие пути, определяющие ячейки Вороного, ограничены тем, что они находятся внутри многоугольника. Обратите внимание, что это не то же самое, что просто обрезать стандартную диаграмму Вороного с помощью ограничивающего многоугольника — ячейки генерируются внутри двумерного многоугольника.
Это простая иллюстрация стандартной диаграммы Вороного, обрезанной до ограничивающего многоугольника:


А это простая иллюстрация геодезической диарамы Вороного, созданной внутри многоугольника:


Я нашел четыре статьи, в которых описывается это и некоторые алгоритмы для его достижения:

• Аронов, Б. (1987). О геодезической диаграмме Вороного точечных площадок в простом многоугольнике.
• Гут Н. и Клингель П. (2012). Распределение спроса при моделировании сетей водоснабжения – подход на основе ГИС с использованием диаграмм Вороного с ограничениями.
• Лю, К.-Х. (2019). Почти оптимальный алгоритм для геодезической диаграммы Вороного точек в простом многоугольнике.
• О, Э. (2019). Оптимальный алгоритм для геодезических диаграмм Вороного ближайшей точки в простых многоугольниках.

Я также нашел видео, которое описывает его, где точки также движутся внутри многоугольника:

• Кинетические геодезические диаграммы Вороного в простом многоугольнике

В идеале любая реализация может быть использована на Python, но любая для начала были бы признательны за реализацию вообще.
Большое спасибо.

Подробнее здесь: https://stackoverflow.com/questions/719 ... -polygon-u