🚀 go-pugleaf

On Tue, 20 Oct 1998 09:08:39 GMT, q3067777@bonsai.fernuni-hagen.de
(Rolf Albinger) wrote:

> >kann mir jemand sagen, wie ich feststellen kann, ob ein Punkt sich innerhalb
> >einer unregelm�ssigen Fl�che befindet, von der ich nur die Koordinaten der
> >Eckpunkte kenne?

> Ja, kann ich. 
> Nimm eine beliebige Gerade (am besten parallel zur x-Achse, gibt
> weniger Rechnung) auf der der Testpunkt liegt. Diese Gerade schneidest
> du mit den Geraden, die von den paarweise benachbarten Punkten deines
> Polygons gebildet werden. Am besten du stellst alle Geraden in
> Parameterdarstellung dar, wenn dann der Schnittpunkt zwischen 0 und 1
> liegt, so weisst du, dass sich die Geraden im relevanten Abschnitt
> schneiden. Wie oft sich die Geraden deines Polygons mit deiner
> Testgeraden im relevanten Abschnitt schneiden, das zaehltst du.
> Ist diese Anzahl ungerade, so liegt dein Punkt innerhalb deines
> Polygons, ist sie gerade, so liegt dein Punkt ausserhalb.
> Wenn dich die Formeln interessieren, so kann ich dir die auch liefern.
> Dieses Verfahren geht bei beliebigen Polygonen; ob konvex,konkav ist
> egal.  



1. Man darf keine _Gerade_ durch den Testpunkt mit allen
Konturelementen des Polygons schneiden, sondern nur eine _Halbgerade_
(Strahl), die im Testpunkt beginnt.



2. Das Hauptproblem dieser Methode sind die Grenzfaelle. Was passiert,
wenn die Halbgerade eine Polygonseite in einem Eckpunkt schneidet ?
Hier kann man den Schnittpunkt nicht blind als einen Schnittpunkt
zaehlen. Was passiert, wenn eine Polygonseite ganz oder partiell in
der Halbgeraden liegt ?

Diese Probleme treten insbesondere bei ganzzahligen Rasterkoordinaten
haeufig auf und eine blauaeugige Implementierung "nach Rezept" kann da
fuerchterlich danebenhauen.





MfG
Horst