Esiste un algoritmo efficiente per generare uno scafo concavo 2D?
https://stackoverflow.com/questions/83593
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Avendo una serie di punti (2D) da un file GIS (una mappa della città), devo generare il poligono che definisce il "contorno" per quella mappa (il suo confine).I suoi parametri di input sarebbero i punti impostati e una "lunghezza massima del bordo".Verrebbe quindi restituito il poligono corrispondente (probabilmente non convesso).
La soluzione migliore che ho trovato finora è stata generare i triangoli di Delaunay e quindi rimuovere i bordi esterni più lunghi della lunghezza massima del bordo.Dopo che tutti i bordi esterni sono più corti, rimuovo semplicemente i bordi interni e ottengo il poligono che desidero.Il problema è che richiede molto tempo e mi chiedo se esiste un modo migliore.
Altri suggerimenti
Uno degli ex studenti del nostro laboratorio ha utilizzato alcune tecniche applicabili per la sua tesi di dottorato.Credo che uno di questi si chiami "forme alfa" e viene citato nel seguente articolo:
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
Quel documento fornisce alcuni ulteriori riferimenti che puoi seguire.
I ragazzi Qui affermano di aver sviluppato un approccio k vicini più vicini per determinare l'involucro concavo di un insieme di punti che si comporta "quasi linearmente sul numero di punti".Purtroppo il loro documento sembra essere molto ben custodito e dovrai chiedere loro per questo.
Ecco un buona serie di referenze che include quanto sopra e potrebbe portarti a trovare un approccio migliore.
La risposta potrebbe essere ancora interessante per qualcun altro:Si può applicare a variazione dell'algoritmo del quadrato in marcia, applicato (1) all'interno dello scafo concavo e (2) poi su (ad es.3) diverso bilancia che il mio dipende dalla densità media dei punti.Le scale devono essere multiple l'una dell'altra, in modo da creare una griglia che è possibile utilizzare per un campionamento efficiente.Ciò consente di trovare rapidamente campioni=quadrati vuoti, campioni che si trovano completamente all'interno di un "cluster/nuvola" di punti e quelli che si trovano nel mezzo.Quest'ultima categoria può quindi essere utilizzata per determinare facilmente la polilinea che rappresenta una parte dello scafo concavo.
Tutto è lineare in questo approccio, non è necessaria alcuna triangolazione, non utilizza forme alfa ed è diverso dall'offerta commerciale/brevettata come descritta qui ( http://www.concavehull.com/ )
Una soluzione semplice è camminare attorno al bordo del poligono.Dato un bordo attuale del confine che collega i punti P0 e P1, il punto successivo sul confine P2 sarà il punto con il più piccolo A possibile, dove
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
Poi ti prepari
P0 <- P1
P1 <- P2
e ripeti finché non torni al punto di partenza.
Questo è ancora O(N^2), quindi ti consigliamo di ordinare un po' la tua lista di punti.Puoi limitare l'insieme di punti da considerare ad ogni iterazione se ordini i punti, ad esempio, in base alla loro direzione rispetto al baricentro della città.
Buona domanda!Non l'ho provato affatto, ma il mio primo tentativo sarebbe questo metodo iterativo:
- Crea un set N ("non contenuto") e aggiungi tutti i punti nel tuo set a N.
- Scegli 3 punti da N a caso per formare un poligono iniziale P.Toglieteli da N.
- Utilizzo qualche algoritmo punto nel poligono e osserva i punti in N.Per ogni punto di N, se ora è contenuto da P, rimuovilo da N.Non appena trovi un punto in N che non è ancora contenuto in P, vai al passo 4.Se N diventa vuoto, il gioco è fatto.
- Chiama il punto che hai trovato A.Trova la linea in P più vicina ad A e aggiungi A al centro.
- Torna al passaggio 3
Penso che funzionerebbe fintanto che funziona abbastanza bene: una buona euristica per i tuoi 3 punti iniziali potrebbe aiutare.
Buona fortuna!
Puoi farlo in QGIS con questo plug-in;https://github.com/detlevn/QGIS-ConcaveHull-Plugin
A seconda di come ti serve per interagire con i tuoi dati, probabilmente vale la pena controllare come è stato fatto qui.
L'SDK interattivo di Bing Maps V8 dispone di un'opzione di scafo concavo nelle operazioni di forma avanzate.
All'interno di ArcGIS 10.5.1, l'estensione 3D Analyst dispone di uno strumento Volume limite minimo con i tipi di geometria scafo concavo, sfera, involucro o scafo convesso.Può essere utilizzato a qualsiasi livello di licenza.
C'è un algoritmo dello scafo concavo qui: https://github.com/mapbox/concaveman
Una soluzione rapida e approssimativa (utile anche per scafi convessi) è trovare i limiti nord e sud per ogni piccolo elemento est-ovest.
In base alla quantità di dettagli che desideri, crea una matrice di dimensioni fisse di limiti superiori/inferiori.Per ciascun punto calcolare in quale colonna E-W si trova e quindi aggiornare i limiti superiore/inferiore per quella colonna.Dopo aver elaborato tutti i punti è possibile interpolare i punti superiore/inferiore per le colonne mancate.
Vale anche la pena fare un rapido controllo in anticipo per forme molto lunghe e sottili e decidere se inserire NS o Ew.
Come riferimento ampiamente adottato, PostGIS inizia con uno scafo convesso e poi lo sprofonda, puoi vederlo qui.
