Prüfen ob Punkt in Viereck liegt

Sonstiges Hausaufgaben
1

Hey Leute.

Es geht mal wieder um Vektorrechnung, aufgabe wie im Titel und wir sollten
versuchen uns eine eigene lösung zu erarbeiten… ich komm aber irgendwie nicht
weiter… dabei ist meine idee so hübsch :stuck_out_tongue:

Nochmal genauer.
[das folgende ist nur meine interpretation der aufgabe, ergibt sich eben aus zuvor
ausgeführten teilschritten. ich denke aber das sollte so richtig sein.]
Man hat ein Viereck welches durch die Punkte
A(7,5|8|1) B(7,5|8,5|1) C(8|7,75|1) D(8,25|8,25|1)
definiert ist. Um ein… „richtiges…“ (hieß das nicht konvexes?) viereck zu erhalten, muss
ich offensichtlich die Strecke AB gegenüber CD legen… also ab ist offensichtlich keine
diagonale und cd auch nicht. auch wenn ich nicht weiß wie man das herausfindet. aber egal.

Außerdem hat man nen Punkt H(8|8|1) und soll prüfen ob dieser in diesem viereck liegt.

Meine Idee:

Wenn das rechteck so aussieht: (höhe (x3) is ja immer 1, daher kann man ne 2d abbildung verwenden)

verbinde ich AB und CD mit vektoren, also so:

und anschließend einen Punkt auf dem einen mit einem Punkt auf dem anderen Vektor, also quasi verbindungsvektor zum zeitpunkt t:
(bild zeigt diesen vektor für t=0.5)

nun muss ich diesen „allgemeinen verbindungsvektor“ ja nur noch mit dem Punkt H gleichsetzen, und schauen ob dieser
auf diesem vektor (dieser gerade was auch immer) liegt oder nicht. Weil die summe aller dieser „Verbindungsvektoren“
mit 0 <= t <= 1 würden ja die fläche des gesamten vierecks einschließen.

Okay, nun gings ans rechnen:

vektor AB = A + t((7.5, 8.5, 1) - (7.5, 8, 1)) = A + t * (0, 0.5, 0)
analog CD = C + t((8.25, 8.25, 1) - (8, 7.75, 1)) = C + t * (0.25, 0.5, 0)

so. jetzt die verbindung von AB zu CD zum zeitpunkt t:

startpunkt quasi = AB, was zusammmengefasst (7.5, 8 + 0.5t, 1) ist (sagen wir = F)
dieser startpunkt zu CD, zusammengefasst (8 + 0.25t, 7.75 + 0.5t, 1) (sagen wir = G)

so die richtung von AB nach CD wär also G - F = (0.5 + 0.25t, -0.25, 0) - da das wieder ein vektor
sein soll muss diese richtung wieder mal eine neue zeit genommen werden, also bswp s. Plus den startkpunkt,
haben wir: s * (0.5 + 0.25t, -0.25, 0) + (7.5, 8 + 0.5t, 1)

So. Das würde ich jetzt mit (8, 8, 1) gleichsetzen. Käme für s und t etwas >= 0 und <= 1 raus - so wäre
laut meiner theorie der punkt innerhalb dieses vierecks.
Das Problem ist das gleichsetzen, beziehungsweise auflösen.
komponenten weise wäre das:

0.5s + 0.25st + 7.5 = 8
-0.25s + 0.5t + 8 = 8
0 + 1 = 1

wie soll man das bitte nach s und t auflösen?
super schlaue skripte wie diese hier Gleichungssysteme lösen mit dem Gleichsetzungsverfahren meinen keine lösung, aber es muss doch
eine lösung geben, siehe bilder… der punkt is doch definitiv innerhalb des vierecks…

Und kann man das so überhaupt machen, wie ich das hier beschrieben habe, oder ist
das voll der schwachsinn?

Danke für alle Denkanstöße :slight_smile:

2

Ein Punkt liegt im Viereck, wenn er in einem der Teildreiecke ABC, BCD liegt. Und das testet man so: algorithm - How to determine a point in a triangle? - Stack Overflow

