¿Cómo puedo verificar si una línea dibujada por un jugador sigue un camino?

8

Quiero dibujar un camino invisible que el usuario debe seguir. He almacenado ese camino como puntos. Cuando un jugador dibuja una línea, ¿cómo puedo probar si sigue la ruta que he almacenado?

Aquí hay un ejemplo para rastrear la letra A.

ejemplo de traza

if((traitSprite.getX()<=Invisible.X  && traitSprite.getX()>=Invisible.X )){...}

( traitSpritees un sprite)

Androide
fuente
¿Cómo almacena el camino que debe seguir la línea dibujada del jugador? ¿Es eso lo que es el sprite?
Anko
no, son puntos que ingresé manualmente. es una mala idea, pero creo que el uso de "Vector2" será una solución efectiva, pero realmente no sé cómo usarlo.
Android

Respuestas:

12

Aquí hay una solución basada en vectores. No lo he probado, pero parece estar bien conceptualmente.

Teoría

Supongo que has almacenado la forma como segmentos de línea. Aquí está la letra A representada con tres segmentos de línea.

segmentos de línea que representan una letra

Supuse que las rutas en el dibujo del usuario se almacenan como listas de puntos.

Podemos "inflar" esos segmentos de línea para permitir un margen de error al verificar la proximidad : si la ruta dibujada del usuario está cerca del margen de error de las líneas correctas.

segmentos de línea "inflados" ruta dibujada por el usuario en la parte superior de la carta con márgenes de error

Sin embargo, eso solo no es suficiente. También tenemos que verificar la cobertura : si el dibujo del usuario "cubre" una gran fracción de la forma. Estos dibujos son malos, porque a pesar de que se ajustan al margen de error, les falta parte de la letra:

malos dibujos

Si verificamos ambas cosas, podemos aproximarnos si el dibujo del jugador es bueno.

Implementación

Verificar la cercanía solo significa para cada punto de ruta del usuario, encontrar la distancia entre esa y cada línea que forma la letra, tomar la más baja y verificar que sea menor que el margen de error.

Verificar la cobertura es más complicado, pero puede obtener una muy buena aproximación con las matemáticas vectoriales si para cada segmento de línea, encuentra la ruta dibujada por el usuario más cercana (verde) y proyecta sus partes (verde oscuro) en ese segmento de línea (negro), luego verifique qué tan bien lo cubren los vectores proyectados (azul):

verificación de cobertura por proyección vectorial

Para proyectar un vector asobre otro vector b, haga

projection = dotProduct(a, b) / lengthSquared(b) * b

donde dotProductcalcula el producto punto de los dos vectores y lengthSquaredes lo que parece. Básicamente, esto encuentra el valor escalar de cuánto ava en bla dirección y se multiplica bpor eso para obtener un vector en la misma dirección. (El tutorial de detección de colisión de Metanet Software A tiene una buena visualización de esto en el Apéndice A § proyección ).

La dirección del vector proyectado podría no ser realmente importante. Si solo suma las longitudes de los vectores proyectados y los compara con la longitud total del segmento de línea, eso le indicará qué fracción está cubierta. (Excepto en casos extraños, ver § Limitaciones a continuación).

En la imagen de arriba, la ruta cubriría aproximadamente la mitad del segmento. Puede elegir cualquier valor de tolerancia que desee.

Limitaciones

Letras curvas

Los segmentos de línea son sub ideal: ¡muchas letras son curvas! ¿Cómo se representa una 'P' o una 'O'?

Podría usar muchos segmentos de línea (tal vez con un margen de error mayor).

letra P aproximada con segmentos de línea letra O aproximada con segmentos de línea

También podría comenzar a usar curvas de Bézier en lugar de líneas para un ajuste más cercano, pero tenga en cuenta que encontrar el punto más cercano en un Bézier es mucho más complejo, al igual que muchas otras operaciones de medición.

Desajustes

Los márgenes de tolerancia demasiado relajados para la distancia de las líneas y la cobertura de la carta podrían tener consecuencias no deseadas.

