metodo veloce per trovare la distanza dal punto più vicino bordo del poligono

Question

Setup

• funzione dovrà fornire la distanza da un punto verso il bordo più vicino di un poligono
• Point è conosciuto per essere all'interno della poligono
• poligono può essere concave o convesse
• molti punti (milioni) dovranno essere testati
• Molti poligoni separati (decine) dovrà essere eseguito attraverso la funzione per punto
• Le strutture di dati precalcolate e memorizzate in modo permanente sono un'opzione.
• La funzione di ricerca finale sarà in C++

Per l'implementazione della funzione, so che un metodo semplice potrebbe essere quella di verificare la distanza a tutti i segmenti del poligono con distanza standard per allineare le formule di segmento. Questa opzione sarebbe abbastanza lenta e sono sicuro che dovrebbe esserci un'opzione migliore.

Il mio istinto è che dovrebbero esserci alcuni algoritmi molto veloci per questo tipo di funzione che sarebbero stati implementati in un motore di gioco, ma non sono sicuro di dove cercare.

Ho trovato un riferimento per la memorizzazione di segmenti di linea in un quadruplo, che fornirebbe una ricerca molto rapida e penso che potrebbe essere usato per il mio scopo di restringere rapidamente il segmento da considerare come il segmento più vicino e poi avrebbe solo bisogno di calcolare la distanza di un segmento di linea. https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf

Non sono stato in grado di individuare alcun esempio di codice per come funzionerebbe. Non mi interessa implementare algoritmi da zero, ma non vedo il punto nel farlo se esiste una base di codice funzionante e testata.

Ho osservato un paio di implementazioni in quad e penso che il modo in cui avrebbe funzionato è creare un quadrifoglio per poligono e inserire i segmenti di ogni poligono con un rettangolo di selezione nel quadrifoglio per quel poligono.

La parte "query" della funzione che vorrei creare consisterebbe nel creare un punto come un riquadro di delimitazione molto piccolo, che verrebbe quindi utilizzato per cercare la struttura quadripre, che quindi troverà solo il più vicino porzioni del poligono.

http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

e

https://github.com/Esri/geometry-api-java/blob/master/src/main/java/com/esri/core/geometry/QuadTree.java

La mia vera domanda sarebbe, Ti sembra un valido approccio per una funzione di tempo di ricerca veloce?

C'è qualcosa che potrebbe funzionare più velocemente?

MODIFICA: Mi sono guardato in giro e ho trovato alcuni problemi con l'utilizzo di un quadrifoglio. Il modo in cui i quadrifori funzionano è utile per il rilevamento delle collisioni, ma non è configurato per consentire una ricerca efficiente del vicino più vicino. https://gamedev.stackexchange.com/questions/14373/in-2d-how-do-i-efficiently-find-the-nearest-object-to-a-point

R-Trees sembrano essere un'opzione migliore. https://en.wikipedia.org/wiki/R-tree

e

efficient way to handle 2d line segments

Sulla base di tali posti, R-alberi sembrano il vincitore. Utile anche per vedere che C++ Boost li ha già implementati. Questo sembra abbastanza vicino a quello che stavo progettando di fare che andrò avanti e implementarlo e verificare i risultati.

Answer 1

EDIT: Dal momento che ho implementato un quadtree PMR, vedo ora, che la ricerca vicino più prossimo è un po 'più complessa di quanto ho descritto. Se il risultato della ricerca quad per il punto di ricerca è vuoto, diventa più complesso. Ricordo una descrizione da qualche parte in Hannan Sammets: struttura di ricerca multidimensionale. Dando la risposta di sotto avevo in mente la ricerca di tutti gli oggetti con una distanza specificata. Questo è facile per il quadrifoglio PMR, ma trovare il più vicino è più complesso. Modifica fine

