¿Cómo puedo cuantificar la rectitud de una línea dibujada?

37

Estoy trabajando en un juego que requiere que los jugadores dibujen una línea desde un punto A (x1, y1) hasta el otro punto B (x2, y2) en la pantalla de un dispositivo Android.

Quiero encontrar qué tan bien ese dibujo se ajusta a una línea recta. Por ejemplo, un resultado del 90% significaría que el dibujo se ajusta casi perfectamente a la línea. Si los jugadores dibujan una línea curva de A a B, debería obtener una puntuación baja.

Los puntos finales no se conocen de antemano. ¿Cómo puedo hacer esto?

usuario3637362
fuente
1
¿Sabes de antemano cuáles son tus dos puntos finales? ¿O se determina en el momento en que el usuario deja de tocar la pantalla?
Vaillancourt
Lo siento si mi descripción no es clara para ti. Bueno, el punto de partida A (x, y) es el primer toque y el punto final B (x, y) es cuando salimos de la pantalla táctil como dijiste.
user3637362
Tenemos una pregunta relacionada sobre la correspondencia de letras dibujadas por jugadores .
Anko
3
No publique imágenes para el código fuente en el futuro.
Josh
1
@ user3637362 Entiendo que usted está comenzando j=1por lo que se puede comparar touchList[j]con touchList[j-1], pero cuando touch.phase == TouchPhase.Begano touch.phase == TouchPhase.Endedlas posiciones no se añaden a touchListy posteriormente no incluido en sumLength. Este error estaría presente en todos los casos, pero sería más evidente cuando la línea tiene pocos segmentos.
Kelly Thomas

Respuestas:

52

Una línea perfectamente recta también sería la línea más corta posible con una longitud total de sqrt((x1-x2)² + (y1-y2)²). Una línea más garabateada será una conexión menos ideal y, por lo tanto, será inevitablemente más larga.

Cuando toma todos los puntos individuales de la ruta que dibujó el usuario y suma las distancias entre ellos, puede comparar la longitud total con la longitud ideal. Cuanto más pequeña es la longitud total dividida por la longitud ideal, mejor es la línea.

Aquí hay una visualización. Cuando los puntos negros son los puntos finales del gesto y los puntos azules son los puntos que midió durante el gesto, calcularía y sumaría las longitudes de las líneas verdes y las dividiría por la longitud de la línea roja:

ingrese la descripción de la imagen aquí

Un puntaje o índice de sinuosidad de 1 sería perfecto, cualquier cosa más alta sería menos perfecta, cualquier cosa por debajo de 1 sería un error. Cuando prefiera tener el puntaje en porcentaje, divida el 100% por ese número.

Philipp
fuente
34
Hay un pequeño problema con este enfoque en que las polilíneas de igual longitud no son igualmente "rectas". Una línea que se tambalea con una desviación baja (pero muchas veces) sobre la línea recta es 'más recta' que una línea de igual longitud que se desvía hacia un solo punto y luego regresa.
Dancrumb
No puedo hacer +1 en @Dancrumbs para comentar lo suficiente: esa es una limitación clave con este método, ya que si el usuario está dibujando una línea recta, se tambalearán un poco, por lo que parece un caso de uso común.
T. Kiley
@Dancrumb solo tiene en cuenta la distancia promedio desde la línea, o la "distancia máxima", cualquier punto es desde la línea. Luego puede ponderar el algoritmo hacia líneas más tambaleantes con amplitudes de desviación más pequeñas, y lejos de las líneas que se alejan del camino esperado.
Superdoggy
2
@Dancrumb me parece que esto podría terminar siendo un beneficio para el caso de uso del OP. Las líneas dibujadas a mano, por supuesto, tendrán pequeñas desviaciones. Este enfoque podría funcionar para amortiguar el efecto de estas diferencias esperadas.
2
@ user3637362 tiene un error en su código. Una posible explicación es que olvidó tener en cuenta la distancia entre el punto inicial y el primer punto o el punto final y el último punto, pero sin mirar su código es imposible saber cuál podría ser su error.
Philipp
31

Esta podría no ser la mejor manera de implementar esto tampoco, pero sugiero que un RMSD ( desviación cuadrática media raíz) podría ser mejor, que simplemente el método de distancia, en los casos mencionados por Dancrumb (ver las dos primeras líneas a continuación).

RMSD = sqrt(mean(deviation^2))

Nota:

  • La suma de las desviaciones absolutas (tipo integral) podría ser mejor, ya que no promedia los errores positivos con los negativos. ( =sum(abs(deviation)))
  • Probablemente tendría que buscar la distancia más corta a la línea lineal si hay una forma que crea distancias más cortas que soltar la perpendicular.

dibujo

(Por favor, disculpe la baja calidad de mi dibujo)

Como ves, tienes que

  1. encuentre un vector ortogonal a su línea ( punto-producto es igual a 0 ).
    Si su línea apunta hacia (1, 3) lo que desea (3, -1)(a través del origen cada uno)
  2. Mida las distancias h desde la línea ideal hasta la del usuario, paralelas a ese vector.
  3. Calcule el RMSD o la suma de las diferencias absolutas.
