La migliore struttura dati per archiviare poligoni contigui?

Question

Mi dispiace, sto avendo molti problemi a dare una risposta a questa domanda.

Sono bloccato su quale struttura dati (o combinazione di strutture dati) dovrei usare per memorizzare un accordo di poligoni che si confondono l'un l'altro (come qualsiasi mappa del mondo reale).

Devo chiarire: quello che intendo fare è avere un punto che si muove a una velocità fissa attraverso una mappa (un paesaggio) di questi poligoni. L'intero paesaggio è coperto di poligoni: nessuno spazio è non classificato; ogni punto della mappa appartiene a qualche poligono. Ciò significa che tutti i poligoni delimitano, su tutti i lati, un altro poligono o il bordo della mappa. La mappa è limitata, ma idealmente, non dovrebbe importare quanto è grande la mappa o quanti poligoni sono rappresentati. Ogni poligono ha un nome (questo è significativo, poiché ogni punto ora appartiene ad almeno due poligoni nominati). Il punto che si muove attraverso la mappa dovrebbe sempre conoscere il nome del poligono in cui si trova, e il punto dovrebbe anche essere notificato ogni volta che attraversa un confine da un poligono a un altro. (se sono necessari altri chiarimenti, si prega di commentare.)

Esiste un modo accettato per farlo?

--EDIT--

I poligoni sono fissi. Tutti i punti e i bordi dovranno essere hard-coded in anticipo. I punti e gli spigoli non cambieranno mai in modo imprevedibile o casuale (se cambiano, sarà in risposta a un evento fisso poco frequente).

Answer 1

Build a 2D segment tree dove ogni intervallo 2D corrisponde al riquadro di delimitazione di un poligono e il tipo di valore corrisponde al poligono stesso (l'elenco dei suoi bordi).

Dopo che l'agente è passato da p1 a p2, eseguire una query di finestra sull'albero del segmento: cercare tutti gli intervalli 2D (riquadri di delimitazione) che si intersecano con/contenuti nel rettangolo definito da p1 e p2.

Per ciascuno dei poligoni all'interno di queste caselle di delimitazione, verificare se contiene p2.

Answer 2

Il termine tecnico che descrive questo è un planar straight-line graph, per il quale una rappresentazione adeguata è il doubly connected edge list (DCEL).

Uno dei requisiti della struttura dati sembra essere la possibilità di eseguire query di posizione punto (veloce). (A quale poligono appartiene questo punto?) Esistono soluzioni classiche, tra cui si può raccomandare lo trapezoidal decomposition.

Non so di una soluzione adeguata per le query "border", cioè trovare le intersezioni con una (presumibilmente) traiettoria lineare. Probabilmente puoi adattarti dal problema della posizione del punto, ma questo promette di essere complicato.

In ogni caso, se i poligoni hanno un numero ragionevole di vertici, non è un grosso problema trovare tutte le intersezioni con una linea retta provando a turno tutti i bordi. Usando una rappresentazione DCEL, quando lasci un poligono, sai quale inserisci.

Se fossi in te, vorrei iniziare con una struttura DCEL, un algoritmo point-in-polygon e un algoritmo di intersezione linea-poligono (che è essenzialmente la stessa cosa).