Algorithmus zur Implementierung eines Lasso-Auswahlwerkzeugs?

Question

Ich entwickle eine Mac OS X-Anwendung, die als Teil der Benutzeroberfläche viele visuelle Elemente in der Hauptansicht anzeigt, die ausgewählt werden können. Diese Elemente können wirklich überall in der Ansicht positioniert werden. Die Benutzeroberfläche unterstützt verschiedene Arten der Auswahl der Elemente: Auswahlrechtecke, elliptische Auswahlrahmen und "freie" Lassoauswahl.

Ich habe bereits rechteckige und elliptische Auswahl Auswahl arbeiten. Der Algorithmus ist ziemlich einfach; Ein Element wird als "ausgewählt" betrachtet, wenn die Fläche des Elements die Fläche des Rechtecks ​​/ der Ellipse schneidet.

Die Lasso-Auswahl funktioniert genauso wie in modernen Bildbearbeitungsprogrammen wie Photoshop; Der Benutzer kann einen Pfad anklicken und ziehen, der sich selbst schließt, und die Elemente, die in dem gezeichneten Pfad enthalten sind, werden ausgewählt.

Dieser Algorithmus ist wahrscheinlich sehr viel komplexer als die rechteckige/elliptische Auswahl, da die Form der Auswahl nicht eingeschränkt ist. Ich frage mich, ob jemand Erfahrung darin hat, so etwas zu schreiben, oder ob Sie mir in die richtige Richtung weisen können, welche Art von Programmiertechniken notwendig sind und wie dieser Algorithmus am effizientesten funktioniert.

Vielen Dank im Voraus.

Answer 1

Die einzige Möglichkeit, die ich mir vorstellen kann, besteht darin, den Lasso-Umriss als Polygon zu behandeln. Dann können Sie mit jedem Standard point-inside-polygon test prüfen, welche Elemente ausgewählt werden sollen.

Sie müssen eine Entscheidung treffen, was zu tun ist, wenn sich das Polygon selbst schneidet (z. B. Abbildung 8).

Wenn Sie das Polygon konstruieren, um zu vermeiden, dass es zu viele Punkte bekommt, können Sie möglicherweise Punkte überspringen, die zu nahe am vorherigen Punkt liegen (etwa 3 Pixel, abhängig von Ihrer Anwendung).

Answer 2

Sie betrachten einen Punkt im Polygonproblem: http://en.wikipedia.org/wiki/Point_in_polygon Wenn Sie garantieren können, dass das Polygon konvex ist (nicht wahrscheinlich), wird der Algorithmus einfacher.

Answer 3

Für das Freihand-Lasso-Tool können Sie diese sehr einfache Lösung verwenden: Speichern Sie alle Punkte der Auswahlgrenze in einem Wörterbuch. Mit x als Schlüssel und (y1, y2) als Wert, wobei y1 <= y2. Dann schleifen Sie alle x' und sehen Sie, ob es einen Eintrag im Diktat gibt. Wenn ja, sind alle Punkte, wo x' = x und y >= y1 and y <= y2 sind, in der Auswahl.

Vielleicht nicht die beste Lösung, aber es sollte funktionieren.