gr4nt3d
fuente
La respuesta de Joel Bosveld indica un caso interesante: una línea casi perfectamente recta con esquinas al principio y al final. Si el usuario traza la línea libremente, esto es realmente un problema. Sin embargo, creo que este método podría cubrir ese escenario. En realidad, uno podría realizar un ajuste con RMSD o Integral absoluta como un valor máximo minimizado. Los valores iniciales pueden ser los puntos inicial y final. Como la longitud no importa, también es irrelevante si la optimización mueve los puntos para que la línea ideal se extienda más o sea más corta (la altura debe calcularse a ese nivel).
gr4nt3d
1
Otro caso que esto no parece cubrir: digamos que cada punto medido está en el eje x, pero la línea invierte la dirección varias veces. Esto devolverá un error de 0.
dave mankoff
23

Las respuestas existentes no tienen en cuenta que los puntos finales son arbitrarios (en lugar de dados). Por lo tanto, al medir la rectitud de la curva, no tiene sentido usar los puntos finales (por ejemplo, para calcular la longitud, el ángulo, la posición esperados). Un ejemplo simple sería una línea recta con ambos extremos doblados. Si medimos usando la distancia desde la curva y la línea recta entre los puntos finales, esto será bastante grande, ya que la línea recta que hemos dibujado está desplazada de la línea recta entre los puntos finales.

¿Cómo sabemos qué tan recta es la curva? Suponiendo que la curva es lo suficientemente suave, queremos saber cuánto, en promedio, está cambiando la tangente a la curva. Para una línea, esto sería cero (ya que la tangente es constante).

Si dejamos que la posición en el tiempo t sea (x (t), y (t)), entonces la tangente es (Dx (t), Dy (t)), donde Dx (t) es la derivada de x en el tiempo t (este sitio parece no tener soporte para TeX). Si la curva no está parametrizada por la longitud del arco, normalizamos dividiendo entre || (Dx (t), Dy (t)) ||. Entonces tenemos un vector unitario (o ángulo) de la tangente a la curva en el tiempo t. Entonces, el ángulo es a (t) = (Dx (t), Dy (t)) / || (Dx (t), Dy (t)) ||

Entonces estamos interesados ​​en || Da (t) || ^ 2 integrado a lo largo de la curva.

