Seite 1 von 1
Prüfen ob eine Koordinate innerhalb eines Vierecks liegt
Verfasst: 25.07.2013 22:03
von 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
Re: Prüfen ob eine Koordinate innerhalb eines Vierecks liegt
Verfasst: 25.07.2013 22:14
von 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
Re: Prüfen ob eine Koordinate innerhalb eines Vierecks liegt
Verfasst: 25.07.2013 23:23
von HoDam
Danke für den Tipp Stargate,
oh man, manchmal hat man echt ein Brett vor dem Kopf.
Vielen dank noch mal
HoDam
Re: Prüfen ob eine Koordinate innerhalb eines Vierecks liegt
Verfasst: 26.07.2013 12:40
von 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
Re: Prüfen ob eine Koordinate innerhalb eines Vierecks liegt
Verfasst: 27.07.2013 17:50
von 7x7
STARGÅTE hat geschrieben: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?

Re: Prüfen ob eine Koordinate innerhalb eines Vierecks liegt
Verfasst: 27.07.2013 18:55
von 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
Re: Prüfen ob eine Koordinate innerhalb eines Vierecks liegt
Verfasst: 27.07.2013 21:54
von STARGÅTE
7x7 hat geschrieben: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.
Re: Prüfen ob eine Koordinate innerhalb eines Vierecks liegt
Verfasst: 19.08.2013 12:55
von 7x7
Danke für den Code Nic! Hätte ich so nicht hinbekommen. Kann man bestimmt mal gebrauchen.
