Buscar el eje medio de un polígono usando C#

Question

Se me ha encomendado averiguar cómo encontrar la línea central de un polígono. Mis búsquedas en Google me llevaron a creer que lo que necesito se llama 'Eje medial'. De esta manera:

alt text http://www.ndl.kiev.ua/downloads/center_line.png

Según lo que he leído, lo que necesito se pueden producir mediante el uso de un algoritmo de construcción diagrama de Voronoi 2D para los segmentos.

he encontrado una versión C# del algoritmo de Voronoi en CodePlex (FortuneVoronoi) y después de aplicar mi polígono para que, termino con esto:

alt text http://www.carbonatlas.com/geonotes/gaia_voronoi.png

El verde es el polígono originales. Los naranja son los vértices Voronoi y las líneas negras son los bordes voronoi.

Puedo ver lo que necesito en esos vértices, pero no estoy seguro del próximo paso requerido para filtrar todo lo que no necesito.

Agradecería cualquier ayuda que pueda ofrecer.

Answer 1

Una solución sencilla sería como se sugiere en los comentarios:

1. Construir la triangulación de Delaunay de los vértices del polígono.
2. Identificar los vértices de Voronoi dentro del polígono (ver http://en.wikipedia.org/wiki/Point_in_polygon)
3. salida la Voronoi bordes de conexión dos vértices interior de Voronoi.

Si tiene datos enormes, las intersecciones pueden ser bastante costosas.

Entonces podría hacer un enfoque similar al de question, y this solution también podría funcionar para usted. La forma en que lo haría:

1. Construye la triangulación de Delaunay de los vértices del polígono.
2. Inserte el punto medio de cada borde del polígono que no esté cubierto por un borde delaunay. Haga esto recursivamente hasta que todos los bordes del polígono estén cubiertos por los bordes de Delaunay.
3. Marque todos los bordes de Delaunay que corresponden a un borde de polígono.
4. Extraiga el eje interno siguiendo los pasos 3.-5. en this solution

PS. Tenga en cuenta que ambas soluciones dan una aproximación del eje medio, calculando exactamente es mucho más costoso, pero como reclamo ... puede obtener resultados como este de los puntos de muestreo de entrada negras:

Answer 2

Wow. Voy a dar un paso aquí y sugerir que tal vez el algoritmo esté confundido sobre el interior y el exterior del polígono. Cuando define los bordes y vértices de su polígono original, debe asegurarse de que estén definidos de tal manera que siempre se encuentre "adentro" utilizando algo así como la "regla de la mano derecha". Solo mirando el polígono en la esquina inferior derecha, parece que el borde de su polígono realmente se cruza. Tal vez el algoritmo vea esa sección, y otras, como "de adentro hacia afuera". Lo mismo en la parte inferior izquierda.

Esa es mi corazonada, que el algoritmo no parece ser capaz de determinar qué dirección hay dentro y qué está afuera.

Creo que un enfoque ingenuo sería filtrar todos los "nodos" de Voroni que están fuera del polígono, sin embargo, no creo que se vea. Mirando más de cerca su diagrama, parece que cada nodo tiene 3 bordes que lo conectan a otros nodos. Quizás pueda filtrar nodos donde cualquiera de los 3 bordes esté conectado a nodos fuera del polígono. Funcionaría eso?

Answer 3

Una construcción similar es Straight skeleton, que se puede construir encogiendo el polígono dentro de sí mismo y rastreando los vértices a medida que se acercan al centro. Esto puede ser un poco más fácil de construir, aunque no es exactamente la misma curva que el eje medial.