Abstand Punkt zu 1000 Linien

Jens B.

Jens B.

Erfahrenes Mitglied
Guten Abend,

nehmen wir an ich habe folgendes Problem:

ich habe 1000 Linien in einem 2 dimensionalen Raum. Alle Start- und Endkoordinaten dieser Linien habe ich gespeichert.

Nun möchte ich feststellen, ob mein Cursor weniger als 10 Pixel von irgendeiner Linie entfernt befindet, und das möglichst mit 32 Frames/Sekunde.

Mein Ansatz war, die klassische Abstand Gerade-Punkt Geometrie zu benutzen, allerdings nur für t = 0..1 (also wenn die Gerade durch A + t * B definiert wird und A und B die Start- und Endpunkt der Linien sind). Dies erscheint mir allerdings zu Performancelastig.

Gibt es dort einen Trick? Kann man irgendwie bestimmte Linien von vornherein ausschließen?

Danke schonmal
jens.
 
Hallo,

sind die Geraden fest oder verändern sich deren Positionen auch ständig?

Du könntest die Linien in das Format y = m*x + b umrechnen, also die Steigung und Oridnaten-Abschnitt berechnen. Dann kannst du prüfen, ob abs(m*MouseX + b - MouseY) < 7. Das wäre der erste Schritt einer groben Approximation, ob sich die Mouse 7 Pixel über oder unter der Gerade befindet. Dasselbe könntest du noch mit abs((MouseY - b) / m -MouseX) < 7 für die Prüfen "max. 7 Pixel neben der Geraden" machen. Warum 7 Pixel? Bei einer Diagonalen wäre der x- bzw. y-Abstand SQRT(50), also ungefähr 7...

Mamphil
 
Es macht natürlich wirklich einen großen Unterschied, ob sich die Linien (bzw. Endpunkte) bewegen oder nicht.
Wenn nicht, könnten sämtliche Punkte der Linie vorberechnet und in ein zweidimensionales Array eingetragen werden.
Eventuell könnte es auch nützlich sein, sicherzustellen, dass sich der Startpunkt der Linie immer links vom Endpunkt befindet o.ä. So würden Linien ausscheiden, deren Startpunkt rechts vom Mauscursor bzw. Endpunkt links vom Mauscursor liegen.
 
Danke schonmal,

das mit den Start- und Endpunkten ist ganz gut, werde das mal implementieren. Man kann die ja beim Zeichnen schon zur Not umgdreht in das Array speichern. Vorberechnen können werde ich das ganze aber nicht.

Die Graden sind fest. Die von Memphil gegebenen Formeln decken sich ja fast mit meinem Ansatz.

Danke euch, ich probiers mal aus und meld mich wieder wenns nicht klappt oder zu langsam läuft.
 
Aber wenn Du sagst, dass die Geraden "fest" sind, warum kannst Du dann nichts vorberechnen? Also alle Punkte im Vorhinein berechnen und geeignet ablegen?

Verrätst Du uns was über das Ziel der Anwendung? Musst Du auch erkennen, um welche Linie es sich handelt?
 
Das ganze wird eine Art vektorbasiertes Zeichenprogramm und ich brauche diese Abfrage für das "löschen-Werkzeug", mit welchem man über eine Linie fährt und diese dann gelöscht wird.

Eine Vorberechnung würde das Programm nur zum laggen bringen jedes mal, wenn man das Werkzeug anwählt und deswegen würde ich eine echtzeit-Variante preferieren.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück