Hallo an alle, ich bin dabei, ein ganz kleines CAD-Programm für eine Fräsmaschine zu schreiben. Dabei stellt sich die Aufgabe, die einzelnen Strecken, die das Programm in Form von Anfangs- und Endkoordinaten in einem Array speichert und am Bildschirm zeigt, mit der Maus anzuklicken und somit zwecks weiterer Bearbeitung zu identifizieren. Das Problem dabei ist, dass die Anfangs- und Endpunkte der gewünschten Strecke u.U. sehr weit entfernt von der aktuellen Mausposition, möglicherweise sogar außerhalb des Grafikfensters liegen. Zudem soll das Anklicken auch dann funktionieren, wenn man nur in der Nähe der Linie klickt; das Programm soll also nach derjenigen Strecke suchen, die am nächsten bei der aktuellen Mausposition vorbei läuft. Nun hat aber das Programm keinen Zugriff auf die in der Grafik gezeichneten einzelnen Pixel der Linie, es kennt ja nur Anfangs- und Endpunkte. Natürlich könnte ich mir jetzt eine mathematische Methode ausdenken, mit deren Hilfe man den geringsten Abstand der einzelnen Linien zur Mausposition errechnen kann, z.B. mit trigonometrischen Funktionen. Aber da sich in so einer Grafik u.U. viele hundert solcher Strecken befinden - die alle einzeln "abzuklappern" wären - vermute ich, dass eine solche Methode viel zu rechenintensiv und damit zu langsam wäre. Deshalb meine Frage: Kennt jemand von Euch das allgemein übliche Verfahren, d.h. den Algorithmus für das Anklicken von Strecken in einer unter VB erstellten Grafik und wie arbeitet dieser? Viele Grüße Norbert
RTree bzw. R*Tree Grob gesagt findet man damit alle Rechtecke, die in einem "Suchrechteck" liegen oder sich damit schneiden usw. Damit kann man also recht schnell die Menge der weiter zu untersuchenden Objekte eingrenzen. Bibliotheken dieser Algorithmen gibt es für viele Programmiersprachen. Die Original-Papers findet man auch im Netz, ich glaube von 1986 oder so. Sind nur ein paar Seiten, das Prinzip ist auch nicht so schwierig, also eine nette Übung für die Herbstferien.
Ein anderes Verfahren ist, jedes anklickbare Objekt mit einer einzigartigen Farbe rendern zu lassen (die Objekt-ID), dann muss man nur noch die Farbe der geklickten Position ermitteln und das Objekt kann einfach aus einer LUT bestimmt werden. Hier kann die Graffikhardware gut mitarbeiten, und die CPU muss sich nicht so viel mit Geometrie rumschlagen.
Aber gut, wenn Du in den Ferien schon etwas anderes vorhast: Du kannst auch den Abstand deines Klickpunktes zu all den anderen Streckensegmenten bestimmen und die mit dem kleinsten Abstand auswählen. Das ist zwar O(N), aber der Algorithmus ist sehr einfach, so dass es bei ein paar tausend Strecken schnell genug ist. Du musst nur den Algorithmus für STRECKENABSCHNITTE wählen, nicht den für Geraden. Im Netz geht das etwas durcheinander, ich hatte damals etwas suchen müssen, und mit dem selber Überlegen war mir das nicht so recht gelungen.
Ich habe sogar die Funktion für den Abstand hier im Forum wiedergefunden: Beitrag "Re: Fangfunktion"
Hallo Norbert. Norbert G. schrieb: > Das Problem dabei ist, dass die Anfangs- und Endpunkte der gewünschten > Strecke u.U. sehr weit entfernt von der aktuellen Mausposition, > möglicherweise sogar außerhalb des Grafikfensters liegen. Ich kenne mich mit VB überhaupt nicht aus. Aber mit anderen Sprachen. Und in zumindest einigen ist es üblich, das die Grafikbibliotheken Befehle oder Unterprogramme zur Verfügung stellen, um Objekte direkt zu plazieren oder zu manipulieren, und demzufolge auch anzuklicken, oder wenn Du auch mit der Maus über das Objekt gehst. Vermutlich ist das in VB genauso. Wäre arm, wenn nicht. Siehe dazu weiter unten. > Zudem soll das > Anklicken auch dann funktionieren, wenn man nur in der Nähe der Linie > klickt; das Programm soll also nach derjenigen Strecke suchen, die am > nächsten bei der aktuellen Mausposition vorbei läuft. Zwei Ansätze: Du berechnest ein das Objekt umschliessendes Rechteck, und schaust, ob die aktuelle Mausposition im Rechteck ist. Anderer Ansatz: (geht nur, wenn das GUI Transparenz zulässt, was leider nicht in jedem GUI der Fall ist), Du definierst ein zweites leicht vergrößertes Objekt, das transparent über dem Original liegt. Und reagierst auf Anklicken des transparenten Objekts. Wenn Du aber auch auf Objekte in der Nähe reagieren willst, wirst Du vermutluich öfters auch im "Fangbereich" von zwei Objekten sein. In dem Falle musst Du auch das erkennen, und eine zusätzliche Auswahl treffen. Das hilft auch, wenn zwei Objekte sich überlagern. > Natürlich könnte ich mir jetzt eine mathematische Methode > ausdenken, mit deren Hilfe man den geringsten Abstand der einzelnen > Linien zur Mausposition errechnen kann, z.B. mit trigonometrischen > Funktionen. Aber da sich in so einer Grafik u.U. viele hundert solcher > Strecken befinden - die alle einzeln "abzuklappern" wären - vermute ich, > dass eine solche Methode viel zu rechenintensiv und damit zu langsam > wäre. Richtig. Aber Du musst ja nicht unbedingt den exakten Abstand kennen. Es langt wohl meistens, wenn Du ausschliessen kannst, ob ein Objekt im fraglichen Bereich ist. Die musst Du dann nicht näher untersuchen. > > Deshalb meine Frage: Kennt jemand von Euch das allgemein übliche > Verfahren, d.h. den Algorithmus für das Anklicken von Strecken in einer > unter VB erstellten Grafik und wie arbeitet dieser? Wie oben erwähnt, mit VB kenne ich mich nicht aus, nur ein wenig mit Python3. Ich habe zu einem Wiedereinstieg in Programmieren damals Python gegenüber Basic vorgezogen, weil Python noch einfacher als Basic ist. Im Anhang befindet sich ein Zip-File "Buttontest2.zip", worin sich ein Ordner mit einem Python3 File "buttontest2.py" und ein GIF file Befinden. Das GIF-file ist ein Hintergrundbild. Es sollte im gleichen Ordner wie "buttontest2.py" sein. buttontest2.py solltest Du z.B. mit Idle3.irgendwas starten. Deine Idle-Installation sollte tkinter für die Grafik beinhalten. Wenn das Skript läuft, bekommst Du auf einem Canvas mit dem Hintergrundbild verschiedene Objekte angezeigt, die Du links/rechts anklicken kannst, und dann passiert auch irgendwas. So als Beispiel, wie sowas einfach machbar ist. Mit VB kenne ich mich nicht aus, aber vieleicht gibt es eine tkinter Integration in VB? Keine Ahnung. Zu Python bietet die Wikipedia einen Artikel: https://de.wikipedia.org/wiki/Python_(Programmiersprache) und mit Tutorials über Python wirst Du im Internet zugeschmissen wenn Du eine Suchmaschine bemühst. Es muss auch nicht Google sein, Metager ist eine gute Alternative. Hier schon mit einschlägigen Suchbegriffen vorgeladen: https://metager.de/meta/meta.ger3?focus=web&eingabe=Python3+einf%C3%BChrung+.pdf&encoding=utf8&lang=all&resultCount=20&time=1500&sprueche=on&newtab=on&maps=off&key=&theme=default Mit freundlichem Gruß: Bernd Wiebus alias dl1eic http://www.l02.de
:
Bearbeitet durch User
Norbert G. schrieb: > dass die Anfangs- und Endpunkte der gewünschten > Strecke u.U. sehr weit entfernt von der aktuellen Mausposition, > möglicherweise sogar außerhalb des Grafikfensters liegen 2 Moglichkeiten: Du rechnest das nicht im Grafikfenster, sondern in den kompletten Daten, die hast du ja sowieso, das Grafikfenster stellt nur einen Ausschnitt davon dar. Oder du berechnest zuerst, was von einem Objekt im Fenster liegt, das musst du ja auch sowieso um das Objekt im Fenster zu zeichnen, läuft normalerweise unter "Clipping". Liegen Endpunkte ausserhalb so liegt der Endpunkt im Viewport am Rand des Fensters. Das solltest du ja auch schon haben, um das Objekt im Fenster überhaupt zu zeichnen. Das hat den Vorteil dass du Objekte die komplett ausserhalb des Viewports liegen garnicht erst einbeziehen musst, die kannst du ja nicht angeklickt haben. Noch ein Tipp: sehr oft ist die Auswahl nicht eindeutig, es können ja auch Objekte übereinander liegen. Mein CAD-System blendet dann ein Popup-Menü ein mit den Objekten, die in Frage kommen, und man wählt das richtige aus. Georg
Norbert G. schrieb: > Nun hat aber das Programm keinen Zugriff auf die in der Grafik > gezeichneten einzelnen Pixel der Linie, es kennt ja nur Anfangs- und > Endpunkte. Natürlich könnte ich mir jetzt eine mathematische Methode > ausdenken, mit deren Hilfe man den geringsten Abstand der einzelnen > Linien zur Mausposition errechnen kann, z.B. mit trigonometrischen > Funktionen. Aber da sich in so einer Grafik u.U. viele hundert solcher > Strecken befinden - die alle einzeln "abzuklappern" wären - vermute ich, > dass eine solche Methode viel zu rechenintensiv und damit zu langsam > wäre. Da vermutest du falsch. Schließlich macht jedes ernstzunehmende CAD-Programm in diesem Falle genau das. (Weil es das mathematisch einzig sinnvolle ist.) Rechne doch einfach mal aus, was dieser hypertriviale Scheiss auf einer modernen CPU an Takten kostet. Das ist praktisch nix für eine Linie und nur unwesentlich mehr als praktisch nix für 10.000 Linien. Ja, wenn es 10.000.000 Linien sind, dann beginnt man das zu merken. Ich bezweifele allerdings, dass dein Programm überhaupt in der Lage ist, mit Sachen umzugehen, in denen 10M Linien anfallen. Wäre das der Fall, müßtest du hier nicht so blöd fragen, denn schon das Rendern dieser 10.000.000 Linien würde sehr viel mehr Kosten verursachen, schließlich stellt sich allein schon dafür ein sehr viel größeres Problem, nämlich: ist die Linie in meinem Fenster überhaupt zu sehen. Jedem, der mathematisch-logisch korrekt denken kann ist klar: Zur Beantwortung dieser Frage muß ein Problem mit demselben Rechenaufwand sogar gleich viermal gelöst werden... Sprich: Du hast nicht den Hauch einer Andeutung einer Ahnung von dem, was du da tust, bzw. zu tun versuchst...
Stefan S. schrieb: > Ich habe sogar die Funktion für den Abstand hier im Forum > wiedergefunden: [...] Hmm. Ich bin etwas betrübt, dass das Zauberwort "Hessesche Normalform" nirgendwo genannt wird, denn schätzungsweise ist sie die Basis für den Algorithmus.
c-hater schrieb: [..] > hypertriviale Scheiss [..] > nicht so blöd fragen [..] > Du hast nicht den Hauch einer Andeutung einer Ahnung von dem, > was du da tust, bzw. zu tun versuchst... Welch ein Glück, daß du bereits mit dem gesamten Wissen der Menschheit geboren wurdest und deshalb so unglaublich großschnäuzig und überheblich auftraten kannst. Stell dir nur mal vor, wie schlimm es wäre, wenn du etwas hättest lernen müssen (so wie andere Leute). Aber so kannst du natürlich ganz entspannt von oben auf andere herabschauen. :-(
Beitrag #5542447 wurde vom Autor gelöscht.
c-hater schrieb: > Rechne doch einfach mal aus, was dieser hypertriviale Scheiss auf einer > modernen CPU an Takten kostet. Das ist praktisch nix für eine Linie und > nur unwesentlich mehr als praktisch nix für 10.000 Linien. Man bedenke auch, dass eine moderne Mittelklasse-CPU so Richtung 100 Billionen Gleitkomma-Operationen pro Sekunde durchführen kann.
Jemand schrieb: > Ein anderes Verfahren ist, jedes anklickbare Objekt mit einer > einzigartigen Farbe rendern zu lassen (die Objekt-ID), dann muss man nur > noch die Farbe der geklickten Position ermitteln und das Objekt kann > einfach aus einer LUT bestimmt werden. Dumm nur, dass Strecken zwischen zwei Punkten keine einfärbbare Flächen besitzen.
Na. Lass mal. Sind wir doch froh solch einen Superbimbo zu haben, der alles weiss und bis ins Detail erklaeren kann. Ja, schlussendlich muss man jede Linie wie ein Grafikprogramm rendern um zu sehen, ob sie in einem Gebiet drin ist.
my2ct schrieb: > Jemand schrieb: >> Ein anderes Verfahren ist, jedes anklickbare Objekt mit einer >> einzigartigen Farbe rendern zu lassen (die Objekt-ID), dann muss man nur >> noch die Farbe der geklickten Position ermitteln und das Objekt kann >> einfach aus einer LUT bestimmt werden. > > Dumm nur, dass Strecken zwischen zwei Punkten keine einfärbbare Flächen > besitzen. Seit wann braucht man die?
my2ct schrieb: > Jemand schrieb: >> Ein anderes Verfahren ist, jedes anklickbare Objekt mit einer >> einzigartigen Farbe rendern zu lassen (die Objekt-ID), dann muss man nur >> noch die Farbe der geklickten Position ermitteln und das Objekt kann >> einfach aus einer LUT bestimmt werden. > > Dumm nur, dass Strecken zwischen zwei Punkten keine einfärbbare Flächen > besitzen. Und doch kann man sie visualisieren, obwohl die Pixel auf einem Bildschirm auch eine Fläche haben. Und es gibt Programme, in denen man sie auch anklicken kann, obwohl es unmöglich ist, mit einer Maus eine Linie mit einer Breite von 0 zu treffen. Wunder der Technik? ;-)
:
Bearbeitet durch User
Hallo an alle!
Ganz herzlichen Dank für Eure lebhafte Teilnahme (und Anteilnahme...)
und für die zahlreichen Tipps! Tatsächlich hat mich der Hinweis von Egon
D. ("Hessesche Normalform") auf die richtige Spur gebracht. Ich hatte
diesen Begriff noch nie gehört; anscheinend war das bis zu meinem Abi im
Jahr 1969 noch kein Thema. Zwar habe ich den Umgang damit, bzw. die
Anwendung trotz mehrerer Mathe-Hilfen hier im Internet immer noch nicht
so ganz begriffen, aber bei der weiteren Recherche stieß ich u.a. auf
die folgende klassisch-analytische Lösung, die mir wesentlich eher
liegt:
Der entscheidende Kerngedanke ist, dass die Steigung eines Lots auf eine
beliebige Gerade mit der Steigung m (Geradengleichung: y = mx + y0)
genau das -1/m-fache beträgt. Das hätte ich noch aus der Mittelstufe
wissen müssen, hatte es aber vergessen (schäm). Wenn man dieses Lot vom
Nullpunkt des Koordinatensystems ausgehen lässt, hat es die Form y =
(-1/m) * x. Beide Geraden schneiden sich im Punkt xp/yp. Folglich kann
man sie gleichsetzen und erhält dabei die Koordinaten des Schnittpunkts.
Der Abstand der Geraden vom Nullpunkt beträgt dann SQR(xp² + yp²).
Natürlich muss man vorher die Koordinaten der Geraden um denselben
Vektor verschieben, den die aktuelle Position der Maus innehat. Dann
sitzt die Maus quasi im Koordinaten-Nullpunkt.
Dieser Rechengang ist auf jeden Fall wesentlich weniger rechenintensiv
als irgendwelche trigonometrischen Funktionen.
Zu prüfen wäre lediglich noch, ob die betrachtete Strecke - die ja nur
ein Ausschnitt aus einer unendlich langen Geraden ist - überhaupt durch
den Schnittpunkt hindurch geht oder schon vorher endet. Wenn nicht,
müsste man den näheren der beiden Endpunkte als Ergebnis nehmen.
Viele Grüße!
Norbert
Norbert G. schrieb: > Zu prüfen wäre lediglich noch, Magst Du prüfen -- aber ich hatte dir oben ja die Formel von https://www.geometrictools.com/Source/Mathematics.html genannt. Und unter meinen Ruby Code hatte ja jemand dankenswerter weise den Pascal-Code eingefügt, einen von beiden wirst Du wohl in deine Sprache konvertieren können. Ob das jetzt auf "Hessesche Normalform" aufbaut weiss ich nicht.
Stefan S. schrieb: > so dass es bei > ein paar tausend Strecken schnell genug ist. Rolf M. schrieb: > Man bedenke auch, dass eine moderne Mittelklasse-CPU so Richtung 100 > Billionen Gleitkomma-Operationen pro Sekunde durchführen kann. Ein Test in C++ mit meinem rostigen Notebook mit i5-2520M und einem simplen Algorithmus mit Vektorprojektion (nur +-*/, kein sin/cos/sqrt) ohne weiteres Optimieren ergab 20ms, um zu einem Punkt die dichteste von 1 Mio Linien zu finden. Das sollte für die meisten Anwendungen reichen.
Tom schrieb: > Das sollte für die meisten Anwendungen reichen. Oft wird ja heute Python verwendet (oder so etwas wie MatLab), da ist man dann schon mal um den Faktor 100 langsamer. Die Kombination von RTree und dem Code von geometrictools wäre schon am elegantesten, und RTree kann man dann auch für beliebig geformte Objekte über deren BoundingBox nutzen.
Funktioniert RTree sinnvoll bei einem Haufen sich kreuzender Linien?
Ja sicher, sich kreuzende Linien sind doch nichts anderes als sich überlappende Objekte in 2D. Und RTree liefert für ein Query-Rechteck all die Rechtecke die umschlossen werden, geschnitten werden usw. Damit hat man eine schnelle Vorauswahl mit O(log N). Soweit ich mich erinnere funktioniert die Star-Variante auch für Punktmengen.
Hallo Stefan, danke für Deine Hartnäckigkeit! Natürlich hatte ich auch die Programmabschnitte von Jürgen in dem Thread aus dem Jahr 2013 gesehen, aber zunächst nicht verstanden (ich sträube mich mental gegen Dinge, die ich nicht verstehe ...). Ich hatte nicht begriffen, welche Bedeutung die Variable t0 hat. Erst heute nacht fiel bei mir der Groschen: es handelt sich um den relativen Anteil der Strecke zwischen den Punkten B und C, um den das Lot vom Punkt P die Strecke aufteilt. Wenn t0 kleiner als 0 ist, liegt das Lot außerhalb der Strecke jenseits von B, wenn t0 größer als 1 ist, liegt das Lot außerhalb der Strecke jenseits von Punkt C. In diesen Fällen gilt der Abstand zwischen B und P, bzw. C und P. Ansonsten kriegt man den Abstand ganz bequem aus hx und hy. # (c) # / # / (p) # / # (b) # see http://www.geometrictools.com/ # function AbstandPunktStrecke(px,py,bx,by,cx,cy: integer):integer; var mx,my,hx,hy,t0 : real; begin mx := cx - bx; my := cy - by; hx := px - bx; hy := py - by; t0 := (mx * hx + my * hy)/(sqr(mx) + sqr(my)); if t0 >= 0 then if t0 < 1 then begin hx := hx - t0 * mx; hy := hy - t0 * my; end else begin hx := hx - mx; hy := hy - my; end; result := round(sqrt((sqr(hx) + sqr(hy)))); end; Danke nochmal und viele Grüße Norbert
Wenn du's so am laufen hast, es aber zu langsam ist: Statt für alle Linien den Abstand zu berechnen, den kleinsten Abstand auszuwählen, und z.B. zu Prüfen ob Abstand < 10 Pixel für einen gültigen Klick, kannst du auch Abstand² berechnen, kleinsten Abstand² wählen, und Prüfen ob Abstand² < 100 Pixel.. Damit fällt aus dem Algorithmus oben das round() und sqrt() raus, vtml. die zwei teuersten Teil-Operationen. und es kann auch gut sein, dass mx*mx schneller berechnet ist als sqr(mx).
Noch etwas zum Clipping auf den Viewport: Das Anzeigefenster wird ja nicht so oft geändert wie was angeklickt wird. Daher kann es sich lohnen, bei einer Verschiebung usw. alle Objekte durchzugehen und die zu markieren, die überhaupt im Fenster sichtbar sind, die anderen muss man dann beim Anklicken garnicht berücksichtigen. Georg
Planlos schrieb: > Wenn du's so am laufen hast, es aber zu langsam ist: > > Statt für alle Linien den Abstand zu berechnen, den kleinsten Abstand > auszuwählen, und z.B. zu Prüfen ob Abstand < 10 Pixel für einen gültigen > Klick, kannst du auch Abstand² berechnen, kleinsten Abstand² wählen, und > Prüfen ob Abstand² < 100 Pixel.. Gerne wird für sowas dann einfach der Manhattan-Abstand verwendet, d.h. x + y. Dann hat man das ganze auf eine simple Addition reduziert, und für diese Anwendung kommt's auf hohe Genauigkeit nicht an. > und es kann auch gut sein, dass mx*mx schneller berechnet ist als > sqr(mx). Was ist "sqr"?
:
Bearbeitet durch User
Hallo Planlos, hallo Rolf, ja - bei der Suche nach dem geringsten Abstand auf das Wurzelziehen zu verzichten, ist ein sehr nützlicher Tipp. Denn Quadratwurzeln sind sehr rechenintensiv und für den Vergleich kann man die Quadrate von Zahlen genauso gut wie deren einfachen Betrag verwenden. Und wenn man anschließend vielleicht doch den Betrag braucht, z.B. fürs Zeichnen des Lots, braucht man nur von diesen zuletzt ermittelten Quadrat die Wurzel ziehen. Ob ich womöglich sogar nur den "Manhattan-Abstand" verwende (mit dem man auch noch zwei Quadrierungen sparen kann), wird sich danach richten, wie schnell die Suchfunktion tatsächlich ist. Ich bevorzuge - wo immer möglich - exakte Lösungen. Die Zeichenfolge "sqr()" steht in Pascal (oder Delphi?) für das Quadrat einer Zahl (im Gegensatz zu sqrt() für Quadratwurzel). Möglicherweise bietet sqr() gegenüber der allgemeinen Schreibweise "x * x" intern gewisse Vorteile, wahrscheinlich in der Rechengeschwindigkeit. Aber aufgepasst: Soweit ich mich erinnere, gibt es eine Programmiersprache (ich weiß nicht mehr welche, es kann sogar sein, dass es nur eine Programmierumgebung für Mikrocontroller war), bei der dieses Quadrat das Vorzeichen behält!!! Da wird dann also aus (-x)^2 die negative Zahl -(x²). In meinen Augen ist das der dümmste Unfug, den ich je gesehen habe, aber es ist (oder war) nunmal so. Im obigen Pascal-Code ist das aber nicht so (sonst wären die Ergebnisse falsch). Im Zeitalter schneller Rechner würde ich sicherheitshalber immer die allgemeine Schreibweise verwenden. Ein schnelles Multiplizierwerk dürfte inzwischen zur Grundausstattung jeder CPU gehören, so dass eine eventuell höhere Rechengeschwindigkeit beim Quadrieren keine Rolle mehr spielt. Viele Grüße Norbert
Angehängte Dateien:
Hallo, inzwischen bin ich endlich dazu gekommen, mir über die Hintergründe der verblüffend einfachen Funktion von Jürgen aus dem Jahr 2013 Gedanken zu machen und diese dabei überhaupt erst einmal zu begreifen. Im Anhang findet Ihr dazu den Scan der zugehörigen Hilfs-Skizze. Zusätzlich habe ich den ursprünglichen Pascal-Code der Funktion in VB übertragen. Zu Prüfzwecken habe ich eine einfache Ereignisroutine fürs Betätigen der linken Maustaste geschrieben. Hierin habe ich die Endkoordinaten einer Strecke definiert und auf dem Bildschirm gezeichnet (letzteres wäre gar nicht nötig), die aktuellen Mauskoordinaten und die Koordinaten der Strecke als Eingabeparameter in die Funktion eingegeben. Das Ergebnis (die errechnete Distanz) wird über das Textfeld 4 im StatusStrip an der Unterkante der Form ausgegeben - funktioniert! Viele Grüße Norbert
Norbert G. schrieb: > Gedanken zu > machen und diese dabei überhaupt erst einmal zu begreifen. Das ist sehr löblich. Wobei das interessante an der einfachen Formel ja ist, dass es eben auch dann funktioniert, wenn das Lot von P auf die Gerade b-c ausserhalb von der Strecke b-c fällt. (Ja ist schlecht formuliert.) Ich kann jetzt nicht überblicken, ob deine Zeichnung den Fall auch abdeckt.
Hallo Stefan, nein - meine Skizze deckt nur den "Normalfall" ab (Lot fällt auf die Strecke). Die anderen beiden Möglichkeiten (Distanz P-B und Distanz P-C) sind nach Pythagoras eigentlich selbsterklärend. Ich wollte dieses schöne Forum nicht unnötig mit Dateien vollstopfen.
Vlt eine noch schnellere und trotzdem "exakte" Lösung: 0. Berechne und speichere zu jeder Linie den Normalvektor (2D): normal = [py0-py1,px1-px0]/sqrt((px1-px0)^2+(py1-py0)^2) p0,p1 sind die die Endpunkte der Linie (diese Brechnungen müssen ja nur einmal gemacht werden, nicht bei jedem Klick) zusätzlich noch die Länge der Linie (dazu später mehr) 1A. Für jede Linie: dist = p*normal = (px-px0)*nx + (py-py0)*ny (p: dein Punkt, p0: erster Linienpunkt) das ist der Abstand des Linienstrahls von deinem Punkt. Für die meissten Linien ist dieser Abstand zu gross, d.h ausserhalb der Reichweite. Hier kann also früh abgebrochen werden. 1B. ist dist klein genug, dann bestimme die projezierte Position deines Punktes auf die Linie: pos = p*normal^T = -(px-px0)*ny + (py-py0)*nx Ist pos < -th oder pos > Länge+th (th: Schwellwert/Mind.Abst, Länge: Linienlänge von Oben), dann ist die Linie ausser der Reichweite. Dieser Test muss nur an wenigen Punkten ausgeführt werden. Damit lassen sich auch mehrfachtreffer finden. Mathematisch ist das Verfahren sehr einfach: Du erzeugst aus der Linie ein neues Koordinatensystem und projezierst deinen Punkt hinein.
Erweiterung für sehr viele Linien: Falls in einem Quadrat die Anzahl der Linien zu gross ist, dann teile das Quadrat in 4 neue Quadrate und teile die Linien auf die neuen Quadrate auf (eine Linie kann in mehreren Quadraten enthalten sein). Falls ein Quadrat weniger als eine bestimmte Anzahl Linien enthält, dann halte an. (dieses Verfahren leitet sich von Baumverfahren ab)
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.