Hispanopedia Wiki
Articulo de referencia

Algoritmo de Visvalingam-Whyatt

Comparación con el algoritmo de Douglas-Peucker El algoritmo de Visvalingam-Whyatt , o simplemente algoritmo de Visvalingam , es un algoritmo que reduce una curva compuesta por ...

Hispanopedia WikiContenido en espanolLectura gratuita
Comparación con el algoritmo de Douglas-Peucker

El algoritmo de Visvalingam-Whyatt , o simplemente algoritmo de Visvalingam , es un algoritmo que reduce una curva compuesta por segmentos de línea a una curva similar con menos puntos, principalmente para su uso en generalizaciones cartográficas .

Idea

Dado una cadena poligonal (a menudo llamada polilínea), el algoritmo intenta encontrar una cadena similar compuesta por menos puntos.

Los puntos se clasifican según su importancia en función de las condiciones locales, y se van eliminando desde los menos importantes hasta los más importantes.

En el algoritmo de Visvalingam, la importancia está relacionada con el área triangular que añade cada punto.

Algoritmo

Dada una cadena de puntos 2D{pagi}={[incógnitaiyi]}{\displaystyle \left\{p_{i}\right\}=\left\{{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}\right\}}La importancia de cada punto interior se calcula hallando el área del triángulo formado por él y sus vecinos inmediatos. Esto se puede hacer rápidamente usando un determinante de matriz . [ 1 ] Alternativamente, se puede usar la fórmula equivalente que se muestra a continuación . [ 2 ]

Ai=12|incógnitai−1yi+incógnitaiyi+1+incógnitai+1yi−1−incógnitai−1yi+1−incógnitaiyi−1−incógnitai+1yi|{\displaystyle A_{i}={\frac {1}{2}}\left|x_{i-1}y_{i}+x_{i}y_{i+1}+x_{i+1}y_{i-1}-x_{i-1}y_{i+1}-x_{i}y_{i-1}-x_{i+1}y_{i}\right|}

El punto de importancia mínimapagi{\displaystyle p_{i}}está ubicado y marcado para su remoción (tenga en cuenta queAi−1{\displaystyle A_{i-1}}yAi+1{\displaystyle A_{i+1}}será necesario volver a calcularlo). Este proceso se repite hasta que se alcanza el número de puntos deseado o la contribución del punto menos importante es lo suficientemente grande como para no ignorarla.

Ventajas

  • El algoritmo es fácil de entender y explicar, pero a menudo compite con enfoques mucho más complejos.
  • Mediante el uso de una cola de prioridad , el algoritmo ofrece un buen rendimiento con grandes conjuntos de datos, ya que la importancia de cada punto se puede calcular utilizando únicamente sus vecinos, y la eliminación de un punto solo requiere recalcular la importancia de otros dos puntos.
  • Es sencillo generalizar a dimensiones superiores, ya que el área del triángulo formado por los puntos tiene un significado consistente.

Desventajas

  • El algoritmo no diferencia entre picos pronunciados y características superficiales, lo que significa que eliminará los picos pronunciados que puedan ser importantes.
  • El algoritmo simplifica uniformemente toda la longitud de la curva, lo que significa que las curvas con áreas de alto y bajo nivel de detalle probablemente verán erosionados sus detalles finos.

Véase también

Entre los algoritmos alternativos para la simplificación de líneas se incluyen:

Referencias

Notas
  1. ↑ "6.5 – Aplicaciones de matrices y determinantes" . people.richland.edu . Consultado el 7 de julio de 2020 .
  2. ↑ "Documento sin título" . people.richland.edu . Consultado el 7 de julio de 2020 .
Bibliografía
  • Visvalingam, M.; Whyatt, JD (1993). "Generalización de líneas mediante eliminación repetida de puntos" (PDF) . The Cartographic Journal . 30 (1): 46– 51. doi : 10.1179/000870493786962263 . ISSN 0008-7041 . 
  • Ejemplo interactivo del algoritmo