Prüfen ob eine Koordinate innerhalb eines Vierecks liegt

[HoDam]

Hallo zusammen,

meine Frage hat nichts direkt mit der Programmierung zu tun, sondern es geht mir um einen mathematischen Ansatz.
Leider kann ich hier keine Bild direkt hochladen (oder ich weiss nicht wie es geht) um es einfacher zu veranschaulichen.
Eine Webseite habe ich nicht um zu verlinken.
Ich habe eine Fläche definiert über 4 Eckpunkte (2D). Diese Fläche ist asymetrisch. Dann habe ich eine Punkt und möchte wissen, ob dieser Punkt innerhalb der
4-Ecksfläche liegt.
Geometrie ist leider schon über 20 Jahre her. Vektorrechnung kann ich grundsätzlich schon, aber eben lange nichts mehr gemacht. Ich weiss wie man die kürzeste Strecke von einem Punkt zu einer Geraden berechnet. Aber ich weiss nicht wie ich beurteilen kann ob dieser inner oder ausserhalb liegt, da eine Strecke keine Vorzeichen hat.. Habe schon versucht, das ganze über die Steigung vom Endpunkt einer Geraden zu dem Punkt zu bewerten. Aber ich bekomme keine Regel korrekt hergeleitet, die das Vorzeichen für alle 4 Geraden richtig behandelt. Auch der Weg über Polarkoordinaten funktioniert nur Ansatzweise. Wäre es ein Qaudrat hätte ich keine Probleme damit. Aber über eine asymetrische Vierecksfläche bekomme ich es einfach nicht hin. Mir geht es nicht um Programmcode, ich brauche einfach nur einen Hint.
Da ich nicht wusste, in welches Unterforum ich das schreiben sollte, nichts passendes gefunden, habe ich es hier rein geschrieben. Falls das falsch war, könnt ihr es ja ins richtige schieben.

Danke
HoDam

[STARGÅTE]

Erst mal zerlegst du das Viereck A,B,C,D in zwei Dreiecke A,B,C und A,C,D

Nun kannst du Prüfen ob der Punkt P im Dreieck liegt.
Dazu erstellst du zwei Vektoren: AB und AC
Nun Löst du die Gleichung: P = u*AB + v*AC nach u und v
Der Punkt liegt dann drin wenn 0<=u<=1 und 0<=v<=1 und 0<=u+v<=1

[HoDam]

Danke für den Tipp Stargate,

oh man, manchmal hat man echt ein Brett vor dem Kopf.

Vielen dank noch mal

HoDam

[bobobo]

Du bist hier im PB-Forum
Es bedarf keines Uploads um ein Bild zu zeigen.

Code: Alles auswählen

