Voronoi que não cruzam fronteiras

9

Tenho várias dezenas de pontos traçados em todo o Reino Unido. Cada ponto representa uma instalação que serve a população local. Para estimar as áreas de captação de cada instalação, criei polígonos Voronoi em torno deles e prendi os polígonos nas fronteiras do Reino Unido (usando um arquivo de forma do Reino Unido). Em seguida, pintei cada polígono de acordo com um atributo dos dados do ponto.

Uma parte cortada do mapa está aqui: (País de Gales e Devon / Cornualha) insira a descrição da imagem aqui

Existe alguma maneira de fazer os Voronoi respeitarem as fronteiras naturais do Reino Unido (ou seja, limitá-las ao meu shapefile durante a criação dos Voronoi)? O branco no meu mapa é o mar, e alguns polígonos cruzaram o Canal de Bristol. Isso é implausível para uma área de captação.

Isso é possível ou existe alguma alternativa? Eu usei o QGIS até agora, mas estou aberto a qualquer opção, código ou GUI, de preferência gratuito.

Edit: Existem algumas perguntas: Construindo um diagrama de Voronoi usando uma métrica complicada de tempo de viagem e Existe um método GIS descrito para criar áreas de captação com base na distância de carro mais próxima? que falam sobre a construção de áreas de captação desde os tempos de condução. Essa é uma possibilidade que estou considerando se isso não for possível, mas um algoritmo de Voronoi que respeite as fronteiras seria mais simples.

outrofredo
fonte

Respostas:

5

As palavras-chave são diagrama de voronoi de caminho mais curto , mosaico de voronoi com restrições , mosaico em conformidade ou mosaico restrito . A CGAL pode ajudá-lo a combinar uma triangulação restrita com a construção do diagrama de voronoi . Você também pode ler esta apresentação sobre " diagramas de voronoi com obstáculos " do Grupo de Pesquisa UPC sobre Geometria Discreta, Combinatória e Computacional.

huckfinn
fonte
Muito para ler lá! Então parece possível. Obrigado
anotherfred
Sim, é o mundo fantástico de coisas complexas de geometria computacional .
huckfinn