Dado que lo más probable es que tengamos puntos de datos discretos en lugar de una curva, debemos usar diferencias finitas para aproximar las derivadas. Entonces, Da (t) se convierte (a(t+h)-a(t))/h. Y, a (t) se convierte ((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)/||((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)||. Luego obtenemos S sumando h||Da(t)||^2todos los puntos de datos y posiblemente normalizándolos por la longitud de la curva. Lo más probable es que lo usemos h=1, pero en realidad es solo un factor de escala arbitrario.

Para reiterar, S será cero para una línea y más grande cuanto más se desvía de una línea. Para convertir al formato requerido, use 1/(1+S). Dado que la escala es algo arbitraria, es posible multiplicar S por algún número positivo (o transformarlo de alguna otra manera, por ejemplo, usar bS ^ c en lugar de S) para ajustar qué tan rectas son ciertas curvas.

Joel Bosveld
fuente
2
Esta es la definición más sensata de rectitud.
Marca Thomas el
1
Esta es, con mucho, la respuesta más sensata y estoy seguro de que los demás se volverían muy frustrantes. Desafortunadamente, la forma en que se presenta la solución es un poco más oscura que las otras, pero recomendaría que el OP persista.
Dan Sheppard
En general, también creo que esta respuesta es la mejor. Aunque me molesta un problema: ¿qué sucede si la línea no es "lo suficientemente suave"? Por ejemplo, si tiene dos segmentos de línea perfectamente rectos con un ángulo de, digamos, 90 °. ¿Estoy equivocado o esto resultaría en un resultado bastante bajo en comparación con una línea lineal realmente suave? (Creo que el caso de usuario de Dancrumb con una línea tambaleante fue un problema similar) ... Sin embargo, a nivel local, esta es la mejor manera.
gr4nt3d
3

Este es un sistema basado en cuadrícula, ¿verdad? Encuentra tus propios puntos para la línea y calcula la pendiente de la línea. Ahora, usando ese cálculo, determine los puntos válidos por los que pasaría la línea, dado un margen de error del valor exacto.

A través de una pequeña cantidad de pruebas de prueba y error, determine qué cantidad buena y mala de puntos coincidentes existiría y configure su juego usando una escala para obtener los mismos resultados de sus pruebas.

es decir, una línea corta con pendiente casi horizontal puede tener 7 puntos por los que podría dibujar. Si puede igualar consistentemente 6 o más de los 7 que se determinó que son parte de la línea recta, entonces ese sería el puntaje más alto. La calificación de longitud y precisión debe ser parte de la puntuación.

Arquero
fuente
3

Una medida muy fácil e intuitiva es el área entre la línea recta que mejor se ajusta y la curva real. Determinar esto es bastante sencillo:

  1. Utilice un ajuste de mínimos cuadrados en todos los puntos (esto evita el problema de doblez final mencionado por Joel Bosveld).
  2. Para todos los puntos en la curva, determine la distancia a la línea. Este también es un problema estándar. (álgebra lineal, transformación de base).
  3. Suma todas las distancias.
MSalters
fuente
¿Podría importarle si le pido una codificación de texto (JS, C #) o un pseudocódigo, ya que la mayoría de las respuestas anteriores se describen en teoría, no sé cómo comenzar?
user3637362
1
@ user3637362: StackOverflow tiene respuestas prácticas: stackoverflow.com/questions/6195335/… stackoverflow.com/questions/849211/…
MSalters
2

La idea es mantener todos los puntos que tocó el usuario, luego evaluar y sumar la distancia entre cada uno de esos puntos a la línea formada cuando el usuario suelta la pantalla.

Aquí hay algo para comenzar con el pseudocódigo:

bool mIsRecording = false;
point[] mTouchedPoints = new point[];

function onTouch
  mIsRecording = true

functon update
  if mIsRecording
    mTouchedPoints.append(currentlyTouchedLocation)

function onRelease
  mIsRecording = false

  cumulativeDistance = 0

  line = makeLine( mTouchedPoints.first, mTouchedPoints.last )

  for each point in mTouchedPoints:
    cumulativeDistance = distanceOfPointToLine(point, line)

  mTouchedPoints = new point[]

Lo que cumulativeDistancepodría darte una idea sobre el ajuste. Una distancia de 0 significaría que el usuario estaba en línea recta todo el tiempo. Ahora tendría que hacer algunas pruebas para ver cómo se comporta en su contexto. Y es posible que desee amplificar el valor devuelto al distanceOfPointToLinecuadrarlo para penalizar más las grandes distancias de la línea.

No estoy familiarizado con la unidad, pero el código updateaquí puede ir en una onDragfunción.

Y es posible que desee agregar un código en algún lugar para evitar registrar un punto si es el mismo que el último registrado. No desea registrar cosas cuando el usuario no se mueve.

Vaillancourt
fuente
55
Cuando suma la distancia entre la línea ideal y el punto para cada punto medido, debe tener en cuenta la cantidad de medidas que tomó, de lo contrario, cuando el usuario dibuje más lento o use un dispositivo con una velocidad de escaneo más rápida, registrarán más puntos, lo que significa que obtendrán una puntuación peor.
Philipp
@Philipp ¡Sí, lo haces! Debo admitir que tu forma de hacerlo parece mejor que la mía: P
Vaillancourt
Creo que este enfoque mejora al tomar la distancia promedio , en lugar de la distancia acumulativa.
Dancrumb
@Dancrumb Realmente, depende de las necesidades, pero sí, esa sería una forma de hacerlo.
Vaillancourt
2

Un método que podría usar es subdividir la línea en segmentos y hacer un producto de puntos vectoriales entre cada vector que representa el segmento y un vector que representa una línea recta entre el primer y el último punto. Esto tiene el beneficio de permitirle encontrar segmentos extremadamente "puntiagudos" fácilmente.

Editar:

Además, consideraría usar la longitud del segmento además del producto punto. Un vector muy corto pero ortogonal debe contar menos que uno largo que tenga menos desviación.

Kik
fuente
1

Lo más fácil y rápido podría ser simplemente descubrir qué tan gruesa debería ser la línea para cubrir todos los puntos de la línea dibujada por el usuario.

Cuanto más gruesa sea la línea, peor será el usuario al dibujar su línea.

Adam Davis
fuente
0

De alguna manera, refiriéndome a MSalters Answer, aquí hay información más específica.

Use el método de mínimos cuadrados para ajustar una línea para sus puntos. Básicamente está buscando una función y = f (x) que se ajuste mejor. Una vez que lo tenga, puede usar los valores reales de y para sumar el cuadrado de las diferencias:

s = suma sobre ((yf (x)) ^ 2)

Cuanto más pequeña es la suma, más recta es la línea.

Aquí se explica cómo obtener la mejor aproximación: http://math.mit.edu/~gs/linearalgebra/ila0403.pdf

Acabo de leer de "Ajustar una línea recta". Tenga en cuenta que t se usa en lugar de x y b en lugar de y. C y D se determinarán como aproximación, entonces usted tiene f (x) = C + Dx

Nota adicional: Obviamente, también debe tener en cuenta la longitud de la línea. Cada línea que consta de 2 puntos será perfecta. No sé el contexto exacto, pero creo que usaría la suma de cuadrados dividida por el número de puntos como calificación. También agregaría el requisito de una longitud mínima, un número mínimo de puntos. (Tal vez alrededor del 75% de la longitud máxima)

philipp
fuente