Wie kann ich die Geradheit einer gezeichneten Linie quantifizieren?

37

Ich arbeite an einem Spiel, bei dem die Spieler auf dem Bildschirm eines Android-Geräts eine Linie von einem Punkt A (x1, y1) zum anderen Punkt B (x2, y2) ziehen müssen.

Ich möchte herausfinden, wie gut diese Zeichnung zu einer geraden Linie passt. Zum Beispiel würde ein Ergebnis von 90% bedeuten, dass die Zeichnung fast perfekt zur Linie passt. Wenn die Spieler eine gekrümmte Linie von A nach B ziehen, sollte sie eine niedrige Punktzahl erhalten.

Die Endpunkte sind nicht im Voraus bekannt. Wie kann ich das machen?

user3637362
quelle
1
Wissen Sie im Voraus, was Ihre beiden Endpunkte sind? Oder wird festgestellt, wann der Benutzer den Bildschirm nicht mehr berührt?
Vaillancourt
Entschuldigung, wenn Ihnen meine Beschreibung nicht klar ist. Nun, der Startpunkt A (x, y) ist die erste Berührung und der Endpunkt B (x, y) ist der Zeitpunkt, an dem wir, wie Sie sagten, den Touchscreen verlassen haben.
user3637362
Wir haben eine verwandte Frage zu übereinstimmenden von Spielern gezogenen Buchstaben .
Anko
3
Bitte poste in Zukunft keine Bilder für den Quellcode.
Josh
1
@ user3637362 Ich verstehe , dass Sie beginnen , j=1so dass Sie vergleichen können touchList[j]mit touchList[j-1], aber wenn touch.phase == TouchPhase.Beganoder touch.phase == TouchPhase.Endeddie Positionen nicht hinzugefügt werden touchListund anschließend in nicht enthalten sumLength. Dieser Fehler ist in allen Fällen vorhanden, tritt jedoch deutlicher auf, wenn die Zeile nur wenige Segmente enthält.
Kelly Thomas

Antworten:

52

Eine perfekt gerade Linie wäre auch die kürzest mögliche Linie mit einer Gesamtlänge von sqrt((x1-x2)² + (y1-y2)²). Eine stärker kritzelnde Linie ist eine weniger ideale Verbindung und daher zwangsläufig länger.

Wenn Sie alle einzelnen Punkte des Pfades, den der Benutzer gezeichnet hat, nehmen und die Abstände zwischen ihnen aufsummieren, können Sie die Gesamtlänge mit der idealen Länge vergleichen. Je kleiner die Gesamtlänge geteilt durch die ideale Länge ist, desto besser ist die Linie.

Hier ist eine Visualisierung. Wenn die schwarzen Punkte die Endpunkte der Geste sind und die blauen Punkte die Punkte, die Sie während der Geste gemessen haben, berechnen und addieren Sie die Längen der grünen Linien und dividieren sie durch die Länge der roten Linie:

Bildbeschreibung hier eingeben

Ein Score oder Sinuosity-Index von 1 wäre perfekt, alles, was höher ist, wäre weniger perfekt, alles, was unter 1 liegt, wäre ein Fehler. Wenn Sie die Punktzahl lieber in Prozent haben möchten, dividieren Sie 100% durch diese Zahl.

Philipp
quelle
34
Bei diesem Ansatz besteht ein kleines Problem darin, dass Polylinien gleicher Länge nicht gleich "gerade" sind. Eine Linie, die mit geringer Abweichung (aber oftmals) um die Gerade wackelt, ist "gerader" als eine Linie gleicher Länge, die zu einem einzelnen Punkt und dann zurück abweicht.
Dancrumb
Ich kann @Dancrumbs-Kommentar nicht genug +1 geben - das ist eine ziemlich wichtige Einschränkung bei dieser Methode, da der Benutzer eine gerade Linie zeichnet, die ein wenig wackelt, sodass dies wie ein gewöhnlicher Anwendungsfall erscheint.
T. Kiley
@Dancrumb berücksichtigt nur den durchschnittlichen Abstand von der Linie oder den "maximalen Abstand", den ein Punkt von der Linie hat. Dann können Sie den Algorithmus in Richtung wackeligerer Linien mit kleineren Abweichungsamplituden und von Linien, die weit vom erwarteten Pfad entfernt sind, gewichten.
Superdoggy
2
@Dancrumb es klingt für mich so, als ob dies einen Vorteil für den Anwendungsfall des OP bedeuten könnte. Handgezeichnete Linien weisen natürlich kleine Abweichungen auf. Dieser Ansatz könnte tatsächlich funktionieren, um den Effekt dieser erwarteten Unterschiede zu dämpfen.
2
@ user3637362 Sie haben einen Fehler in Ihrem Code. Eine mögliche Erklärung ist, dass Sie vergessen haben, den Abstand zwischen dem Startpunkt und dem ersten Punkt oder dem Endpunkt und dem letzten Punkt zu berücksichtigen, aber ohne Ihren Code zu betrachten, ist es unmöglich zu sagen, was Ihr Fehler sein könnte.
Philipp
31