Por ejemplo, el jugador podría haber estado tratando de dibujar una 'H' aquí.

una letra H erróneamente reconocida como A

Bucles y superposiciones

bucle y superposición en (posiblemente) letra reconocida

Los bucles o superposiciones en la ruta dibujada por el jugador pueden hacer que algunas partes del dibujo se cuenten dos veces al proyectarlas en el segmento de línea más cercano.

Esto podría solucionarse haciendo un procesamiento más elegante en los vectores proyectados, tal vez almacenando exactamente dónde estaría el vector proyectado (almacene también la dirección de la proyección y el punto más cercano en el segmento de línea al punto en la línea dibujada por el jugador) , luego rechaza los nuevos que se superponen.

Si el jugador dibujó un solo camino y se procesó comenzando en el extremo marcado con el círculo azul, las partes verdes de ese camino serían aceptadas y las rojas rechazadas, porque su proyección se superpondría con algunas partes procesadas anteriormente.

rechazar bucles y superposiciones

La implementación tiene muchas sutilezas técnicas que probablemente pertenecerían a una pregunta diferente.

Jugadores aventureros impredecibles

Un jugador puede dibujar algo extraño que todavía pasa .

trolololol

¡Aunque podrías llamar a eso una característica! :)

Anko
fuente
gracias, ¿qué propones no dibujar fuera de la carta?
Android
@ Android Los "márgenes de error" naranjas son para eso. Podría rechazar líneas que salen de ellas: como esta, por ejemplo.
Anko
Lo que quiero es hacer la letra como SpriteBatch, entonces la única área donde puedo dibujar es ese lote de sprites, que puede tomar la forma de A o B, X ... ¿es esto posible? si es así, ¿cómo puedo hacer una textura como un SpriteBatch? Y gracias por adelantado.
Android
2

tl; dr Sugiero hacer que la pintura con pincel de los jugadores sea un plano 2D visible (o invisible). Difunde la imagen pintada de los usuarios con el origen (la silueta deseada o el modelo 2D). Si desea aumentar la precisión, haga que las líneas de guía y el pincel sean más estrechas, para permitir más margen de error, haga que el pincel y el diseño sean más gruesos.

De lo contrario, podría medir la distancia de cada (x, y) en la que los usuarios hacen clic / tocan desde la spline calculando la distancia punto a segmento. Luego puede promediar las distancias para componer una medida de precisión y eficiencia. Se requerirá más trabajo para obtener una medida significativa de finalización y darse cuenta de la eficacia del desempeño del usuario.


Consideración: sugiero no hacerlo (comprobar directamente si una línea sigue una ruta). Posiblemente sea una mala idea. Parece que quieres que el usuario rellene una silueta. El camino en sí es una spline (esquelética) que representa la silueta.

Si simplemente hace que el pincel de los jugadores aplique una masa monocromática pulposa de píxeles al plano 2D, puede ejecutar un proceso en segundo plano que verifique cuántos píxeles hay dentro de la silueta y cuántos de ellos están afuera. Esto puede resultar fácilmente en un% de éxito, donde la cantidad de% del patrón es una estadística de interés y otra es la cantidad de porcentaje que está fuera de los límites del modelo. Si verifica las distancias del subsegmento, no está muy claro si el trabajo de los usuarios es exacto.

AturSams
fuente
1

La mejor solución es no usar gráficos, ¡hazlo con las matemáticas!

Puede comprender fácilmente cuánto cada punto (pintado por el usuario) está lejos del segmento /programming/849211/shortest-distance-between-a-point-and-a-line-segment

Que puede calcular el error promedio, así que mida cuánto usuario está correcto.

Alexsey Shestacov
fuente
gracias, pero ¿qué pasa con letras como "C" "O"? ... no hay una distancia fija entre los puntos ..
Android
Puede hacer "C" y "O" de 6-8 segmentos de línea, al igual que otros, pero las matemáticas serán ligeramente diferentes, en términos de
medición de