Generar el gráfico de polígonos convexos Connected

Question

Estoy tratando de tomar una gráfica densa de puntos tales como este , y convertirlo en un gráfico de polígonos convexos conectados. Los polígonos deben ser tan grandes y tan simple como sea posible mientras se mantienen conectados. El gráfico resultante será utilizado para la búsqueda de caminos. Me puede punto cualquiera en la dirección correcta?

Answer 1

Es muy molesto que no puedo publicar enlaces. Hace que sea difícil ser un merodeador y única participante ocasional.

Terminé usando las siguientes técnicas:

En primer lugar, crear una transformada de distancia. Solía ??El algoritmo descrito aquí [no se puede vincular], resultando en una imagen como esta [No se puede link]. A continuación, crear una transformación cuenca del DT para dividir en zonas. Esto necesita un poco de trabajo, pero en la actualidad se parece a esto [no puede link] A continuación, utilice los puntos medios de las polilíneas que conectan cada par de zonas, para crear un gráfico de punto de referencia.

Resultado

La partición de cuencas no es perfecto, sin embargo, tenga en cuenta el aliasing causando bandas pero terminan con 181 zonas y 281 waypoints para esta 128x128 mapa.

Answer 2

Esto no es lo que pidieron, pero aquí hay algunas otras ideas para la solución de este problema de planificación de trayectoria 2D:

• Usar A *. Esto proporciona la ruta más corta libre de colisiones. Rendimiento podría estar bien, incluso sin la simplificación del mapa de bits.

• Usar un hoja de ruta basada en el muestreo. Esta es otra representación discretizada de polígonos. Debido a que su espacio de búsqueda es pequeña, se puede recorrer todo el mapa de bits para verificar que cada punto se puede conectar a la hoja de ruta. Si un compacta hoja de ruta es importante (pero no son los caminos más cortos), el técnica de visibilidad hoja de ruta se puede utilizar.

Ya que tienes que hacer frente a la representación gráfica y el gráfico en busca de todos modos, estas técnicas parecen mucho más fácil que la extracción polígono. Desenterré algunas preguntas así que por ese problema:

• de mapa de bits a Polígono
• ¿Cómo puedo convertir mapas de bits sencilla forma a vectores

Cuando el espacio se ha mapeado por polígonos (posiblemente utilizando una herramienta), que se puede dividir en polígonos convexos o alguna otra representación que se puede buscar. Esto también es discutido por Lavalle:

• Vertical (trapezoidal) Cell descomposición
• ruta más corta hojas de ruta