algorithm - Polígonos simplificados(o suaves) que contienen el polígono detallado original

geometry gis (5)

Tengo un polígono 2D detallado (que representa un área geográfica) que está definido por un conjunto muy grande de vértices. Estoy buscando un algoritmo que simplifique y suavice el polígono, (reduciendo el número de vértices) con la restricción de que el área del polígono resultante debe contener todos los vértices del polígono detallado.

Para el contexto, aquí hay un ejemplo del borde de un polígono complejo:

Mi investigación:

Encontré el algoritmo Ramer-Douglas-Peucker que reducirá el número de vértices, pero el polígono resultante no contendrá todos los vértices del polígono original. Ver este artículo Ramer-Douglas-Peucker en Wikipedia
Consideré expandir el polígono (creo que esto también se conoce como compensación de polígono externo). Encontré estas preguntas: expandir un polígono (solo convexo) e inflar un polígono . Pero no creo que esto reduzca sustancialmente los detalles de mi polígono.

¡Gracias por cualquier consejo que puedas darme!

¡Es un problema interesante! Nunca intenté algo como esto, pero esta es una idea en mi cabeza ... disculpas si no tiene sentido o no funcionaría :)

Calcule un casco convexo, que podría ser demasiado grande / impreciso
Divida el casco en N rodajas, por ejemplo unir cada uno de los vértices del casco al centro
Calcula la intersección de tu objeto con cada corte
Repita recursivamente para cada intersección (calculando el casco de la intersección, etc.)

Cada nivel de recursividad debería dar una mejor aproximación ... cuando alcanzas un nivel satisfactorio, combina todos los cascos de ese nivel para obtener el polígono final.

¿Eso suena como que podría hacer el trabajo?

Creo que el algoritmo de Visvalingam se puede adaptar para este propósito, omitiendo la eliminación de triángulos que reducirían el área.

Hasta cierto punto, no estoy seguro de lo que estás tratando de hacer, pero parece que tienes dos respuestas muy buenas. Uno es Ramer-Douglas-Peucker (DP) y el otro está calculando la forma alfa (también llamado casco cóncavo, casco no convexo, etc.). Encontré un artículo más reciente que describe las formas alfa y lo vinculo abajo.

Personalmente, creo que DP con expansión de polígonos es el camino a seguir. No estoy seguro de por qué crees que no reducirá sustancialmente la cantidad de vértices. Con DP, usted proporciona un factor y puede hacer que sea lo que quiera hasta el punto en que termine con un triángulo sin importar cuál sea su entrada. Escoger este factor puede ser difícil, pero en tu caso, creo que es el mejor método. Debería poder determinar el factor según el tamaño del detalle más grande que desea eliminar. Puede hacer esto con pruebas directas o calculando desde sus datos de origen.

http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf

Tenía un problema muy similar: necesitaba una simplificación inflada de polígonos.

Hice un algoritmo simple, eliminando el punto de cóncavo (esto aumentará el tamaño del polígono) o eliminando el borde convexo (entre 2 puntos convexos) y prolongando los bordes adyacentes. En cualquier caso, hacer una de esas 2 posibilidades eliminará un punto en el polígono.

Decidí eliminar el punto o el borde que lleva a la variación de área más pequeña. Puede repetir este proceso hasta que la simplificación sea correcta para usted (por ejemplo, no más de 200 puntos).

Las 2 dificultades principales fueron obtener algoritmo rápido (evitando calcular la variación de eliminación de vértices / bordes dos veces y mantener las posibilidades ordenadas) y evitar insertar autointersecciones en el proceso (no muy fácil de hacer y explicar pero posible con una complejidad computacional limitada )

De hecho, después de mirar más de cerca, es una idea similar a la de Visvalingam con adaptación para la eliminación de bordes.

Editar

A partir de 2013, la mayoría de los enlaces a continuación ya no son funcionales. Sin embargo, encontré el documento citado, algoritmo incluido, todavía disponible en este servidor (muy lento) .

Here puede encontrar un proyecto que trate exactamente sus problemas. Aunque funciona principalmente con un área "llena" por puntos, puede configurarla para que funcione con una definición de tipo "perímetro" como la suya.

Utiliza un enfoque de k vecinos más cercanos para calcular la región.

Muestras:

Here puede solicitar una copia del documento.

Al parecer, planeaban ofrecer un servicio en línea para solicitar cálculos, pero no lo probé, y probablemente no se está ejecutando.

HTH!