Wann liegt ein Vektor "zwischen" zwei Anderen?

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von starcow »

Tach Zusammen :-)

Hat von euch jemand vielleicht eine Idee, wie sich möglichst "kostengünstig" feststellen lässt, ob ein bestimmter Vektor, nennen wir ihn c, zwischen zwei weiteren Vektoren, a und b liegt?
Damit meine ich, dass wenn ich mir die (Einheits-)Vektoren a und b als Zeiger einer Uhr vorstelle und ich dabei die Laufrichtung so wähle, dass mein Weg beim Abschreiten des Ziffernblattes von a nach b möglichst kurz ist - ob ich dann auf meinem Weg Vektor c passiere.

Ich denke, ich sehe einen Weg. Dafür müsste ich aber min. drei mal das Skalarprodukt berechnen.
Gehts vielleicht irgendwie einfacher? (-:

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von Schrompf »

Vielleicht (c - a) * (b - a) < len(b - a)
Länge ist aber auch ein Punktprodukt, du wärst also stattdessen bei zwei Punktprodukten und ein bissl Addition anstatt bei drei Punktprodukten. Weiß nicht, ob es das besser macht. Und ich glaube, Du optimierst gerade die falsche Stelle. Mir fällt nämlich kein Szenario ein, indem die paar Operationen einen Unterschied machen, ohne das vorher durch Datenstrukturen und Cache-Lokalität ne Zehnerpotenz mehr rauszuholen wäre.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von Alexander Kornrumpf »

Wait what?

\tan \phi = \frac{y}{x}

Tangens ist monoton zwischen -\frac{1}{2} \pi und +\frac{1}{2} \pi, das heißt für das was du vor hast brauchst du nicht mal \arctan

... sondern ...

du bastelst dir die passende Fallunterscheidung (die wird computational der teuerste Teil sein, aber das Problem hast du sowieso, egal was du machst).

Ich könnte mir vorstellen, wenn man sich das mal systematisch hinschreibt, fallen einem von selbst die Optimierungsmöglichkeiten auf.

Die Lösung von Schrompf habe ich leider nicht innerhalb 2 Minuten verstanden und länger habe ich jetzt nicht investiert.
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von starcow »

Hey danke Schrompf! :-)
Interessante Methode. Bei "len()" hätte ich dann aber ne Wurzeloperation drin, seh ich das richtig?
Du denkst jetzt wohl an die Kollisionsabfrage als ganzes... Da hast du schon recht! Da dürfte das kaum ins Gewicht fallen. Da setze ich ja auf das "spatial hashing" Prinzip (Zellen). Die Vektoren-Geschichte brauch ich einfach an verschiedenen Stellen - und ich dachte mir, wenn es ne einfachere Lösung gibt, würd ich die gern integrieren. Also eher aus Ästhetik und Interesse, als aus Überlegungen zur Performance. :-)

@Kornrumpf
Dein Ansatz mit den Winkeln hab ich jetzt nicht recht verstanden. Ich hab ja Vektoren, welche ich dann zuerst in Winkel umrechnen müsste. Oder hast du das so gemeint?

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von Schrompf »

Nö, das len() kannst Du einsparen, wenn Du stattdessen den anderen Operanden quadrierst. Das KleinerAls gilt ja genauso für die Quadrate der beiden Werte wie für die Werte selbst.

Was für eine Bewandnis hat das für Spatial Hashing? Ich vermute, Du willst ne fixe Methode, um die Position eines beliebigen Dings zu hashen, um bei ner Umgebungssuche schnell den Großteil der anderen Dinge ausschließen zu können. Dafür kann ich ein schlichtes Punktprodukt empfehlen. Such Dir einen beliebigen Vektor schief und schräg durch Deinen Datensatz aus und sortiere alle Elemente anhand des Punktprodukts derer Position mit diesem Vektor. Dann kannst Du mit einem Binary Search durch dieses sortierte Array schnell den nahesten Punkt zu einer Position eingrenzen oder Nachbarbeziehungen anhand der umgebenden Array-Elemente eines bestimmten Objekts auswählen.

Ersetzt natürlich nicht die echte Abstandsprüfung, aber schließt schnell große Teile der Szene aus.

Den Vektor kannst Du beliebig wählen. Im Idealfall ist es die Hauptachse, entlang der sich die meisten Objekte erstrecken. Diese Achse kann man mathematisch bestimmen, es ist der längste Eigenvektor der Punktwolke. Aber das Ausrechnen ist nicht ganz einfach ohne Fertiglibs.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von Alexander Kornrumpf »

starcow hat geschrieben: 22.01.2020, 13:09 @Kornrumpf
Dein Ansatz mit den Winkeln hab ich jetzt nicht recht verstanden. Ich hab ja Vektoren, welche ich dann zuerst in Winkel umrechnen müsste. Oder hast du das so gemeint?
Gruss starcow
Um weitere Missverständnisse zu vermeiden zuerst der Hinweis dass mein Ansatz so nur in 2d funktioniert. Ich hatte das einfach mal angenommen wegen "zeiger auf einer Uhr" und weil du in höheren Dimensionen ja nicht weißt ob alle drei Vektoren überhaupt in einer Ebene liegen.

