Hallo,
kann mir jemand einen Lösungsvorschlag für folgende Problemstellung
geben?
(am Besten in C)
Es ist ein Polygon mit verschiedenen Koordinaten definiert.
Z.B. 1.Punkt x10 y5
2.Punkt x15 y0
3.Punkt x30 y-4
4.Punkt x12 y-10
5.Punkt x5 y-2
diese Punkte werde zu eine Polygon verbunden.
jetzt möchte ich prüfen ob eine neue Koordinate innnerhalb oder
auserhalb dieses Polygons liegt, wie kann man das prüfen?
Koordinate x12 y-5 = innerhalb
Koordinate x40 y-10 = auserhalb
ich hoffe das war verständlich.
Michael
Du denkst dir eine Verbindung von deinem Testpunkt zu einem Punkt der
garantiert ausserhalb liegt, und zählst wie oft diese Verbindung die
Polygon-Begrenzungen schneidet:
Ungerade=>innerhalb,
Gerade=>ausserhalb.
... und um das weiter auszuführen:
Wenn der Testpunkt dieselbe y Koordinate hat wie dein Testpunkt,
aber in X im unendlichen liegt, dann werden die Tests besonders
einfach.
Im Grunde läuft das dann auf die Bestimmung des Schnittpunktes
2-er Geraden hinaus. Allerdings hast du dann die Möglichkeit
einige Trivialfälle sehr schnell ausscheiden zu können:
Sei P1-P2 eine Kante deines Polygons, und T der zu testende
Punkt, dann fallen folgende Fälle trivialerweise weg:
Sowohl P1.y als auch P2.y sind größer als T.y
Sowohl P1.y als auch P2.y sind kleiner als T.y
Sowohl P1.x als auch P2.x sind kleiner als T.x
Sind P1.y und P2.y gleich, so kann es keinen
Schnittpunkt geben -> P1-P2 ignorieren.
Für die restlichen Fälle bestimmst du den Schnittpunkt
zwischen P1-P2 und einer Geraden die bei T beginnt und
parallel zur X Achse läuft. Über das Prinzip der ähnlichen
Dreiecke ist dies besonders einfach. Nur dann wenn der
Schnittpunkt in Y Richtung zwischen P1.y und P2.y liegt,
dann wird der Schnittpunkt auch gezählt.
Eine Besonderheit gibt es noch, wenn der Testpunkt in der
Y Koordinate exakt auf der Höhe eines Polygonpunktes liegt.
In dem Fall ist eine einfache Lösung die, dass der Schnittpunkt
nur dann gezählt wird, wenn er Y-mässig mit dem kleineren der
beiden Polygonpunkte übereinstimmt.
Du solltest auch noch definieren, wie du mit Punkten umgehen
willst, die exakt an der Aussenkontur des Polygons liegen:
Gehören sie zum Polygon, gehören sie nicht zum Polygon, oder
ist es egal, wie sie gewertet werden.
Michael wrote:
> Das sieht schon viel besser aus!> An den Spitzen wo sich zwei Linien treffen wird ein inside ausgegeben> obwohl ausserhalb.
Hast du mal ein paar Koordinaten?
Ob ein Polygoneckpunkt inside oder outside ist ist weitgehend
Definitionssache.
Muss leider weg.
Du kannst im Web auch weiter nach deinem Problem suchen.
Das Problem ist bekannt als 'Point in Polygon'
http://www.visibone.com/inpoly/
Zunächst muss mal definiert sein was innen und außen von nem Polygon
ist. Dazu verwendet man im normalfall die "Richtung" Der äußeren Kanten.
z.B. Linksrum = Polygon, Rechtsrum = "Loch"
Ich hab vor langen Zeiten auch mal ne Punkt in Polygon Funktion
geschrieben. Die Behandlung von Sonderfällen wie z.b. Testlinie auf
einer Ecke wird dadurch behoben dass einfach die Testlienie neu gewählt
wird :)
1
// testet, ob ein Punkt innerhalb eines Polygons liegt
2
function punktInPolygon(testPunkt: PPunkt; polygon: PPolygon): boolean;
Hallo,
die Funktion läuft. Jetzt suche ich noch eine Möglichkeit den Abstand
von einem sich außerhalb befindlichen Punkt zu einem Polygon zu
errechnen.
Hat da jemand Hilfe oder Info darüber?
