Wie werden alle Liniensegmente aus einer Liste von Punkten ermittelt, die aus einer Mausgeste generiert werden?

Question

Momentan bin ich Praktikant bei einer Softwarefirma und eine meiner Aufgaben war es, die Erkennung von Mausgesten zu implementieren. Einer der Senior-Entwickler half mir beim Start und lieferte Code/Projekte, die den $ 1 Unistroke Recognizer http://depts.washington.edu/aimgroup/proj/dollar/ verwenden. Ich bekomme in einem breiten Weg, was der $ 1 Unistroke Recognizer tut und wie es funktioniert, bin aber ein bisschen überwältigt von dem Versuch, alle Interna/feinere Details davon zu verstehen.

Mein Problem ist, dass ich versuche, die Geste der Bewegung der Maus nach unten, dann nach oben zu erkennen. Der $ 1-Unistroke-Recognizer stellt fest, dass die Geste, die ich erstellt habe, eine Abwärtsbewegung war, was genau das ist, was sie tun sollte. Was ich wirklich gerne tun würde, ist zu sagen: "Ich erkenne eine Geste nach unten und dann eine Geste nach oben."

Ich weiß nicht, ob das fehlende Verständnis des $ 1 Unistroke Recognizer mich völlig am Kopf kratzt, aber hat irgendjemand irgendwelche Ideen, wie man zwei verschiedene Gesten erkennt, wenn man die Maus nach unten und dann nach oben bewegt?

Hier ist meine Idee, dass ich dachte, könnte mir helfen, aber würde für jemanden lieben, der ein Experte ist oder sogar nur ein bisschen mehr weiß als ich, um mich wissen zu lassen, was Sie denken. Jede Hilfe oder Ressourcen, die Sie kennen, wäre stark geschätzt.

Wie Meine Anwendung Derzeit funktioniert:

Die Art und Weise, die meine aktuelle Anwendung funktioniert, ist, dass ich erfassen Punkte aus, wo sich der Mauszeiger befindet, während der Benutzer die linke Maustaste gedrückt hält. Eine Liste von Punkten wird dann einem Gestenerkenner zugeführt, und sie spuckt dann aus, was sie für die beste Form/Geste hält, die den erfassten Punkten entspricht.

Meine Idee:

Was ich wollte, ist zu tun, bevor ich die Punkte auf die Gestenerkenner füttern ist irgendwie alle Punkte durchlaufen und brechen sie in einzelne Linien oder Kurven. Auf diese Weise konnte ich jede Linie/Kurve einzeln nacheinander einziehen und aus den Grundbewegungen nach unten, oben, links, rechts, Diagonalen und Kurven die endgültige Form/Geste bestimmen.

Ein Weg, den ich dachte, wäre gut zu bestimmen, ob es separate Linien in meiner Liste von Punkten gibt, stichprobenartige Gruppen von Punkten und Blick auf ihre Steigung. Wenn die Steigung einer abgetasteten Gruppe von Punkten X% von einer anderen Gruppe von abgetasteten Punkten abweicht, wäre es sicher anzunehmen, dass tatsächlich eine separate Linie vorhanden ist.

Was mir Mögliche Probleme Denken in meinem Denken ist:

• Wo finde ich das Ende einer Zeile und den Beginn einer separaten Zeile bestimmen? Wenn ich die Idee verwenden würde, die Steigung einer Gruppe von Punkten zu überprüfen, und dann feststellen würde, dass eine separate Linie vorhanden war, bedeutet das nicht, dass ich die Steigung einer separaten Linie gefunden habe. Wenn Sie zum Beispiel ein rechtwinkliges "L" mit einem rechten Winkel zeichnen und die Steigung der Punkte um die Ecke des "L" abtasten würden, würden Sie sehen, dass die Steigung einen vernünftigen Hinweis darauf gibt, dass eine separate Linie vorhanden ist Diese Punkte entsprechen nicht dem Beginn einer separaten Zeile.

