diagramme Voronoi en utilisant la distance sur mesure (grand cercle)

Question

Je veux créer un diagramme Voronoi sur plusieurs paires de latitudes / longitudes, mais veulent utiliser la grande distance orthodromique entre eux, pas (inexactes) distance pythagoricienne.

Puis-je faire qhull / qvoronoi ou un autre programme Linux faire?

Je considérais la cartographie des points 3D, ayant qvoronoi créer une 3D diagramme Voronoi [1], et coupant le résultat avec la sphère unité, mais Je ne suis pas sûr que ce soit facile.

[1] je réalise la distance 3D entre deux latitudes / longitudes (le « À travers la Terre » chemin) n'est pas la même que la distance orthodromique, mais il est facile de prouver que cette transformation préserve par rapport distances, ce qui est tout ce qui importe pour un diagramme Voronoi.

Answer 1

Je suppose que vous avez trouvé cette article . De cela, il semble que vous avez la bonne idée en utilisant un plongement 3D. Votre question est alors de savoir comment intersecte le résultat avec la sphère.

Tout d'abord, vous devez considérer comment vous allez représenter le diagramme de Voronoï. Si vous voulez travailler en coordonnées lat / long dans un plan 2D, votre diagramme de Voronoï contiendra des bords courbes, alors peut-être il est préférable d'utiliser simplement une représentation 3D.

Si vous utilisez un programme comme qvoronoi, vous devriez en théorie seulement besoin des données Inifinite hyperplanes (générées par Fo). Cela vous donne l'équation du plan et les deux points, il correspond. En général, il vous suffit d'utiliser le diagramme de Voronoï pour tester l'inclusion dans les régions et les hyperplans devrait être suffisant pour cela.

Answer 2

Voir aussi cette question: algorithme pour calculer un diagramme Voronoi sur une sphère