Comment puis-je quantifier la rectitude d'une ligne?

Je travaille sur un jeu qui demande aux joueurs de tracer une ligne d'un point A (x1, y1) à l'autre point B (x2, y2) sur l'écran d'un appareil Android.

Je veux savoir à quel point ce dessin correspond à une ligne droite. Par exemple, un résultat de 90% signifie que le dessin correspond presque parfaitement à la ligne. Si les joueurs dessinent une ligne courbe de A à B, le score devrait être faible.

Les points finaux ne sont pas connus à l'avance. Comment puis-je faire ceci?

Une ligne parfaitement droite serait également la ligne la plus courte possible avec une longueur totale de sqrt((x1-x2)² + (y1-y2)²). Une ligne plus scribbly sera une connexion moins idéale et sera donc inévitablement plus longue.

Lorsque vous prenez tous les points individuels du chemin tracé par l'utilisateur et que vous récapitulez les distances qui les séparent, vous pouvez comparer la longueur totale à la longueur idéale. Plus la longueur totale divisée par la longueur idéale est petite, meilleure est la ligne.

Voici une visualisation. Lorsque les points noirs sont les points finaux du geste et les points bleus sont les points que vous avez mesurés pendant le geste, vous calculez et additionnez les longueurs des lignes vertes et divisez-les par la longueur de la ligne rouge:

Un score ou un indice de sinuosité de 1 serait parfait, tout ce qui est plus élevé serait moins parfait, tout ce qui se situe sous 1 serait un bug. Si vous préférez avoir le score en pourcentage, divisez 100% par ce nombre.

Ce n'est peut-être pas la meilleure façon de mettre en œuvre cela non plus, mais je suggère qu'un écart-type ( RMSD ) pourrait être meilleur que la simple méthode de la distance, dans les cas mentionnés par Dancrumb (voir les deux premières lignes ci-dessous).

RMSD = sqrt(mean(deviation^2))

Remarque:

• La somme des déviations absolues (de type intégrale) pourrait être meilleure, car elle ne fait pas la moyenne des erreurs positives avec des négatives. ( =sum(abs(deviation)))
• Vous devrez probablement rechercher la distance la plus courte de la ligne linéaire s’il existe un moyen de créer des distances plus courtes que la chute de la perpendiculaire.

(Veuillez excuser la mauvaise qualité de mon dessin)

Comme vous le voyez, vous devez

1. trouvez un vecteur orthogonal à votre ligne ( produit-points égal à 0 ).
   Si votre ligne pointe vers (1, 3) vous voudriez (3, -1)(par l'origine chacun)
2. Mesurez les distances h entre la ligne idéale et la ligne utilisateur, parallèlement à ce vecteur.
3. Calculez le RMSD ou la somme des différences absolues.

Les réponses existantes ne tiennent pas compte du fait que les points finaux sont arbitraires (plutôt que donnés). Ainsi, lors de la mesure de la rectitude de la courbe, il n’est pas logique d’utiliser les points finaux (par exemple, pour calculer la longueur, l’angle, la position attendus). Un exemple simple serait une ligne droite avec les deux extrémités coupées. Si nous mesurons en utilisant la distance de la courbe et la ligne droite entre les points extrêmes, celle-ci sera assez grande, car la ligne droite que nous avons tracée est décalée par rapport à la ligne droite entre les points extrêmes.

Comment pouvons-nous dire à quel point la courbe est droite? En supposant que la courbe soit suffisamment lisse, nous voulons savoir dans quelle mesure la tangente à la courbe change en moyenne. Pour une ligne, ce serait zéro (car la tangente est constante).

Si on laisse la position à l'instant t être (x (t), y (t)), alors la tangente est (Dx (t), Dy (t)), où Dx (t) est la dérivée de x à l'instant t (ce site semble manquer du support TeX). Si la courbe n'est pas paramétrée par la longueur de l'arc, on normalise en divisant par || (Dx (t), Dy (t)) ||. Nous avons donc un vecteur unitaire (ou angle) de la tangente à la courbe au temps t. Donc, l'angle est a (t) = (Dx (t), Dy (t)) / || (Dx (t), Dy (t)) ||

Nous sommes alors intéressés par || Da (t) || ^ 2 intégré le long de la courbe.

Étant donné que nous avons très probablement des points de données discrets plutôt qu'une courbe, nous devons utiliser des différences finies pour approximer les dérivées. Alors, Da (t) devient (a(t+h)-a(t))/h. Et a (t) devient ((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)/||((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)||. Nous obtenons ensuite S en faisant la somme h||Da(t)||^2de tous les points de données et en normalisant éventuellement par la longueur de la courbe. Très probablement, nous utilisons h=1, mais c'est vraiment un facteur d'échelle arbitraire.

Pour réitérer, S sera zéro pour une ligne et plus grand, plus il s'écarte d'une ligne. Pour convertir au format requis, utilisez 1/(1+S). Étant donné que l'échelle est quelque peu arbitraire, il est possible de multiplier S par un nombre positif (ou de le transformer d'une autre manière, par exemple, utilisez bS ^ c au lieu de S) pour ajuster la droite de certaines courbes.