• Wie man mit der sich ständig ändernden Steigung einer gekrümmten Linie umgehen kann? Der Gestenerkenner, den ich benutze, behandelt Kurven bereits so, wie ich es möchte.Aber ich möchte nicht, dass meine Methode, die ich zur Bestimmung der einzelnen Zeilen verwende, weiterhin nach diesen so genannten separaten Zeilen in einer Kurve sucht, weil sich ihre Steigung ständig ändert, wenn ich Gruppen von Punkten abgucke. Würde ich einfach aufhören, Punkte zu sammeln, wenn sich die Steigung mehr als X% so oft hintereinander geändert hat?

• Ich verwende nicht den richtigen "Typ" der Mathematik für die Bestimmung separater Zeilen. Mathematik ist nicht mein stärkstes Fach, aber ich habe etwas recherchiert. Ich habe versucht, in Dot Products zu schauen und zu sehen, ob das mich in eine Richtung weisen würde, aber ich weiß nicht, ob es das tut. Hat jemand Dot Prodcuts benutzt, um so etwas oder eine andere Methode zu machen?

Abschließende Gedanken, Hinweise und Dank:

Teil meines Problems ist Ich mag das Gefühl, dass ich nicht weiß, wie compeletly meine Frage zu stellen. Ich wäre nicht überrascht, wenn dieses Problem bereits (auf die eine oder andere Weise) gestellt wurde und es eine Lösung gibt, die gegoogelt werden kann. Aber meine Suchergebnisse auf Google haben keine Lösungen bereitgestellt, da ich nicht genau weiß, wie ich meine Frage stellen soll. Wenn Sie das Gefühl haben, dass es verwirrend ist, lassen Sie es mich bitte wissen, wo und warum und ich werde helfen, es zu klären. Vielleicht werden meine Suchanfragen bei Google präziser und ich werde eine Lösung finden.

Ich möchte nur noch einmal Danke sagen für das Lesen meiner Post. Ich weiß es lange, wusste aber nicht wirklich, wo ich es sonst noch fragen sollte. Imma sprechen mit einigen anderen Leuten im Büro, aber all meine besten Lösungen, die ich in der Schule verwendet habe, kamen von der StackOverflow-Community, also verdanke ich dir vielmals.

Edits zu diesem Beitrag:

(7/6 4:00 PM) Eine andere Idee, die ich darüber nachgedacht wurde, alle Punkte vor einem Min/Max Punkt zu vergleichen. Wenn ich zum Beispiel die Maus nach unten und dann nach oben bewege, wäre mein Ausgangspunkt der aktuelle Max-Punkt, während der Punkt, an dem ich die Maus wieder nach oben bewege, mein Min-Punkt wäre. Ich könnte dann weitermachen und nachsehen, ob es Punkte nach dem Min-Punkt gibt und wenn ja, dass es eine neue potenzielle Linie geben könnte. Ich weiß nicht, wie gut das bei anderen Formen wie Sternen funktionieren wird, aber das ist eine andere Sache, in die ich schauen werde. Hat jemand so etwas schon einmal gemacht?

Answer 1

Wenn Sie Ihr Problem so eingrenzen können, dass Sie eine allgemeine Kurve in gerade oder sanft gekrümmte Teillinien zerlegen, können Sie dies versuchen.

Vergleichen der Steigung der Segmente und Identifizieren von Bruchpunkten, wo es größer ist, dann würde ein Schwellenwert in einem sehr vereinfachten Fall funktionieren. Stellen Sie sich eine perfekt geformte L-Form vor, bei der Sie einen rechten Winkel zwischen zwei geraden Linien haben. Offensichtlich würde der Eckpunkt der einzige sein, bei dem die Steigungsdifferenz über dem Schwellenwert liegt, solange der Schwellenwert zwischen 0 und 90 Grad liegt, und somit eine identifizierbare Bruchstelle.

