Suavizado de línea eficiente (simplificar)

Question

Estoy creando una aplicación de pintura en Actionscript (aunque mi pregunta no está relacionada con Actionscript). La idea básica es comenzar a pintar cuando se presiona el mouse y seguir los movimientos del mouse. Lo que quiero es acchieve:

1. reducir el "ruido" del ratón y
2. crear líneas de aspecto más suave.

En este momento, (1) es problemático porque obtengo miles de movimientos del mouse en pocos segundos. Debido a (1) la línea puede verse irregular. Qué idea actual: cuando el usuario termina de dibujar la línea, almaceno todos los movimientos en una matriz y los reduzco (umbral mediano) y luego uso un algoritmo spline para recrear una línea.

¿Algún enfoque mejor?

Answer 1

Ver Efficient Curve Fitting por Sarah Frisken. También disponible at the author's page.

Answer 2

(topamos con su pregunta mientras mira por el mismo, y pasó a armar algo de nuestra propia)

http://willowsystems.github.com/jSignature/#/about/linesmoothing/

(enlace compatible con SEO para misma: http://willowsystems.github.com/jSignature/%2523%252Fabout%252Flinesmoothing%252F.html)

La cuestión tu describes es doble 1. Quiere 'simplificar' los datos de captura. 2. Desea dibujar una línea bonita ('ajustar una curva') dentro de los puntos.

Simplify.js citado anteriormente es realmente bueno, pero solo le da puntos. Para jSignature queríamos un algoritmo de ajuste de curvas super-eficiente y sin retardo.

Vea el enlace de arriba para la explicación de uno (nuestro) acercamiento a las curvas de ajuste (Bezier aka 'cubic') entre los puntos. Le permite mantener la línea que dibujó el usuario y simplemente retrasar la conexión de las últimas 2 coordenadas, o puede simplificar y volver a dibujar toda la línea de esa manera.

(Nuestra publicación del algoritmo fue intencional, como para establecer el "estado de la técnica" y excluir la petentabilidad del método combinado. Esto significa que no ponemos nuestro yugo patentado en el algoritmo y lo buscamos y no lo hicimos encontrarlo patentado en otra parte. Por supuesto, puede haber algún troll de patente que pueda encontrar un problema contigo al implementar el método, pero, al menos, no nosotros. Así que, disfruta.)

El enlace de demostración está usando Salto de 4 píxeles en el movimiento del mouse. Esto es crudo, pero está bien para la 'simplificación' de datos en tiempo real. Si tiene el lujo de capturar todo el trazo y volver a dibujarlo todo, sin duda, use simplify.js.

Answer 3

Mike Bostock tiene algunos buenos ejemplos aquí Line Simplification. Señala que el algoritmo Douglas-Peucker es bien conocido. Sin embargo, Visvalingam parece ser más efectivo.