Domanda

Io ho 1 poligono rosso dire e 50 poligoni blu posizionati casualmente - sono situati in aree geografiche Spazio 2D.Qual è l'algoritmo più rapido/veloce per trovare la distanza più breve tra un poligono rosso e il poligono blu più vicino?

Tieni presente che non si tratta semplicemente di prendere i punti che compongono i vertici del poligono come valori per testare la distanza poiché potrebbero non essere necessariamente i punti più vicini.

Quindi, alla fine, la risposta dovrebbe restituire il poligono blu più vicino al singolare rosso.

Questo è più difficile di quanto sembri!

È stato utile?

Soluzione

Dubito che ci sia una soluzione migliore che calcolare la distanza tra quello rosso e tutti quelli blu e ordinarli per lunghezza.

Per quanto riguarda l'ordinamento, di solito QuickSort è difficile da battere in termini di prestazioni (uno ottimizzato, che interrompe la ricorsione se la dimensione scende al di sotto di 7 elementi e passa a qualcosa come InsertionSort, forse ShellSort).

Quindi immagino che la domanda sia come calcolare rapidamente la distanza tra due poligoni, dopotutto è necessario eseguire questo calcolo 50 volte.

Il seguente approccio funzionerà anche per il 3D, ma probabilmente non è il più veloce:

Distanza minima del poligono nello spazio 2D

La domanda è: sei disposto a barattare la precisione con la velocità?Per esempio.puoi comprimere tutti i poligoni in riquadri di delimitazione, dove i lati dei riquadri sono paralleli agli assi del sistema di coordinate.I giochi 3D utilizzano questo approccio abbastanza spesso.Pertanto è necessario trovare i valori massimo e minimo per ogni coordinata (x, y, z) per costruire il riquadro di delimitazione virtuale.Calcolare le distanze di questi riquadri di delimitazione è quindi un compito piuttosto banale.

Ecco un'immagine di esempio di riquadri di delimitazione più avanzati, che non sono paralleli agli assi del sistema di coordinate:

Riquadri di delimitazione orientati - OBB

Tuttavia, questo rende il calcolo della distanza meno banale.Viene utilizzato per il rilevamento delle collisioni, poiché non è necessario conoscere la distanza, è sufficiente sapere se un bordo di un riquadro di delimitazione si trova all'interno di un altro riquadro di delimitazione.

L'immagine seguente mostra un riquadro di delimitazione allineato agli assi:

Riquadro di delimitazione allineato con gli assi - AABB

Gli OOB sono più accurati, gli AABB sono più veloci.Forse ti piacerebbe leggere questo articolo:

Tecniche avanzate di rilevamento delle collisioni

Ciò presuppone sempre che tu sia disposto a scambiare la precisione con la velocità.Se la precisione è più importante della velocità, potresti aver bisogno di una tecnica più avanzata.

Altri suggerimenti

Potresti essere in grado di ridurre il problema e quindi eseguire una ricerca intensiva su un piccolo set.

Elabora prima ciascun poligono trovando:

  • Centro del poligono
  • Raggio massimo del poligono (ovvero, punto sul bordo/superficie/vertice del poligono più lontano dal centro definito)

