Voronoi schema utilizzando personalizzato (cerchio) distanza

Question

Voglio creare un diagramma di Voronoi su diverse coppie di latitudini / longitudini, ma si desidera utilizzare la distanza ortodromica tra di loro, non il (imprecisa) pitagorico distanza.

Posso fare Qhull / qvoronoi o qualche altro programma Linux fare questo?

I considerata la mappatura dei punti al 3D, avendo qvoronoi creare un 3D diagramma di Voronoi [1], ed intersecante il risultato con sfera unitaria, ma Io non sono sicuro che è facile.

[1] mi rendo conto la distanza 3D tra due latitudini / longitudini (la "Attraverso la Terra" percorso) non è la stessa della distanza ortodromica, ma è facile dimostrare che questa trasformazione conserva relativa distanze, che è tutto ciò che conta per un diagramma di Voronoi.

Answer 1

presumo che hai trovato questo articolo . Da questo, sembra che si ha l'idea giusta utilizzando un incorporamento 3D. La tua domanda è quindi come si intersecano il risultato con la sfera.

Prima di tutto è necessario considerare come si sta andando a rappresentare il diagramma di Voronoi. Se si vuole lavorare in Lat Long coordinate / in un piano 2D, allora il vostro diagramma di Voronoi conterrà bordi curvi, quindi forse è meglio utilizzare solo una rappresentazione 3D.

Se si utilizza un programma come qvoronoi, si dovrebbe in teoria solo bisogno i dati iperpiani Inifinite (generati da Fo). Questo vi dà l'equazione del piano e i due punti corrisponde. Di solito solo è necessario utilizzare il diagramma di Voronoi per verificare l'inclusione all'interno delle regioni, e gli iperpiani dovrebbe essere abbastanza per questo.

Answer 2

Si veda anche questa domanda: Algoritmo per il calcolo di un diagramma di Voronoi su una sfera?