¿Cómo tratan los programadores gráficos con vértices de renderizado que no cambian la imagen?

10

Entonces, el título es un poco incómodo. Daré algunos antecedentes y luego haré mi pregunta.

Antecedentes : trabajo como desarrollador de aplicaciones SIG web , pero en mi tiempo libre he estado jugando con la representación de mapas y mejorando los formatos de intercambio de datos. Solo trabajo en el espacio 2D.

Un problema interesante que he encontrado es que cuando se renderiza un polígono a pequeña escala (alejándose), muchos de los vértices son redundantes. Un caso extremo sería que tiene un polígono con 500,000 vértices que solo ocupa un solo píxel. Si está enviando estos datos al navegador, tendría sentido omitir ~ 499,999 de esos vértices. Una forma de lograrlo es renderizando una imagen en un servidor y enviándola como PNG: voila, es un punto. Sin embargo, a veces, queremos que los datos se envíen al navegador donde se pueden representar con SVG (o canvas, o webgl) para que puedan ser interactivos.

El problema : resulta que, usando conjuntos de datos geográficos modernos, es muy fácil sobrecargar las capacidades de renderizado de SVG. En un esfuerzo por hacer frente a esas limitaciones, estoy tratando de descubrir cómo reducir visualmente sin pérdidas un conjunto de datos para una escala y extensión de mapa determinadas (y, si es necesario, para un ancho y altura de píxeles de mapa conocidos).

Obtuve una gran reducción en el tamaño de los datos simplemente usando el algoritmo Douglas-Peucker , y creo que pude lograr que los polígonos se mantuvieran fieles a un píxel. Desafortunadamente, Douglas-Peucker no conserva la topología, por lo que cambió la forma en que se renderizaron los límites entre los polígonos. No pude encontrar fácilmente otros algoritmos para probar y adaptarme al propósito, pero no tengo mucha experiencia en CS / algoritmo y podría no reconocerlos si los viera.

canisrufus
fuente
1
Busque "Douglas-Peucker topológicamente coherente" en Google y encontrará algunos enlaces a resúmenes de algunos artículos. Desafortunadamente, tienes que pagar por los artículos completos que vi.
Doc Brown
@DocBrown ¡ Gracias! Questia incluso parece tener una prueba gratuita.
canisrufus

Respuestas:

3

Lo que estás buscando es 2d level of detail algorithms.

Hay mucho documentado sobre esto en Google si busca esos términos resaltados.

Esta pregunta sobre stackoverflow tiene la información que está buscando en la representación de Nivel de detalle 2D.

Comunidad
fuente
+1 para el vocabulario muy pertinente. Parece que en realidad estoy usando un enfoque de nivel de detalle, pero necesito un algoritmo de simplificación de polígonos que se adapte a mis necesidades. Encontró una visión general ordenada para los 3d. Creo que realmente he elaborado una estrategia de simplificación adecuada, aunque no he tenido tiempo de codificarla.
canisrufus 05 de