Вороной, который не пересекает границы

9

У меня есть несколько десятков точек, нанесенных по всей Великобритании. Каждая точка представляет собой объект, который обслуживает местных жителей. Чтобы оценить зоны охвата каждого объекта, я создал вокруг них полигоны Вороного и обрезал полигоны до границ Великобритании (используя шейп-файл Великобритании). Затем я раскрасил каждый многоугольник в соответствии с атрибутом точечных данных.

Обрезанная часть карты находится здесь: (Уэльс и Девон / Корнуолл) введите описание изображения здесь

Есть ли способ заставить Вороного уважать естественные границы Великобритании (т.е. ограничить их моим шейп-файлом во время создания Вороного)? Белое на моей карте - море, и некоторые полигоны пересекли Бристольский канал. Это неправдоподобно для водосбора.

Это возможно или есть альтернатива? До сих пор я использовал QGIS, но я открыт для любого варианта, кода или графического интерфейса, желательно бесплатного.

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

anotherfred
источник

Ответы:

5

Ключевыми словами являются диаграмма кратчайшего пути вороной , тесселяция вороной с ограничениями , соответствующая тесселяция или ограниченная тесселяция . CGAL может помочь вам объединить ограниченную триангуляцию с построением диаграммы Вороного . Вы также можете прочитать эту презентацию о « вороной диаграммах с препятствиями » из исследовательской группы UPC по дискретной, комбинаторной и вычислительной геометрии.

huckfinn
источник
Много читать там! Так что это кажется возможным. Спасибо
anotherfred
Да, это фантастический мир сложной компьютерной геометрии .
huckfinn