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

37

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?

utilisateur3637362
la source
1
Savez-vous à l'avance quels sont vos deux points finaux? Ou est-il déterminé au moment où l'utilisateur cesse de toucher l'écran?
Vaillancourt
Désolé si ma description n'est pas claire pour vous. Eh bien, le point de départ A (x, y) correspond au premier contact et le point final B (x, y) correspond au moment où nous avons quitté l'écran tactile, comme vous l'avez dit.
user3637362
Nous avons une question connexe sur la correspondance des lettres dessinées par les joueurs .
Anko
3
S'il vous plaît, ne postez pas d'images pour le code source à l'avenir.
Josh
1
@ user3637362 Je comprends que vous démarrez j=1pour pouvoir comparer touchList[j]avec touchList[j-1], mais quand touch.phase == TouchPhase.Beganou touch.phase == TouchPhase.Endedles positions ne sont pas ajoutées touchListet, par la suite, ne sont pas incluses dans sumLength. Ce bug serait présent dans tous les cas mais serait plus apparent lorsque la ligne a peu de segments.
Kelly Thomas

Réponses:

52

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:

entrez la description de l'image ici

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.

Philipp
la source
34
Cette approche pose un petit problème en ce sens que les polylignes de même longueur ne sont pas également «droites». Une ligne qui vacille avec une faible déviation (mais plusieurs fois) par rapport à la ligne droite est «plus droite» qu'une ligne de longueur égale qui dévie d'un point à l'autre puis revient en arrière.
Dancrumb
Je ne peux pas assez commenter @Dancrumbs - c'est une limitation essentielle avec cette méthode, car si l'utilisateur trace une ligne droite, il vacillera un peu, ce qui ressemble à un cas d'utilisation courant.
T. Kiley
@Dancrumb suffit de prendre en compte la distance moyenne de la ligne ou de "la distance maximale" à un point quelconque de la ligne. Ensuite, vous pouvez pondérer l'algorithme en fonction de lignes plus instables, d'amplitudes de déviation plus faibles, et éloignées des lignes qui s'éloignent du chemin attendu.
Superdoggy
2
@Dancrumb, il me semble que cela pourrait être avantageux pour le cas d'utilisation du PO. Les lignes tracées à la main auront, bien sûr, de petites déviations. Cette approche pourrait effectivement atténuer l’effet de ces différences attendues.
2
@ user3637362 vous avez un bug dans votre code. Une explication possible est que vous avez oublié de prendre en compte la distance entre le point de départ et le premier point ou entre le point final et le dernier point, mais sans regarder votre code, il est impossible de dire quelle pourrait être votre erreur.
Philipp
31

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.

dessin

(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.
gr4nt3d
la source
La réponse de Joel Bosveld indique un cas intéressant: une ligne presque parfaitement droite avec des angles au début et à la fin. Si la ligne doit être tracée librement par l'utilisateur, c'est effectivement un problème. Néanmoins, je pense que cette méthode pourrait couvrir ce scénario. On pourrait en fait effectuer un ajustement avec RMSD ou Absolute absolu en tant que valeur top-be-minimized. Les valeurs de départ peuvent être les points de début et de fin. Comme la longueur n'a pas d'importance, il est également indifférent que l'optimisation déplace les points de sorte que la ligne idéale s'étende plus loin ou soit plus courte (la hauteur doit être calculée à ce niveau).
gr4nt3d
1
Un autre cas que cela ne semble pas couvrir: supposons que chaque point mesuré soit sur l’axe des x, mais que la ligne inverse la direction plusieurs fois. Cela retournera une erreur de 0.
dave mankoff
23

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.

Joel Bosveld
la source
2
C'est la définition la plus sensée de la rectitude.
Marcks Thomas
1
C’est de loin la réponse la plus sensée et je suis sûr que les autres deviendraient de plus en plus frustrants. Malheureusement, la forme sous laquelle la solution est présentée est un peu plus obscure que les autres, mais je recommanderais que l'OP persiste.
Dan Sheppard
De manière générale, je pense aussi que cette réponse est effectivement la meilleure. Bien qu'un problème me dérange: que se passe-t-il si la ligne n'est pas "suffisamment lisse"? Par exemple, si vous avez deux segments parfaitement droits avec un angle de, disons, de 90 °. Est-ce que je me trompe ou est-ce que cela donnerait un résultat assez faible comparé à une ligne linéaire vraiment lisse? (Je pense que le cas d'utilisation de Dancrumb avec une ligne bancale était un problème similaire) ... Localement, c'est la meilleure façon de procéder.
gr4nt3d
3

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.

Archer
la source
3

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.
MSalters
la source
Pourriez-vous vous déranger si je vous demande du codage de texte (JS, C #) ou un pseudo-code, car la plupart des réponses ci-dessus sont décrites en théorie, je ne sais pas comment commencer?
user3637362
1
@ user3637362: StackOverflow a des réponses pratiques: stackoverflow.com/questions/6195335/… stackoverflow.com/questions/849211/…
MSalters
2

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.

Vaillancourt
la source
5
Lorsque vous additionnez la distance entre la ligne idéale et le point pour chaque point mesuré, vous devez prendre en compte le nombre de mesures que vous avez prises. Sinon, lorsque l'utilisateur tire plus lentement ou utilise un périphérique avec un taux de balayage plus rapide, il s'enregistre davantage points ce qui signifie qu'ils obtiendront un score plus mauvais.
Philipp
@ Philippe Oui, vous le faites! Je dois avouer que ta façon de le faire semble meilleure que la mienne: P
Vaillancourt
Je pense que cette approche est améliorée en prenant la distance moyenne , plutôt que la distance cumulative.
Dancrumb
@Dancrumb Vraiment, cela dépend des besoins, mais oui, ce serait une façon de le faire.
Vaillancourt
2

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.

Kik
la source
1

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.

Adam Davis
la source
0

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)

philipp
la source