Non vorrei utilizzare un R-Tree.
Il punto debole (e il punto di forza!) Sugli alberi R è la separazione dello spazio in rettangoli.
Esistono tre algoritmi noti per eseguire tale separazione, ma nessuno è adatto per tutte le situazioni. Gli alberi R sono molto complessi da implementare. Perché allora farlo? Solo perché gli alberi R possono essere due volte più veloci di un albero quad quando perfettamente implementati. La differenza di velocità tra un quadruplo e un R-Tree non è rilevante. La differenza monetaria è. (Se hai codice funzionante per entrambi, utilizzerei il quadrifoglio PMR, se hai solo il codice per l'albero R, allora usa quello, se non ne hai nessuno usa il Quadrifoglio PMR)

Quadri (PMR) funzionano sempre, e sono semplici da implementare.

Utilizzando il quadruplo PMR, vengono individuati tutti i segmenti relativi al punto di ricerca. Il risultato saranno alcuni segmenti, quindi li controlli e sei pronto.

Le persone che dicono che i quadricipiti non sono adatti o alla ricerca del vicino, non sanno che ci sono centinaia di quadrangoli diversi. La non idoneità è vera solo per un punto quad tree, non per quello PMR, che memorizza i bounding box.

Una volta ho ripetuto la descrizione del compelx di trovare i punti vicini in un POINT-Quadtree. Per il quadrifoglio PMR non avevo nulla da fare (per una ricerca all'interno di un intervallo rettangolare specificato), nessun cambio di codice, basta ripetere il risultato e trovare il più vicino.

Penso che ci siano soluzioni persino migliori rispetto a Quad tree o R-Tree per le vostre domande specifiche, ma il punto è che il PMR funziona sempre. Basta implementarlo una volta e usarlo se per tutte le ricerche spaziali.

Answer 2

Non sono sicuro di quanto grande sarebbe stato l'algoritmo quadtree, quindi lascerò che qualcun altro lo commentasse, ma ho pensato a qualcosa che potrebbe essere veloce e robusto.

Il mio pensiero è che potresti rappresentare un poligono con un albero KD (supponendo che i vertici siano statici nel tempo) e quindi trovare i due vertici più vicini, facendo una ricerca vicina più vicina a 2, a qualunque sia il punto in cui si trova poligono. Questi due vertici dovrebbero essere quelli che creano il segmento di linea più vicino, indipendentemente dalla convessità, se il mio pensiero è corretto.

Answer 3

Dato che ci sono molti più punti da testare rispetto ai poligoni, è possibile prendere in considerazione una pre-elaborazione piuttosto estesa dei poligoni per accelerare il numero medio di test per trovare il segmento di linea più vicino per punto.

consideri un approccio di questo tipo (si assume poligoni hanno fori):

1. piedi i bordi del poligono e definiscono segmenti di linea lungo ciascuna linea equidistante
2. Prova quale lato del segmento di linea un punto è per limitare il potenziale insieme di segmenti di linea più vicini
3. Costruisci un albero di codifica aritmetico con ciascun test ponderato in base alla quantità di spazio che viene scartata dal semispazio del segmento di linea. questo dovrebbe dare una buona prestazione media nel determinare il segmento più vicino per un punto e aprire la possibilità di test paralleli su più punti contemporaneamente.

Questo diagramma dovrebbe illustrare il concetto. Le linee blu definiscono il poligono e le linee rosse sono le linee equidistanti.

Si noti che il bisogno di supportare i poligoni concavi aumenta notevolmente la complessità, come illustrato dalla regione 6-7-8. Le regioni concave significano che i segmenti di linea che si estendono all'infinito possono essere definiti da vertici arbitrariamente distanti.

È possibile scomporre questo problema inserendo uno scafo convesso nel poligono e quindi eseguire un test rapido e convesso per la maggior parte dei punti e fare solo ulteriore lavoro sui punti che si trovano all'interno della "regione di influenza" della regione concava, ma Non sono sicuro se ci sia un modo veloce per calcolare quel test.