Punkt innerhalb Polygon (mit konkaven Formen)
Übersicht
BlitzMax, BlitzMax NG Allgemein
|
RatchetBetreff: Punkt innerhalb Polygon (mit konkaven Formen) |
 Sa, Dez 24, 2005 0:36Antworten mit Zitat 
|
|---|---|---|
|
Ich möchte feststellen ob sich eine X-Y Koordinate innerhalb eines Polygons befindet. Mein Code funktioniert zwar mit konvexen Formen, aber nicht mit konkaven.
Wikipedia hat Folgendes geschrieben: Als konvex (lat.: convexus gewölbt, gerundet) bezeichnet man (u. a. in der Mathematik und in der Optik) Formen (Flächenteile, Linien), die nach außen gewölbt sind.
Nach innen gewölbte Formen werden als konkav bezeichnet. Das bedeutet dass mein Code bei einem Polygon in Form eines Kreises in dem ein Stück fehlt leider nicht funktioniert. Hat da jemand eventuell ein kleinen Codeschnipsel für mich? Hier der Auszug aus meinem Code: Code: [AUSKLAPPEN] Method PointInAction(X: Int, Y: Int)
Local Poly: Float[] Local Count: Int Local TmpX: Float Local TmpY: Float Local Checked: Int Local Point: TPoint 'Punkt Array erstellen Poly = New Float[PointList.Count() * 2] i = 0 For Point = EachIn PointList Poly[i] = Point.X i :+ 1 Poly[i] = Point.Y i :+ 1 Next 'Pruefen ob der Punkt innerhalb der Action liegt Count = PointList.Count() Checked = 0 For i = 1 To Count If i = Count Then TmpX = Poly[0] TmpY = Poly[1] Else TmpX = Poly[i*2] TmpY = Poly[i*2+1] EndIf If (TmpX - Poly[i*2-2]) * (Y - TmpY) - (X - TmpX) * (TmpY - Poly[i*2-1]) > 0 Then Checked :+ 1 Next Return (Checked = Count) End Method |
||
| [iMac 27"] [3,4GHz Intel Core i5 ] [8GB Ram] [NVIDIA GeForce GTX 775M 2GB] [MacOS X Yosemite] [BlitzMax + MaxGui] [Monkey X Pro] | ||
Dreamora |
Sa, Dez 24, 2005 2:33 Antworten mit Zitat
|
|
|---|---|---|
|
Ob es dafür einen Code gibt ... Ich zweifle irgendwie.
Aber du könntest einen Code schreiben, der deine konkave Fläche in einzelne konvexe Flächen zerschneidet und dann dagegen testen. Im Extremfall indem du sie triangulierst (also immer aus 3 Punkten ein 3 Eck bildest) und diese Dreiecke dann zu den maximal möglichen konvexen Flächen zusammenhängst. |
||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
|
TheShadowModerator |
Sa, Dez 24, 2005 13:03 Antworten mit Zitat
|
|---|---|---|
|
genau so geht es auch...
man kann flächen immer in dreiecke zerteilen... das erste problem ist: werden die punkte im uhrzeigersinn oder gegen den uhrzeigersinn angegeben? wenn gegen den uhrzeiger, dann nimmst du den ersten punkt und gehst zu nächsten 2 - wenn diese auch gegen den uhrzeigersinn liegen (es gibt so formen dafür), dann wandelst du das in dreieck um. und entfernst 2. punkt aus der liste und machst so weiter... falls eine fläche nicht aufgelöst werden kann, dann mußt du das ganze umgekehrt machen - also die punkte im uhrzeigersinn ablaufen (die punkte wurden im uhrzeigersinn angegeben) - und dann dreicke im uhrzeigersinn auflösen einzig bei überschneidungen gibt es bisschen probleme dann must du daraus einfach mehrere flächen vorher zerteilen... |
||
| AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2 | ||
Steffen |
Sa, Dez 24, 2005 13:47 Antworten mit Zitat
|
|
|---|---|---|
|
Hi,
Es geht auch, ohne das Ploygon zu zerteilen: Wenn die y-Koordinate größer ist, als das Maximum der y-Koordinaten aller Polygonpunkte oder die x-Koordinate größer ist, als das Maximum der x-Koordinaten aller Polygonpunkte, dann liegt der Punkt außerhalb. sonst musst du weiterprüfen: Du musst eine Linie vom Testpunt zu einem beliebigen Punkt außerhalb des Polygons ziehen. Wegen der einfachen Rechnung nimmst du am Besten eine Linie, die waagrecht verläuft. Also der Endpunkt hat die selbe y-Koordinate, wie der Testpunkt. Die x-Koordinate muss größer sein, als das Maximum der x-Koordinaten aller Polygonpunkte. Also z.B. x=Max(X1, X2, ...)+1. Damit liegt der Endpunkt außerhalb des Polygons. Diese Linie musst du mit allen Kanten des Polygons schneiden und die Anzahl der Schnitte merken. Wenn die Anzahl der Schnitte ungerade ist, dann liegt der Testpunkt im Polygon, sonst nicht. Ob die Kante geschnitten wurde, ermittelst du so: Wenn beide Ploygonpunkte über oder unter der Linie liegen, dann gibt es keinen Schnittpunkt. Sonst: (xt,yt=Koordinaten d. Testpunktes; x1,y1,x2,y2=Koordinaten der beiden Polygonpunkte, xe,ye=Koordinaten des Endpunktes) Wenn xt <=x2+(y1-y2)*(y1-y2)/(yt-y2)<=xe, dann wurde die Kante geschnitten. Ich habe es aus dem Kopf geschrieben, also garantiere ich nicht für Fehlerfreiheit. 
Gruß Steffen |
||
|
>PC: Pentium III 750MHz, ATI Rage 128 mit 32Mb, Windows Me, Blitz3D 1.87
>Laptop: Pentium M 1,4GHz, 512 Mb DDR, ATI Mobility Radeon 9000 mit 64Mb DDR, Windows XP Home, Blitz3D 1.87 |
||
|
|
TheShadowModerator |
Sa, Dez 24, 2005 15:33 Antworten mit Zitat
|
|---|---|---|
|
stimmt - das hab ich vergessen...
allerdings fand ich diese methode irg. nicht so genau - vllt. weil ich von oben/links die linie gezogen habe - k.A. ? ansonsten ja - das ist am schnellsten... |
||
| AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2 | ||
|
|
Ratchet |
Mi, Dez 28, 2005 0:31 Antworten mit Zitat
|
|---|---|---|
| Danke für eure Antworten. Dann mal ran ans Keyboard! | ||
| [iMac 27"] [3,4GHz Intel Core i5 ] [8GB Ram] [NVIDIA GeForce GTX 775M 2GB] [MacOS X Yosemite] [BlitzMax + MaxGui] [Monkey X Pro] | ||
Übersicht
BlitzMax, BlitzMax NG Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group