Algoritmo de nivel 2D de detalle (LOD)

Question

He estado buscando en la red un algoritmo que te permita crear representaciones de niveles de detalle (LOD) de polígonos 2D, pero no puedo encontrar CUALQUIER referencia decente. Tal vez estoy usando términos de búsqueda incorrectos, pero todos los resultados de búsqueda son para algoritmos 3D LOD, que, supongo, no pueden (?) Realmente aplicarse en 2D.

Estoy seguro de que antes de la embestida de los gráficos 3D, muchas personas habrían trabajado en algoritmos 2D LOD. ¿Alguna pista o punteros a donde puedo obtener más información? ¡Gracias!

Answer 1

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:.

1. Calcular todos los ángulos entre los segmentos de Si y Si + 1 de el polígono
2. Tome todos los ángulos por debajo de un umbral dado (o tome los M menores ángulos)
3. Simplifique los segmentos que identificamos en 2. (reemplace [Pi, Pi + 1] y [Pi + 1, Pi + 2 ] por [Pi, Pi + 2])
4. 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:

1. Considere los vértices del polígono originales como los puntos de control de una spline de Catmull-Rom
2. 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

Answer 2

Buscar Douglas-Peucker algorithm que se utiliza para simplificar polilíneas, pero puede ser extendida para soportar polígonos. Es lo que he usado. También hay extensiones topológicamente estables si es necesario.