Genera grafico di Connected convessi poligoni

StackOverflow https://stackoverflow.com/questions/4752816

Domanda

Sto cercando di prendere un grafico densa di punti, come questo , e trasformarlo in un grafico di poligono convesso collegati. I poligoni deve essere il più grande e più semplice possibile rimanendo connessi. Il grafico risultante sarà utilizzato per pathfinding. Qualcuno può punto me nella giusta direzione?

È stato utile?

Soluzione

E 'molto fastidioso che non posso postare link. Lo rende difficile essere un lurker e solo partecipante occasionale.

Ho finito per usare le seguenti tecniche:

In primo luogo, creare una distanza di trasformare. Ho usato l'algoritmo descritto qui [non può collegare], con conseguente un'immagine di questo tipo [no link]. Quindi, creare uno spartiacque trasformata di DT di partizionare in aree. Questo ha bisogno di un certo lavoro, ma attualmente sembra che questo [non può link] Quindi, utilizzare i punti medi dei polilinee che collegano ogni coppia di zone, per creare un grafico waypoint.

Risultato

Il partizionamento spartiacque non è ancora perfetto, nota l'aliasing causando banding ma io alla fine con 181 aree e 281 waypoint per questa 128x128 mappa.

Altri suggerimenti

Questo non è quello che hai chiesto, ma qui ci sono alcune altre idee per risolvere questo problema di pianificazione percorso 2D:

  • Usa A *. Questo produce il più breve percorso libero di collisione. Prestazioni potrebbe essere OK, anche senza la semplificazione della bitmap.

  • Usa un roadmap campionamento-based. Questa è un'altra rappresentazione discretizzata di poligoni. Dal momento che il vostro spazio di ricerca è di piccole dimensioni, si può attraversare l'intera bitmap per verificare che ogni punto può essere collegato alla tabella di marcia. Se un compatto tabella di marcia è importante (ma percorsi brevi non sono), il tecnica visibilità tabella di marcia può essere utilizzato.

Dal momento che si ha a che fare con la rappresentazione grafica e grafico a cercare in ogni caso, queste tecniche sembrano molto più facile che l'estrazione del poligono. Ho scavato alcune domande quindi per questo problema:

Quando lo spazio è stato mappato da poligoni (possibilmente utilizzando uno strumento), può essere suddivisa in poligono convesso o qualche altra rappresentazione che può essere cercato. Questo è anche discusso da LaValle:

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