3

Dein Verfahren aus dem superschlauen skript ist nicht anwendbar, wegen des 0.25st ist das Ding nicht linear.

0,5s+0.25st=0.5 besser mit 4 malnehzmen 2s+st=2 also s(2+t)=2
-0.25s +.5t = 0

aus der zweiten GL folgt doch sofort s=2t, also 2t(2+t)=2, also 2t^2+4t-2=0, also t^2+2t-1=0

hätte die (positive) Lösung t=sqrt(2)-1 usw.

Hinweis: Ganz allgemein - Wenn du die 4 Punkte linearkombinierst

z_1 a + z_2 b + z_3 c +z_4 d

mit zahlen 0 <= z_1,z_2,z_3,z_4 <= 1 für die z_1+z_2+z_3+z_4 = 1 gilt, dann erhältst du genau die Punkte des Vierecks

4

Das ist zwar korrekt aber mit Vorsicht zu genießen. In diesem Falle muss das Viereck unbedingt Konvex sein, und es darf keine Konkave Ecke vorhanden sein.

Man muss also auch zwingend prüfen dass beim
Dreieck, der Punkt ausserhalb dessen liegt.
BCD, A
ACD, B
ABD, C
ABC, D

Angenommen D sein eine konkave Ecke, dann muss der gesuchte Punkt im Dreieck ABC liegen und er muss ausserhalb des Dreiecks BCD liegen.

5

… außer er liegt auf der Strecke BC…

6

So sieht nie im Leben ein Rechteck aus

Ansonsten probiere es mal mit dieser Methode aus
Punkt-in-Polygon-Test nach Jordan

7

Für ein Spiel hab ich mal die Even-odd rule benutzt. Hat ziemlich gut funktioniert, und es sind nur ien paar Zeilen.
Hab zwar noch nicht ganz durchblickt wie es eigentlich funktioniert, aber vielleicht kommt hier ja jemand drauf :wink:

8

Bei even-odd zeichnest du einen Strahl von deinem Punkt in eine beliebige Richtung (meistens x oder y) und zählst, wie oft der Strahl durch die “Wände” des Polygons dringt. Stehst du in einem Viereck, wird das normalerweise einmal sein. Aber selbst wenn eine Ecke bei einem Delta-Viereck innen zeigt und von dem Strahl passiert wird, bleibt die Anzahl ungerade (in dem Fall drei). Stehst du dagegen außerhalb, dringt dein Strahl durch eine gerade Anzahl “Wände”. Einziges Problem ist, dass man aufpassen muss, wenn der Strahl das Polygon genau in einer Ecke durchdringt - das muss genau einmal zählen, und nicht null- oder zweimal.

9

Interessant was hier so alles zusammen gekommen ist ^^
Sorry das ich hier nicht geantwortet hab, war stumm am mitlesen.

Aber danke für die ganzen antworten :slight_smile:
Letzten endes habe ich erfahren, das meine Lösung quasi
schon eine Ebenengleichung war… nur das ich davon nichts wusste…
also vektoriell der „richtigste“ weg das zu lösen.

10

[quote=Landei]Bei even-odd zeichnest du einen Strahl von deinem Punkt in eine beliebige Richtung (meistens x oder y) und zählst, wie oft der Strahl durch die „Wände“ des Polygons dringt.
[/quote]
das ist sicherlich verstanden wenn man Even-odd rule kennt,
warum der Zweizeiler-Code geht, was genau der ausrechnet, ist schon etwas komplizierter

Einziges Problem ist, dass man aufpassen muss, wenn der Strahl das Polygon genau in einer Ecke durchdringt - das muss genau einmal zählen, und nicht null- oder zweimal.

ein bisschen komplizierter dürfte es sein und das kann der Zweizeiler-Code irgendwie,
man kann von innen genau durch eine Ecke gehen, das muss einmal zählen,
sowie von außen eine Ecke berühren → null- oder zweimal