Dies ist möglicherweise auch nicht der beste Weg, dies zu implementieren. Ich schlage jedoch vor, dass eine RMSD (Root Mean Square Deviation) in den von Dancrumb genannten Fällen besser sein könnte als nur die Distanzmethode (siehe die ersten beiden Zeilen unten).

RMSD = sqrt(mean(deviation^2))

Hinweis:

  • Die Summe der absoluten Abweichungen (ganzzahlig) könnte besser sein, da positive Fehler nicht mit negativen Fehlern gemittelt werden. ( =sum(abs(deviation)))
  • Sie müssten wahrscheinlich den kürzesten Abstand zur linearen Linie suchen, wenn es einen Weg gibt, der kürzere Abstände schafft als das Ablegen der Senkrechten.

Zeichnung

(Bitte entschuldigen Sie die schlechte Qualität meiner Zeichnung)

Wie Sie sehen, müssen Sie

  1. Finden Sie einen orthogonalen Vektor zu Ihrer Linie ( Punktprodukt ist gleich 0 ).
    Wenn Ihre Linie in die Richtung zeigt, in die (1, 3) Sie möchten (3, -1)(jeweils durch den Ursprung)
  2. Messen Sie den Abstand h von der Ideallinie zum Benutzer parallel zu diesem Vektor.
  3. Berechnen Sie den Effektivwert oder die Summe der absoluten Differenzen.
gr4nt3d
quelle
Die Antwort von Joel Bosveld weist auf einen interessanten Fall hin: eine fast perfekt gerade Linie mit Ecken am Anfang und Ende. Wenn die Linie vom Benutzer frei gezogen werden soll, ist dies in der Tat ein Problem. Dennoch denke ich, dass diese Methode dieses Szenario abdecken könnte. Man könnte tatsächlich eine Anpassung mit RMSD oder absolutem Integral als einen zu minimierenden Wert durchführen. Startwerte können Start- und Endpunkte sein. Da die Länge keine Rolle spielt, ist es auch unerheblich, ob die Optimierung die Punkte so verschiebt, dass die Ideallinie weiter oder kürzer herausragt (die Höhe muss auf dieses Niveau berechnet werden).
gr4nt3d
1
Ein anderer Fall, den dies nicht zu behandeln scheint: Angenommen, jeder gemessene Punkt liegt auf der x-Achse, aber die Linie kehrt die Richtung mehrmals um. Dies wird einen Fehler von 0 zurückgeben.
Dave Mankoff
23

Bestehende Antworten berücksichtigen nicht, dass die Endpunkte willkürlich sind (anstatt gegeben). Daher ist es bei der Messung der Geradheit der Kurve nicht sinnvoll, die Endpunkte zu verwenden (z. B. um die erwartete Länge, den Winkel und die Position zu berechnen). Ein einfaches Beispiel wäre eine gerade Linie, bei der beide Enden geknickt sind. Wenn wir den Abstand von der Kurve und der geraden Linie zwischen den Endpunkten messen, ist dieser ziemlich groß, da die gerade Linie, die wir gezeichnet haben, von der geraden Linie zwischen den Endpunkten versetzt ist.

Wie erkennen wir, wie gerade die Kurve ist? Unter der Annahme, dass die Kurve glatt genug ist, möchten wir wissen, um wie viel sich die Tangente an die Kurve im Durchschnitt ändert. Für eine Linie wäre dies Null (da die Tangente konstant ist).

Wenn wir die Position zum Zeitpunkt t (x (t), y (t)) sein lassen, dann ist der Tangens (Dx (t), Dy (t)), wobei Dx (t) die Ableitung von x zum Zeitpunkt t ist (Diese Seite scheint keine Unterstützung für TeX zu haben). Wenn die Kurve nicht durch die Bogenlänge parametrisiert ist, normieren wir durch Teilen durch || (Dx (t), Dy (t)) ||. Wir haben also einen Einheitsvektor (oder Winkel) der Tangente an die Kurve zum Zeitpunkt t. Der Winkel ist also a (t) = (Dx (t), Dy (t)) / || (Dx (t), Dy (t)) ||

