Minimizar los vértices de polígonos

Question

¿Cuál es un buen algoritmo para reducir la cantidad de vértices en un polígono sin cambiar mucho la forma en que se ve?

Entrada: un polígono, representado como una lista de puntos, con demasiadas verticías: por ejemplo, entrada sin procesar del mouse.

Salida: un polígono con muchas menos verticales que todavía se parece mucho al original: algo que se puede usar para la detección de colisiones, por ejemplo (no necesariamente convexo).

Editar: La solución a esto sería similar a encontrar una línea multisegmentada de mejor ajuste en un gráfico. Se llama Segmentos mínimos segmentados en mi libro de algoritmos.

Edit2: el algoritmo de Douglas Peucker es lo que realmente quiero.

Answer 1

Edit: Oh, mira, Simplificación de polígonos

Mencionaste la detección de colisiones. Podrías ser realmente simple y calcular un casco convexo delimitador a su alrededor.

Si le importaron las áreas cóncavas, puede calcular un casco cóncavo tomando el centroide de su polígono y eligiendo un punto para comenzar. Desde el punto de inicio, gire alrededor del centroide, encuentre cada vértice que desee mantener y asigne ese vértice como el siguiente en el casco delimitador. La complejidad del algoritmo vendría en cómo determinó qué vértices mantener, pero estoy seguro de que ya lo pensó. Puede lanzar todos sus vértices en cubos en función de su ubicación en relación con el centroide. Cuando un cubo obtiene más que un número arbitrario de vértices llenos, puede dividirlo. Luego tome la media de los vértices en ese cubo como el vértice para usar en su casco de delimitación. O, olvida los cubos y, cuando te muevas por el centroide, solo elige un punto si está a más de una distancia dada del último punto.

En realidad, probablemente podrías usar todos los vértices de tu polígono como " nube de puntos " y calcular el casco cóncavo alrededor de eso. Buscaré un enlace de algoritmo. El peor de los casos sería un polígono completamente convexo.

Otra alternativa es comenzar con un rectángulo delimitador. Para cada vértice en el rectángulo, encuentre la distancia desde el punto hasta el polígono. Para el vértice más lejano, divídalo en dos vértices más y muévalos en algunos. Repita hasta que se cumpla una cierta proporción de vértices o área. Tendría que pensar un poco más en los detalles de este.

Si te importa que el polígono tenga un aspecto similar, incluso en el caso de un polígono que se intersecta por sí mismo, entonces se requeriría otro enfoque, pero no parece que eso sea necesario ya que preguntaste acerca de la detección de colisiones.

Esta publicación tiene algunos detalles sobre la parte del casco convexo.

Answer 2

Hay mucho material por ahí. Solo busca en Google cosas como " reducción de malla " ;, " simplificación de malla " ;, " optimización de malla " ;, etc.