Vielleicht habe ich auch einfach nicht verstanden was du vor hast.
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von joeydee »

Ich wollte die Idee von Schrompf testen, hatte nicht ganz geklappt, und bin stattdessen bei nur einem Dot gelandet:
(a-c)*(b-c)<0
(für normalisierte 2D-Vektoren)

Umgangssprachlich übersetzt heißt das: "Wenn die Verbindungsvektoren von der zu testenden Vektorspitze zu den beiden einrahmenden Vektorspitzen in gegensätzliche Richtungen (>90°) zeigen, dann liegt der zu testende Vektor zwischen diesen beiden."
Auf alle Grenzfälle und Konsequenzen habe ich jetzt nicht getestet, ist nur mal ein Ansatzpunkt ohne wirklichen Beweis.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von Schrompf »

Ahja, ein Missverständnis. Ich ging davon aus, dass A, B und C drei Punkte im Raum wären.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von starcow »

Achso! Jetzt versteh ich deine Idee erst richtig! Das ist wirklich ziemlich raffiniert und bestechend einfach! :-) Dank dir Schrompf! Und Danke an joeydee für die Aufdeckung des Missverständnisses :-D
Ich hätte noch einen grafischen Beweis zu diesem Ansatz gefunden - aber ich glaube für dich ist das Ding ohnehin schon "wasserdicht" gewesen.
Bei Interesse will ich es aber gerne versuchen aufzuzeigen.
Aber die Idee ist wirklich cool! Und ästhetische Lösungen liebe ich ja ganz besonders! :-D Nochmal herzlichen Dank *wink*

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von Alexander Kornrumpf »

Meine Intuition waren Polarkoordinaten (dachte das geht aus dem \phi hervor) und \tan um um die Berechnung des Radius drumrum zu kommen. Wenn wir aber Einheitslänge vorraussetzen braucht man über Winkelfunktionen gar nicht nachdenken (wegen dann cos \phi = x und \sin \phi = y)

Nennen wir den zu testenden Vektor (x, y) und die umrahmenden (x1, y1) bzw. (x2, y2).

Wir können durch Spiegelung immer erreichen, dass x, y >= 0

Wenn 1) x1, x2 beide < 0 oder 2) y1, y2 beide < 0 ist der Test negativ

Es gibt also drei mögliche verbleibende Fälle:

3) y1, y2 >= 0: dann teste, dass x zwischen x1 und x2 liegt <=> (x1 - x), (x2 -x) haben nicht dasselbe Vorzeichen <=> (x1 - x)*(x2 - x) < 0
4) x1, x2 >= 0: dann teste, dass y zwischen y1 und y2 liegt <=> (y1 - y), (y2 -y) haben nicht dasselbe Vorzeichen <=> (y1 - y)*(y2 - y) < 0
5) x1, y2 <= 0 , x2, y1 >=0 (oder umgekehrt) dann teste ob x1+x2 > 0

Zum Vergleich Schrompf, Joeydee:
(x1-x)*(x2-x)+(y1-y)*(y2-y) < 0

man sieht schon die Gemeinsamkeit aber den Äquivalenzbeweis habe ich jetzt auf die Schnelle nicht hinbekommen.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von Alexander Kornrumpf »

Der Beweis der Schrompf/Joeydee Idee müsste über Thales gehen. Alle drei Punkte liegen auf einem Kreis. Wenn in einem Punkt ein rechter Winkel ist, müssen die anderen beiden Punkte sich genau gegenüberliegen. Das ist der Grenzfall. Wenn du den Winkel kleiner machst müssen die Punkte auf der anderen Seite zusammenwandern. Wenn du ihn größer machst müssen sie auf dieser Seite zusammenwandern.

Echt ein nettes Gimmick, Respekt.
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Wann liegt ein Vektor "zwischen" zwei Anderen?

Beitrag von joeydee »

Noch ein Ansatz, der für beliebige Dimensionen skalierbar sein dürfte:
- Die einrahmenden Vektoren a1 und a2 spannen einen 2-dimensionalen Raum auf.
- Ein Vektor p lässt sich in diesem Raum mit p=s1*a1+s2*a2 definieren.
- p liegt genau dann zwischen a1 und a2, wenn er im positiven Quadranten liegt, d.h. wenn alle Faktoren (s1, s2) >0 sind.

Etwas konkreter:
Man transformiert p mit der Inversen der Matrix mit den Schenkeln a1 und a2 (... bis a(n) für n Dimensionen).
Wenn alle Elemente des Ergebnisvektors >0 sind, liegt p zwischen diesen Schenkeln.

Oder ganz klassisch in Gleichungssystemen erzählt:
p.x=s1*a1.x+s2*a2.x
p.y=s1*a1.y+s2*a2.y
gegeben: p,a1,a2
gesucht: s1,s2
Zwei Unbekannte, zwei Gleichungen, lösbar.

Voraussetzung für Lösbarkeit in allen Fällen ist natürlich, dass keine Schenkel aufeinanderliegen.
Grundgedanke der Methode ist der Punkt-im-Dreiek-Test mittels baryzentrischer Koordinaten, nur eben mit beliebig langen Schenkeln.
Antworten