Ceci est un système basé sur une grille, non? Trouvez vos propres points pour la ligne et calculez la pente de la ligne. Maintenant, en utilisant ce calcul, déterminez les points valides que la ligne passerait, compte tenu de la marge d’erreur de la valeur exacte.

À travers une courte quantité d'essais et d'essais, déterminez quelle quantité de points de correspondance existerait bonne et mauvaise et configurez votre jeu en utilisant une échelle pour obtenir les mêmes résultats que vos tests.

C'est-à-dire qu'une ligne courte avec une pente presque horizontale peut avoir 7 points que vous pourriez tracer. Si vous pouvez toujours faire correspondre 6 ou plus des 7 qui ont été identifiés comme faisant partie de la ligne droite, alors ce serait le score le plus élevé. La notation pour la longueur et la précision devrait faire partie de la notation.

Une mesure très simple et intuitive est la surface entre la droite la mieux ajustée et la courbe réelle. Déterminer cela est assez simple:

1. Utilisez un ajustement des moindres carrés sur tous les points (cela évite le problème de kink final évoqué par Joel Bosveld).
2. Pour tous les points de la courbe, déterminez la distance à la ligne. C'est aussi un problème standard. (algèbre linéaire, transformation de base.)
3. Somme toutes les distances.

L'idée est de conserver tous les points touchés par l'utilisateur, puis d'évaluer et de faire la somme de la distance entre chacun de ces points et la ligne formée lorsque l'utilisateur relâche l'écran.

Voici quelque chose pour vous aider à démarrer en pseudo-code:

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[]

Ce qui cumulativeDistancepourrait vous donner une idée sur le raccord. Une distance de 0 signifierait que l'utilisateur était en ligne droite tout le temps. Vous devez maintenant faire quelques tests pour voir comment il se comporte dans votre contexte. Et vous voudrez peut-être amplifier la valeur renvoyée en le distanceOfPointToLineplaçant au carré pour pénaliser davantage les grandes distances de la ligne.

Je ne suis pas familier avec l'unité, mais le code updateici peut entrer dans une onDragfonction.

Et vous voudrez peut-être ajouter quelque part dans le code pour empêcher l'enregistrement d'un point s'il est identique au dernier enregistré. Vous ne voulez pas enregistrer des choses quand l'utilisateur ne bouge pas.

Une méthode que vous pouvez utiliser consiste à subdiviser la ligne en segments et à créer un produit vectoriel entre chaque vecteur représentant le segment et un vecteur représentant une ligne droite entre le premier et le dernier point. Cela a l’avantage de vous permettre de trouver facilement des segments extrêmement "hérissés".

Modifier:

En outre, je considérerais d'utiliser la longueur du segment en plus du produit scalaire. Un vecteur très court mais orthogonal devrait compter moins qu'un long qui présente moins d'écart.

Le plus simple et le plus rapide serait peut-être simplement de déterminer l'épaisseur de la ligne pour couvrir tous les points de la ligne dessinée par l'utilisateur.

Plus la ligne doit être épaisse, plus l'utilisateur a du mal à dessiner sa ligne.

En quelque sorte, faisant référence à MSalters Answer, voici quelques informations plus spécifiques.

Utilisez la méthode des moindres carrés pour ajuster une ligne à vos points. Vous recherchez essentiellement une fonction y = f (x) qui convient le mieux. Une fois que vous l'avez, vous pouvez utiliser les valeurs y réelles pour additionner le carré des différences:

s = somme sur ((yf (x)) ^ 2)

Plus la somme est petite, plus la ligne est droite.

Comment obtenir la meilleure approximation, est expliqué ici: http://math.mit.edu/~gs/linearalgebra/ila0403.pdf

Il suffit de lire "d'ajuster une ligne droite". Notez que t est utilisé à la place de x et b à la place de y. C et D doivent être déterminés comme approximation, alors vous avez f (x) = C + Dx

Remarque supplémentaire: Évidemment, vous devez également prendre en compte la longueur de la ligne. Chaque ligne composée de 2 points sera parfaite. Je ne connais pas le contexte exact, mais j'imagine que j'utiliserais la somme des carrés divisée par le nombre de points pour l'évaluation. J'ajouterais également l'exigence d'une longueur minimale, d'un nombre minimal de points. (Peut-être environ 75% de la longueur maximale)