Wir interessieren uns dann für || Da (t) || ^ 2, das entlang der Kurve integriert ist.

Da wir höchstwahrscheinlich eher diskrete Datenpunkte als eine Kurve haben, müssen wir endliche Differenzen verwenden, um die Ableitungen zu approximieren. Also wird Da (t) (a(t+h)-a(t))/h. Und a (t) wird ((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)/||((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)||. Dann erhalten wir S, indem wir h||Da(t)||^2für alle Datenpunkte summieren und möglicherweise durch die Länge der Kurve normalisieren. Am wahrscheinlichsten verwenden wir h=1, aber es ist wirklich nur ein willkürlicher Skalierungsfaktor.

Um es noch einmal zu wiederholen: S ist für eine Linie Null und größer, je mehr sie von einer Linie abweicht. In der gewünschten Format, Verwendung zu konvertieren 1/(1+S). Da die Skalierung etwas willkürlich ist, ist es möglich, S mit einer positiven Zahl zu multiplizieren (oder auf andere Weise zu transformieren, z. B. mit bS ^ c anstelle von S), um die Geradheit bestimmter Kurven anzupassen.

Joel Bosveld
quelle
2
Dies ist die vernünftigste Definition von Geradheit.
Marcks Thomas
1
Dies ist bei weitem die vernünftigste Antwort und ich bin sicher, dass die anderen sehr frustrierend werden würden. Leider ist die Form, in der die Lösung präsentiert wird, etwas unklarer als die anderen, aber ich würde empfehlen, dass das OP bestehen bleibt.
Dan Sheppard
Generell halte ich diese Antwort auch für die beste. Obwohl mich ein Problem stört: Was passiert, wenn die Leitung nicht "glatt genug" ist? Wenn Sie beispielsweise zwei perfekt gerade Liniensegmente mit einem Winkel von beispielsweise 90 ° haben. Täusche ich mich oder würde dies zu einem ziemlich niedrigen Ergebnis führen, verglichen mit einer wirklich glatten linearen Linie? (Ich denke, Dancrumbs Anwenderfall mit einer wackeligen Linie war ein ähnliches Problem) ... Vor Ort ist dies jedoch der beste Weg.
gr4nt3d
3

Dies ist ein gitterbasiertes System, oder? Finden Sie Ihre eigenen Punkte für die Linie und berechnen Sie die Neigung der Linie. Bestimmen Sie nun anhand dieser Berechnung gültige Punkte, durch die die Linie verlaufen würde, wenn eine gewisse Fehlerquote gegenüber dem exakten Wert besteht.

Bestimmen Sie anhand einer kurzen Anzahl von Testversuchen, welche Anzahl von guten und welche Anzahl von schlechten Übereinstimmungspunkten vorhanden sind, und richten Sie Ihr Spiel anhand einer Skala aus, die dieselben Ergebnisse wie Ihre Tests liefert.

Das heißt, eine kurze Linie mit fast horizontaler Neigung kann 7 Punkte haben, durch die Sie zeichnen können. Wenn Sie konsequent 6 oder mehr der 7 übereinstimmen können, die als Teil der geraden Linie bestimmt wurden, ist dies die höchste Punktzahl. Die Bewertung der Länge und Genauigkeit sollte Teil der Bewertung sein.

Bogenschütze
quelle
3

Ein sehr einfaches und intuitives Maß ist der Bereich zwischen der am besten passenden Geraden und der tatsächlichen Kurve. Dies zu bestimmen ist ziemlich einfach:

  1. Verwenden Sie eine Least-Squares-Anpassung für alle Punkte (dies verhindert das von Joel Bosveld erwähnte End-Kink-Problem).
  2. Bestimmen Sie für alle Punkte auf der Kurve den Abstand zur Linie. Dies ist auch ein Standardproblem. (Lineare Algebra, Basistransformation.)
  3. Summiere alle Entfernungen.
MSalters
quelle
Könnte es Ihnen etwas ausmachen, wenn ich Sie nach Textcodierung (JS, C #) oder Pseudocode frage, da die meisten Antworten theoretisch beschrieben sind, weiß ich nicht, wie ich anfangen soll?
user3637362
1
@ user3637362: StackOverflow hat praktische Antworten: stackoverflow.com/questions/6195335/… stackoverflow.com/questions/849211/…
MSalters
2

Die Idee besteht darin, alle vom Benutzer berührten Punkte beizubehalten und dann den Abstand zwischen jedem dieser Punkte und der beim Loslassen des Bildschirms gebildeten Linie zu bewerten und zu summieren.

Hier ist etwas, um Ihnen den Einstieg in Pseudo-Code zu erleichtern:

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

Was ist cumulativeDistancekönnte Ihnen eine Idee über die Armatur geben. Ein Abstand von 0 würde bedeuten, dass der Benutzer die ganze Zeit direkt in der Leitung war. Jetzt müssten Sie einige Tests durchführen, um zu sehen, wie es sich in Ihrem Kontext verhält. Und Sie können den zurückgegebenen Wert distanceOfPointToLinedurch Quadrieren verstärken, um größere Entfernungen von der Linie zu bestrafen.

Ich bin nicht mit Unity vertraut, aber der Code updatehier kann in eine onDragFunktion gehen.

Und vielleicht möchten Sie irgendwo einen Code hinzufügen, um zu verhindern, dass ein Punkt registriert wird, wenn er mit dem zuletzt registrierten identisch ist. Sie möchten keine Inhalte registrieren, wenn sich der Benutzer nicht bewegt.

Vaillancourt
quelle
5
Wenn Sie für jeden gemessenen Punkt den Abstand zwischen der Ideallinie und dem Punkt addieren, müssen Sie die Anzahl der durchgeführten Maßnahmen berücksichtigen. Wenn der Benutzer langsamer zeichnet oder ein Gerät mit einer schnelleren Abtastrate verwendet, registriert er mehr Punkte, was bedeutet, dass sie eine schlechtere Punktzahl bekommen.
Philipp
@Philipp Ja, das tust du! Ich muss zugeben, dass Ihre Vorgehensweise besser zu sein scheint als meine: P
Vaillancourt
Ich denke, dass dieser Ansatz verbessert wird, indem die durchschnittliche Entfernung und nicht die kumulative Entfernung verwendet wird.
Dancrumb
@Dancrumb Wirklich, es hängt von den Bedürfnissen ab, aber ja, das wäre ein Weg, es zu tun.
Vaillancourt
2

Eine Methode, die Sie verwenden können, besteht darin, die Linie in Segmente zu unterteilen und zwischen jedem Vektor, der das Segment darstellt, und einem Vektor, der eine gerade Linie zwischen dem ersten und dem letzten Punkt darstellt, ein Vektorpunktprodukt zu erstellen. Dies hat den Vorteil, dass Sie extrem "stachelige" Segmente leicht finden können.

Bearbeiten:

Ich würde auch in Betracht ziehen, die Länge des Segments zusätzlich zum Skalarprodukt zu verwenden. Ein sehr kurzer, aber orthogonaler Vektor sollte weniger zählen als ein langer, der eine geringere Abweichung aufweist.

Kik
quelle
1

Am einfachsten und schnellsten kann es sein, einfach herauszufinden, wie dick die Linie sein muss, um alle Punkte der vom Benutzer gezeichneten Linie abzudecken.

Je dicker die Linie sein muss, desto schlechter hat der Benutzer die Linie gezeichnet.

Adam Davis
quelle
0

In Bezug auf MSalters Answer finden Sie hier einige spezifischere Informationen.

Verwenden Sie die Methode der kleinsten Quadrate, um eine Linie für Ihre Punkte anzupassen. Sie suchen im Grunde nach einer Funktion y = f (x), die am besten passt. Sobald Sie es haben, können Sie die tatsächlichen y-Werte verwenden, um das Quadrat der Differenzen zu summieren:

s = Summe über ((yf (x)) ^ 2)

Je kleiner die Summe, desto gerader die Linie.

Wie Sie die beste Annäherung erhalten, erfahren Sie hier: http://math.mit.edu/~gs/linearalgebra/ila0403.pdf

Lesen Sie einfach "Eine gerade Linie einpassen". Beachten Sie, dass t anstelle von x und b anstelle von y verwendet wird. C und D sind näherungsweise zu bestimmen, dann gilt f (x) = C + Dx

Zusätzlicher Hinweis: Natürlich müssen Sie auch die Länge der Linie berücksichtigen. Jede Linie, die aus 2 Punkten besteht, ist perfekt. Ich kenne den genauen Kontext nicht, aber ich würde die Summe der Quadrate geteilt durch die Anzahl der Punkte als Bewertung verwenden. Auch würde ich die Anforderung einer minimalen Länge, einer minimalen Anzahl von Punkten hinzufügen. (Vielleicht 75% der maximalen Länge)

Philipp
quelle