Aparte del algoritmo más estúpido obvio que sería tomar cada N-ésimo vértice del polígono (reduciendo el número de vértices por N), aquí hay una idea inspirada en algunos algoritmos 3D.
Normalmente, en 3D, lo que se necesita es eliminar las caras que contribuyen menos al volumen general. Para hacer esto, tratamos de simplificar las áreas "más planas" del modelo.
Ahora en 2D, que se podría traducir esto a "simplificar los segmentos que tienen el menor ángulo entre ellos una primera implementación ingenua podría ser:.
- Calcular todos los ángulos entre los segmentos de Si y Si + 1 de el polígono
- Tome todos los ángulos por debajo de un umbral dado (o tome los M menores ángulos)
- Simplifique los segmentos que identificamos en 2. (reemplace [Pi, Pi + 1] y [Pi + 1, Pi + 2 ] por [Pi, Pi + 2])
- Repita desde 1. hasta que hayamos reducido suficientemente nuestro polígono en
Por supuesto, esto no es óptimo, pero debería ser una buena operación entre calidad y velocidad. En lugar del ángulo, se puede tomar la distancia mínima entre el punto medio de dos segmentos (Pi + 1) y el segmento potencialmente simplificado ([Pi, Pi + 2])
Editar:
Otro algoritmo I intentaría si yo no necesitaba demasiada rendimiento:
- Considere los vértices del polígono originales como los puntos de control de una spline de Catmull-Rom
- tesselate este spline en el número deseado de puntos
Finalmente, encontré algo de código fuente para que en ese enlace: http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html, así como la algoritmos asociados: http://www.geom.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm
Interesante, ¿tal vez buscando la simplificación de la forma, la abstracción de la imagen o incluso la compresión? ¿Cuáles son los requisitos para el LOD? Al igual que en la voluntad de la imagen se redujo? ¿Es para el rendimiento, para guardar la memoria o emular la profundidad? –
Estoy buscando mejorar el rendimiento de un algoritmo existente (heredado). Básicamente, quiero una aproximación razonable del "envoltorio retráctil" del polígono, donde se conservan las principales características externas y los detalles internos ocultos. +1 para las palabras clave sugeridas. ¡Gracias! – tathagata