Ora puoi raccogliere, diciamo, i 5-10 poligoni più vicini a quello rosso (trova la distanza da centro a centro, sottrai il raggio, ordina l'elenco e prendi i primi 5) e poi esegui una routine molto più esaustiva.

Per le forme poligonali con un numero ragionevole di punti di confine, come in un'applicazione GIS o di giochi, potrebbe essere più semplice e veloce eseguire una serie di test.

Per ogni vertice nel poligono rosso calcola la distanza da ciascun vertice nei poligoni blu e trova il più vicino (suggerimento, confronta la distanza^2 in modo da non aver bisogno di sqrt ()) trova il più vicino, quindi controlla il vertice su ciascun lato del vertice rosso e blu trovato per decidere quali segmenti di linea sono più vicini e quindi trovare l'approccio più vicino tra due segmenti di linea.

Vedere http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/ (è facile semplicemente per il caso 2d)

Questa tecnica di screening ha lo scopo di ridurre il numero di calcoli della distanza da eseguire nel caso medio, senza compromettere l'accuratezza del risultato.Funziona su poligoni convessi e concavi.

Trova la distanza minima tra ciascuna coppia di vertici tale che uno sia rosso e l'altro blu.Chiamalo R.La distanza tra i poligoni è al massimo R.Costruisci una nuova regione dal poligono rosso in cui ogni segmento di linea viene spostato verso l'esterno R ed è unito ai suoi vicini da un arco di raggio R è centrato nel vertice.Trova la distanza da ciascun vertice all'interno di questa regione a ogni segmento di linea del colore opposto che interseca questa regione.

Naturalmente potresti aggiungere un metodo approssimativo come i riquadri di delimitazione per determinare rapidamente quale dei poligoni blu non può intersecarsi con la regione rossa.

So che hai detto "la distanza più breve" ma in realtà intendevi la soluzione ottimale o una soluzione "buona/molto buona" va bene per il tuo problema?

Perché se devi trovare la soluzione ottimale, devi calcolare la distanza tra tutti i limiti del poligono di origine e di destinazione (non solo i vertici).Se ti trovi nello spazio 3D, ogni limite è un piano.Questo può essere un grosso problema (O(n^2)) a seconda di quanti vertici hai.

Quindi, se hai un conteggio dei vertici che fa quadrato a un numero spaventoso E una soluzione "buona/molto buona" va bene per te, scegli una soluzione euristica o un'approssimazione.

Potresti dare un'occhiata a Voronoi Culling.Documento e video qui:

http://www.cs.unc.edu/~geom/DVD/

Inizierei delimitando tutti i poligoni con un cerchio delimitante e quindi trovando un limite superiore della distanza minima.Quindi controllerei semplicemente i bordi di tutti i poligoni blu il cui limite inferiore della distanza è inferiore al limite superiore della distanza minima rispetto a tutti i bordi del poligono rosso.

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

Ma tutto dipende dai tuoi dati.Se i poligoni blu sono relativamente piccoli rispetto alle distanze tra loro e il poligono rosso, allora questo approccio dovrebbe funzionare bene, ma se sono molto vicini, non salverai nulla (molti di loro saranno abbastanza vicini).E un'altra cosa: se questi poligoni non hanno molti vertici (come se la maggior parte di essi fossero triangoli), allora potrebbe essere altrettanto veloce controllare semplicemente ogni bordo rosso con ogni bordo blu.

spero che sia d'aiuto

Come altri hanno già detto, l'utilizzo di aree di delimitazione (riquadri, cerchi) può consentire di scartare alcune interazioni poligono-poligono.Esistono diverse strategie per questo, ad es.

  1. Scegli un poligono blu qualsiasi e trova la distanza da quello rosso.Ora scegli un altro poligono qualsiasi.Se la distanza minima tra le aree di delimitazione è maggiore della distanza già trovata, puoi ignorare questo poligono.Continua per tutti i poligoni.
  2. Trova la distanza minima/distanza baricentrica tra il poligono rosso e tutti i poligoni blu.Ordina le distanze e considera prima la distanza più piccola.Calcola la distanza minima effettiva e continua attraverso l'elenco ordinato finché la distanza massima tra i poligoni non sarà maggiore della distanza minima trovata finora.

La scelta di cerchi/riquadri allineati assialmente o riquadri orientati può avere un grande effetto sulle prestazioni dell'algoritmo, a seconda della disposizione effettiva dei poligoni di input.

Per il calcolo della distanza minima effettiva è possibile utilizzare il metodo ' di Yang et al.Un nuovo algoritmo veloce per calcolare la distanza tra due poligoni convessi disgiunti basato sul diagramma di Voronoi' che è O(log n + log m).

Devo scappare a un funerale tra un secondo, ma se dividi i tuoi poligoni in sottopoli convessi, ci sono alcune ottimizzazioni che puoi fare.Puoi fare una ricerca binaria su ciascun poligono per trovare il vertice più vicino, e poi I credere il punto più vicino dovrebbe essere quel vertice o un bordo adiacente.Ciò significa che dovresti essere in grado di farlo log(log m * n) dove m è il numero medio di vertici su un poligono e n è il numero di poligoni.È un po' frettoloso, quindi potrebbe essere sbagliato.Fornirà maggiori dettagli in seguito, se lo si desidera.

Potresti iniziare confrontando la distanza tra i riquadri di delimitazione.Testare la distanza tra i rettangoli è più semplice che testare la distanza tra i poligoni e puoi eliminare immediatamente tutti i poligoni che sono più lontani di neighbor_rect + its_diagonal (forse puoi perfezionarlo ancora di più).Quindi, puoi testare i poligoni rimanenti per trovare il poligono più vicino.

Esistono algoritmi per trovare la prossimità dei poligoni: sono sicuro che Wikipedia ne ha una buona recensione.Se ricordo bene, quelli che consentono solo poligoni convessi sono sostanzialmente più veloci.

Credo che quello che stai cercando sia l'algoritmo A*, è utilizzato nel pathfinding.

L'approccio ingenuo è trovare la distanza tra gli oggetti rossi e 50 blu, quindi stai guardando 50 calcoli pitagorici 3D + ordinamento per trovare la risposta.Tuttavia funzionerebbe davvero solo per trovare la distanza tra i punti centrali.

Se desideri poligoni arbitrari, forse la soluzione migliore è una soluzione di raytracing che emette raggi dalla superficie del poligono rosso rispetto alla normale e segnala quando viene colpito un altro poligono.

Un ibrido potrebbe funzionare: potremmo trovare la distanza dai punti centrali, assumendo di avere qualche idea della dimensione relativa dei poligoni blu, potremmo selezionare il set di risultati più vicino tra quelli, quindi utilizzare il raytracing per restringere il campo reale poligono/i più vicino/i.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top