Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Bestimmen, ob Punkt in Viereck liegt [solved]

  • 1
  • 2

Werbeanzeige

the[V]oid

Alter Hase

  • »the[V]oid« ist der Autor dieses Themas

Beiträge: 775

Wohnort: Aachen

  • Private Nachricht senden

1

23.05.2009, 19:45

Bestimmen, ob Punkt in Viereck liegt [solved]

Hallo,

gibt es eine einfache (effiziente) Möglichkeit, zu bestimmen, ob ein Punkt innerhalb eines durch 4 Eckpunkte definiertem Viereck liegt? Für ein Parallelogram wär's ja einfach, aber diese können in R^2 beliebig angeordnet sein.

Vielen Dank im Voraus
<< an dieser Stelle ist eine Signatur verstorben >>

User_User

Frischling

Beiträge: 46

  • Private Nachricht senden

2

23.05.2009, 20:05

Spontan würde ich das Viereck in zwei Dreiecke zerlegen und prüfen, ob der Punkt in einem der Dreiecke liegt.

Zera

Treue Seele

Beiträge: 133

  • Private Nachricht senden

3

23.05.2009, 21:41


(Link)

Wenn
0<=(P-E1) • (E2-E1) <=1
0<=(P-E1) • (E4-E1) <=1
0<=(P-E3) • (E2-E3) <=1
0<=(P-E3) • (E4-E3) <=1
gilt liegt P im Viereck :)

Genion

Alter Hase

Beiträge: 769

  • Private Nachricht senden

4

23.05.2009, 23:18

Da fehlen logische Verknüpfung. Ich nehme an du hast überall ein logisches und. (?)

Falls ja ist es falsch :P

Zera

Treue Seele

Beiträge: 133

  • Private Nachricht senden

5

23.05.2009, 23:24

*ähust*
0<=(P-E1) • (E2-E1) && (P-E1) • (E2-E1) <=1&&
0<=(P-E1) • (E4-E1) && (P-E1) • (E4-E1) <=1&&
0<=(P-E3) • (E2-E3) && (P-E3) • (E2-E3) <=1&&
0<=(P-E3) • (E4-E3) && (P-E3) • (E4-E3) <=1
jetzt?

the[V]oid

Alter Hase

  • »the[V]oid« ist der Autor dieses Themas

Beiträge: 775

Wohnort: Aachen

  • Private Nachricht senden

6

23.05.2009, 23:53

Danke schonmal... was für eine Verknüpfung sind denn die Punkte? Skalarprodukt?
<< an dieser Stelle ist eine Signatur verstorben >>

Genion

Alter Hase

Beiträge: 769

  • Private Nachricht senden

7

24.05.2009, 00:37

Zitat von »"Zera"«

*ähust*
0<=(P-E1) • (E2-E1) && (P-E1) • (E2-E1) <=1&&
0<=(P-E1) • (E4-E1) && (P-E1) • (E4-E1) <=1&&
0<=(P-E3) • (E2-E3) && (P-E3) • (E2-E3) <=1&&
0<=(P-E3) • (E4-E3) && (P-E3) • (E4-E3) <=1
jetzt?
Wie gesagt... ist falsch :P
Auf 2-dimensionaler Ebene:
E1(0|0)
E2(1|0)
E3(2|3)
E4(-2|1)
P(-1|1)

Der Punkt liegt im Viereck.

E4-E1 = (-2|1)
P-E1 = (-1|1)
(-2|1) • (-1|1) = 3

Du musst entweder vorher die Vektoren der Seiten auf die Länge 1 bringen oder alles durch die Länge der beiden benutzten Seiten teilen. (Um zu schauen obs weitere Tücken gibt werd ich langsam zu müde)

Edit: Achja, mir ist gerade nocheine Falle eingefallen.
E2-E1 = (1|0)
P-E1 = (-1|1)
(1|0) • (-1|1) = -1

Falsches Vorzeichen... lässt sich nicht durch eine Kürzung der Länge des Vektors ändern.

Zera

Treue Seele

Beiträge: 133

  • Private Nachricht senden

8

24.05.2009, 11:35

0<=(P-E1) • (E2-E1) && (P-E1) • (E2-E1) <=length(E2-E1)&&
0<=(P-E1) • (E4-E1) && (P-E1) • (E4-E1) <=length(E4-E1)&&
0<=(P-E3) • (E2-E3) && (P-E3) • (E2-E3) <=length(E2-E3)&&
0<=(P-E3) • (E4-E3) && (P-E3) • (E4-E3) <=length(E4-E3)

so müsste es passen(?)
hab verpennt, dass dan Punktprodukt ja nur bei Normalisierten maximal 1 ist :oops:

the[V]oid

Alter Hase

  • »the[V]oid« ist der Autor dieses Themas

Beiträge: 775

Wohnort: Aachen

  • Private Nachricht senden

9

24.05.2009, 14:42

Sicher, dass das so stimmt? Funktioniert leider nicht...

Beispiel:

Quellcode

 
1
2
3
4
5

P := (273 | 239)
E := ( (289 | 253), (258 | 255), (254 | 230), (286 | 229) )
f := (P - E1) • (E2 - E1) = 468,   |E2 - E1| = 2

0 <= f <= |E2 - E1| ist offensichtlich nicht erfüllt


Wenn ich mit diesen Werten mal deine Formeln durch-x'e, sollte der Punkt nicht im Viereck liegen, obwohl er es offensichtlich tut.

@ Genion: Sorry, aber habe leider nicht verstanden, was du meinst ^^


Edith sagt: Mit den folgenden Bedingungen funktioniert es hingegen immerhin teilweise (mit den ursprünglichen habe ich nie ein positives Resultat erhalten)

Quellcode

 
1
2
3
4

0 <= norm ( P-E1) • norm (E2-E1) <= 1 &&
0 <= norm ( P-E1) • norm (E4-E1) <= 1 &&
0 <= norm (E2-E3) • norm (E2-E3) <= 1 &&
0 <= norm ( P-E3) • norm (E4-E3) <= 1

Teilweise liefert dies aber auch für Punkte, die außerhalb liegen, ein positives Resultat....


Edith fügt noch hinzu: Funktioniert wohl (mit der letzten Variante), ich hatte bloß einen kleinen Fehler bei der Implementierung :D
<< an dieser Stelle ist eine Signatur verstorben >>

knivil

Treue Seele

Beiträge: 383

  • Private Nachricht senden

10

25.05.2009, 12:19

Ist das Polygon konvex und gibt man ihm eine Orientierung, z.B. gegen den Uhrzeigersinn, so muss man nur testen, ob der Punkt links von allen Geraden/Seiten ist. Dreiecke sind meist konvex, also zerlegt man sein Polygon (hier Viereck) in Dreiecke und testet, ob der Punkt in dem einen oder dem anderen ist. (So spart man uebrigens auch die eckelhaften Normierungen).
If it were not for laughter, there would be no Tao.

Werbeanzeige

  • 1
  • 2