OpenWindow(0,0,0,400,400,"so geht das ",#PB_Window_SystemMenu|#PB_Window_ScreenCentered)
CanvasGadget(0,0,0,400,400)
StartDrawing(CanvasOutput(0))
Box(0,0,400,400,#White)
DrawingMode(#PB_2DDrawing_Transparent)
FrontColor(#Black)
LineXY(48,90,241,70)
LineXY(241,70,303,207)
LineXY(303,207,133,291)
LineXY(133,291,48,90)
Circle(122,175,5,#Red)
DrawText(130,175,"wie kann ich ermitteln ob der")
DrawText(130,195,"Punkt innerhalb des Vierecks liegt?")
DrawingMode(#PB_2DDrawing_Outlined)
Circle(150,350,50)
Circle(130,330,15)
Circle(170,330,15)
DrawingMode(#PB_2DDrawing_Transparent)
Circle(130,318,3)
Circle(170,318,3)
Ellipse(150,360,40,10)
Ellipse(150,358,40,10,#White)
StopDrawing()
Repeat
Until WaitWindowEvent()=#PB_Event_CloseWindow
End

[7x7]

Erst mal zerlegst du das Viereck A,B,C,D in zwei Dreiecke A,B,C und A,C,D

Nun kannst du Prüfen ob der Punkt P im Dreieck liegt.
Dazu erstellst du zwei Vektoren: AB und AC
Nun Löst du die Gleichung: P = u*AB + v*AC nach u und v
Der Punkt liegt dann drin wenn 0<=u<=1 und 0<=v<=1 und 0<=u+v<=1

Aha...echt cool!
Wusste gar nicht, dass es so einfach sein kann. Hast du das selbst rausgefunden oder irgendwo rausgelesen?

Ähm...dieses Vektorgedöns aus der Schule liegt bei mir schon ein paar Jährchen zurück! Hast du da irgendwo ein Beispielcode rumfliegen?

[NicTheQuick]

Da ich gerade wieder Langeweile hatte, hier ein Beispiel mit Dreiecken. Obwohl ich den Code nicht kommentiert habe, hoffe ich er ist verständlich.

Code: Alles auswählen

EnableExplicit

Structure Vector2f
	StructureUnion
		x.f
		u.f
	EndStructureUnion
	StructureUnion
		y.f
		v.f
	EndStructureUnion
EndStructure

Structure Trianglef
	p.Vector2f[3]
EndStructure

Structure Quadf
	p.Vector2f[4]
EndStructure

Procedure SolveUV(*t.Trianglef, *p.Vector2f, *uv.Vector2f)
	Protected u.Vector2f, v.Vector2f, p0.Vector2f
	
	u\x = *t\p[1]\x - *t\p[0]\x
	u\y = *t\p[1]\y - *t\p[0]\y
	v\x = *t\p[2]\x - *t\p[0]\x
	v\y = *t\p[2]\y - *t\p[0]\y
	p0\x = *p\x - *t\p[0]\x
	p0\y = *p\y - *t\p[0]\y
	
	If (Abs(u\x) > 0.00001)
		*uv\v = (p0\y - p0\x *u\y / u\x) / (v\y - (v\x * u\y / u\x))
		*uv\u = (p0\x - *uv\v * v\x) / u\x
	Else
		*uv\v = (p0\x - p0\y *u\x / u\y) / (v\x - (v\y * u\x / u\y))
		*uv\u = (p0\y - *uv\v * v\y) / u\y
	EndIf
EndProcedure

Procedure.i isPointInTriangle(*t.Trianglef, *p.Vector2f)
	Protected uv.Vector2f
	
	SolveUV(*t, *p, @uv)
	If (uv\u >= 0.0 And uv\u + uv\v <= 1.0 And uv\v >= 0.0)
		ProcedureReturn #True
	EndIf
EndProcedure

#W = 640
#H = 480

Define t.Trianglef, dir.Trianglef, i.i, mouse.Vector2f, eventId.i

For i = 0 To 2
	t\p[i]\x = Random(#W)
	t\p[i]\y = Random(#H)
	dir\p[i]\x = Random(2000) / 1000. - 1.
	dir\p[i]\y = Random(2000) / 1000. - 1.
Next
t\p[0]\x = 0

If OpenWindow(0, 0, 0, 640, 480, "Triangle Hit Test", #PB_Window_ScreenCentered | #PB_Window_SystemMenu)
	CanvasGadget(0, 0, 0, 640, 480)
	
	AddWindowTimer(0, 0, 20)
	
	Repeat
		eventId = WaitWindowEvent()
		Select eventId
			Case #PB_Event_CloseWindow
				Break
			
			Case #PB_Event_Gadget
				If EventGadget() = 0 And EventType() = #PB_EventType_MouseMove
					mouse\x = GetGadgetAttribute(0, #PB_Canvas_MouseX)
					mouse\y = GetGadgetAttribute(0, #PB_Canvas_MouseY)
				EndIf
			
			Case #PB_Event_Timer
				If EventTimer() = 0
					For i = 0 To 2
						t\p[i]\x + dir\p[i]\x
						t\p[i]\y + dir\p[i]\y
						dir\p[i]\x * (1 - 2 * Bool(t\p[i]\x < 0.0 Or t\p[i]\x > #W - 1))
						dir\p[i]\y * (1 - 2 * Bool(t\p[i]\y < 0.0 Or t\p[i]\y > #H - 1))
					Next
					If StartDrawing(CanvasOutput(0))
						Box(0, 0, 640, 480, $ffffff)
; 						Define.i x, y
; 						For x = 0 To #W - 1
; 							For y = 0 To #H - 1
; 								mouse\x = x
; 								mouse\y = y
; 								Define color.i = $0000ff
; 								If (isPointInTriangle(@t, @mouse))
; 									color = $00ff00
; 								EndIf
; 								Plot(x, y, color)
; 							Next
; 						Next
						For i = 0 To 2
							LineXY(t\p[i]\x, t\p[i]\y, t\p[(i + 1) % 3]\x, t\p[(i + 1) % 3]\y, $000000)
						Next
						Define color.i = $0000ff
						If (isPointInTriangle(@t, @mouse))
							color = $00ff00
						EndIf 
						Circle(mouse\x, mouse\y, 4, color)
						StopDrawing()
					EndIf
				EndIf
		EndSelect
	ForEver
EndIf

[STARGÅTE]

Aha...echt cool!
Wusste gar nicht, dass es so einfach sein kann. Hast du das selbst rausgefunden oder irgendwo rausgelesen?

Ähm...dieses Vektorgedöns aus der Schule liegt bei mir schon ein paar Jährchen zurück! Hast du da irgendwo ein Beispielcode rumfliegen?

Ich hab das nicht "herausgefunden", da ich in der Schule und im Studium ausgiebig analytische Geometrie (arbeiten mit Vektoren usw.) hatte, würde ich es inzwischen als allgemein Wissen bezeichnen.

Aus zwei Punkten erstelle ich mir halt ein Richtungsvektor, und mit zwei Richtungsvektoren kann ich ein Koorinatensystem aufspannen (muss ja nicht rechtwinklig sein). Dann stellt sich die Frage, mit welchen Koordinaten (in diesen speziellen System) ich den gesuchten Punkt erreichen kann.
Und die Nebenbedingungen binden den Punkte in ein Dreieck.

NicTheQuicks Code sieht auf den ersten Blick vllt sehr kompliziert aus, liegt aber nur daran, dass die ganze Vektoralgebra mit drin steckt.
Ich habe mit für PB mit der Zeit Includes geschrieben, mit denen ich schnell, einfach und übersichtlich mit Vektoren und mehr arbeiten kann.

[7x7]

Danke für den Code Nic! Hätte ich so nicht hinbekommen. Kann man bestimmt mal gebrauchen.