Die vertikalen und horizontalen Linien können jedoch leicht gekrümmt sein, so dass der Schwellenwert groß genug sein muss, damit diese kleinen Unterschiede in der Steigung als Bruchpunkte ignoriert werden. Sie müssen auch entscheiden, wie scharf eine Ecke der Algorithmus als Pause aufgreifen soll. ist 90 Grad oder mehr erforderlich oder sind sogar 30 Grad genug? Dies ist eine wichtige Frage.

Schließlich, um dies robust zu machen, würde ich nicht zufrieden sein, die Neigungen zweier benachbarter Segmente zu vergleichen. Hände können wackeln, Ecken können geglättet werden und die idealen Bedingungen, um gerade Linien und scharfe Ecken zu finden, werden wahrscheinlich nie vorkommen. Für jeden Punkt, der für eine Unterbrechung untersucht wird, würde ich die durchschnittliche Steigung der vorhergehenden Segmente nehmen und sie mit der durchschnittlichen Steigung der N folgenden Segmente vergleichen.Dies kann unter Verwendung eines laufenden Mittels effizient implementiert werden. Durch Auswahl einer guten Probennummer N (abhängig von der Genauigkeit der Eingabe, der Gesamtzahl der Punkte usw.) kann der Algorithmus das Rauschen vermeiden und bessere Erkennungen vornehmen.

• Für jede untersuchte Stelle (vor dem Ende beginn N Stellen in die Sequenz und endend N Punkte.)
  • Compute durchschnittliche Steigung der:

    Grundsätzlich würde der Algorithmus sein, N vorherige Segmente.

  • Berechnen durchschnittliche Steigung der N nächsten Segmente.
  • Wenn der Unterschied der Mittelwerte größer ist als Schwellenwert, den aktuellen Punkt als Bruchpunkt markieren.

Das ist ganz aus der Spitze von meinem Kopf. Sie müssten es in Ihrer Anwendung ausprobieren.

Answer 2

Wenn Sie mit absoluten Winkeln arbeiten, wie nach oben und nach unten, können Sie einfach die absolute Steigung zwischen zwei Punkten (nicht notwendigerweise benachbart) nehmen, um zu bestimmen, ob es rechts, links, oben, unten ist (wenn das genug ist))

die Kunst eine Entfernung zwischen den Punkten zu finden ist, so dass der Winkel nicht zufällig (mit 1px ist, wird der Winkel ein Vielfaches von 45 °)

Es ist ein Firefox-Plugin für Navigation mit Mausgesten werden, dass funktioniert sehr gut. Ich denke, es sind FireGestures, aber ich bin mir nicht sicher. Ich denke, Sie können sich davon inspirieren lassen.

Zusätzlicher Gedanke: Wenn Sie eine Form durch connectiong aufeinander folgende Punkte ziehen, dann ist das Verhältnis zwischen dem Bereich und der Länge des letzten Liniensegments auch ein Indikator, wenn Sie zurück zum ersten Punkt verbinden für die "Edginess" der Geste

Answer 3

Wenn Sie nur an up/down/links/rechts interessiert sind, ist eine erste Annäherung, um 45-Grad-Segmente eines Kreises zu überprüfen. Dies wird leicht gemacht, indem die horizontale Differenz zwischen (aufeinanderfolgenden) Punkten gegen die vertikale Differenz zwischen Punkten geprüft wird.

Angenommen, Sie haben eine größere positive horizontale Differenz als vertikale Differenz, dann wäre das "RECHTS".

Die einzige Schwierigkeit besteht dann zB darin, UP/DOWN von UP/RIGHT/DOWN zu unterscheiden. Dies könnte jedoch durch Abstände zwischen Punkten erfolgen. Wenn Sie feststellen, dass sich die Maus für weniger als 20 Pixel RECHTS bewegt hat, können Sie diese Bewegung ignorieren.