Scafo convesso di (longitudine, latitudine) - punti sulla superficie di una sfera

Question

Gli algoritmi di convessità convessa standard non funzionano con (longitudine, latitudine) - punti, poiché gli algoritmi standard presuppongono che si desideri lo scafo di un insieme di punti cartesiani. I punti di latitudine-longitudine sono non cartesiano, perché la longitudine "avvolge" l'anti-meridiano (+/- 180 gradi). Ad esempio, due gradi est della longitudine 179 sono -179.

Quindi, se il tuo set di punti avviene a cavallo dell'anti-meridiano, calcolerai scafi spuri che si estendono in tutto il mondo in modo errato.

Eventuali suggerimenti per i trucchi Potrei applicare con un algoritmo di scafo convesso standard per correggere questo, o puntatori a appropriati algoritmi di scafo "geosferici"?

Ora che ci penso, ci sono casi più interessanti da considerare che a cavallo dell'anti-merdiano. Considera una "banda" di punti che circondano la terra - il suo scafo convesso non avrebbe limiti est/ovest. O ancora di più, qual è lo scafo convesso di {(0,0), (0, 90), (0, -90), (90, 0), (-90, 0), (180, 0)}? - Sembrerebbe contenere l'intera superficie della terra, quindi quali punti sono sul suo perimetro?

Answer 1

algoritmi convesso standard non sono sconfitti dalla confezione -la combinazione delle coordinate sulla superficie della Terra ma da un problema più fondamentale. La superficie di una sfera (dimentichiamo la non-abbastanza-sfericità della Terra) non è uno spazio euclideo, quindi la geometria euclidea non funziona e le routine di carena convesse che presuppongono che lo spazio sottostante sia euclideo (mostratene uno che non lo fa) t, per favore) non funzionerà.

La superficie della sfera è conforme ai concetti di uno elliptic geometry in cui le linee sono grandi cerchi e i punti antipodali sono considerati lo stesso punto. Hai già iniziato a sperimentare i problemi derivanti dal tentativo di applicare un concetto euclideo di convessità a uno spazio ellittico.

Un approccio aperto a voi sarebbe quello di adottare le definizioni di geodesic convexity e implementare una routine dello scafo convesso geodetico. Sembra piuttosto peloso. E potrebbe non produrre risultati conformi alle vostre aspettative (generalmente euclidee). In molti casi, per 3 punti arbitrari, lo scafo convesso risulta essere l'intera superficie della sfera.

Un altro approccio, quello adottato dai navigatori e dai cartografi nel corso dei secoli, sarebbe quello di proiettare parte della superficie della sfera (una parte contenente tutti i punti) nello spazio euclideo (che è il soggetto delle proiezioni cartografiche e ho vinto Ti infastidiscono con riferimenti alla vasta letteratura su di esso) e per capire lo scafo convesso dei punti proiettati. Proietta l'area che ti interessa sul piano e regola le coordinate in modo che non si avvolgano; per esempio, se fossi interessato in Francia potresti aggiustare tutte le longitudini aggiungendo 30 gradi in modo che l'intero paese fosse coordinato da + ve numeri.

Mentre sto scrivendo, l'idea proposta nella risposta di @ Li-aung Yip, sull'uso di un algoritmo di scafo convesso 3D, mi sembra sbagliata.Lo scafo convesso 3D dell'insieme di punti superficie includerà punti, bordi e facce che si trovano all'interno della sfera. Questi letteralmente non esistono sulla superficie bidimensionale della sfera e cambiano solo le tue difficoltà dal wrestling con il concetto non proprio corretto in 2D al completamente sbagliato in 3D. Inoltre, ho appreso dall'articolo di Wikipedia che ho riferito che un emisfero chiuso (cioè uno che include il suo 'equatore') non è convesso nella geometria della superficie della sfera.

Answer 2

Invece di considerare i dati come dati di latitudine-longitudine, puoi invece considerarlo nello spazio 3D e applicare uno 3D convex hull algorithm? Potresti essere in grado di trovare lo scafo convesso 2D che desideri analizzando lo scafo convesso 3D.

Questo restituisce algoritmi ben studiati per scafi convessi cartesiani (anche se in tre dimensioni) e non presenta problemi con il riepilogo delle coordinate.

In alternativa, c'è questa carta: Computing the Convex Hull of a Simple Polygon on the Sphere (1996) che sembra a che fare con alcuni degli stessi problemi che hai a che fare con (coordinate avvolgente, etc.)

Answer 3

Se tutti i punti sono all'interno di un emisfero (cioè, se riesci a trovare un piano di taglio attraverso il centro della Terra che li mette tutti da un lato), allora puoi eseguire una proiezione gnomonica alias gnomica centrale da il centro della Terra a un piano parallelo al piano di taglio. Quindi tutti i grandi cerchi diventano linee rette nella proiezione, e quindi uno scafo convesso nella proiezione eseguirà il mapping su uno scafo convesso corretto sulla Terra. Puoi vedere come sono errati i punti di lat/lon guardando le linee di latitudine nella sezione "Gnomonic Projection" here (nota che le linee di longitudine rimangono diritte).

(Trattare la Terra come una sfera non è ancora perfettamente ragione, ma è una buona seconda approssimazione. Non credo che punti su un vero e proprio percorso di distanza attraverso una Terra più realistico (diciamo WGS84) generalmente si trovano sulla . un piano attraverso il centro Forse facendo finta che fanno ti dà una migliore approssimazione di quello che si ottiene con una sfera)

Answer 4

FutureNerd:.

Lei ha assolutamente ragione. Ho dovuto risolvere esattamente lo stesso problema di Maxy-B per la mia applicazione. Come prima iterazione, ho appena trattato (lng, lat) come (x, y) e ho eseguito un algoritmo 2D standard. Questo ha funzionato bene finché nessuno sembrava troppo vicino, perché tutti i miei dati erano negli Stati Uniti contigui. Come seconda iterazione, però, ho usato il tuo approccio e dimostrato il concetto.

I punti DEVONO essere nello stesso emisfero. A quanto pare, scegliere questo emisfero non è banale (non è solo il centro dei punti, come avevo inizialmente intuito.) Per illustrare, considera i seguenti quattro punti: (0,0), (-60,0), (+60,0) lungo l'equatore e (0,90) il polo nord. Comunque tu scegli di definire "centro", il loro centro si trova sul polo nord per simmetria e tutti e quattro i punti sono nell'emisfero settentrionale. Tuttavia, considera di sostituire il quarto punto con, per esempio (-19, 64) islanda. Ora il loro centro NON è sul polo nord, ma è attratto asimmetricamente verso l'Islanda. Tuttavia, tutti e quattro i punti sono ancora nell'emisfero settentrionale. Inoltre, l'emisfero settentrionale, come definito in modo univoco dal Polo Nord, è l'UNICO emisfero che condividono. Quindi il calcolo di questo "polo" diventa algoritmico, non algebrico.

Vedi il mio repository per il codice Python: https://github.com/VictorDavis/GeoConvexHull