Stuttgart, den 27. Dezember 1998
Sehr geehrter Herr Scherbaum,
Vorbemerkung
------------
anscheinend antwortete Ihnen bisher noch niemand auf Ihre Frage, wie man
feststellt,
ob ein Punkt innerhalb eines Polygons oder eines Polyeders liegt.
Ich selbst kann Ihnen leider auch keine fertige Loesung liefern, denke
aber, dass ich
Ihnen den Loesungsgang erlauertern kann. Dabei will ich mich auf die
Diskussion des
Polygon-Problems beschraenken.
Die Loesung des Polyeder-Problems ist eine offensichtiche Verallgemeinerung
des Polygon-Problems. Allerdings ist diese Verallgemeinerung nicht voellig
trivial.
Vielleicht hilft Ihnen meine Diskussion ja auch schon weiter.
Definition "Polygon"
---------- -------
Ein "Polygon" ist eine geschlossene, zusammenhaengende Folge von
Geradenstuecken in einer Ebene.
Definition "Innenseite / Aussenseite eine Polygons"
---------- ---------- -------------------------
Da ein Polygon eine geschlossene, zusammenhaengende Folge von
Geradenstuecken ist, kann man diese Folge in einer Richtung abwandern, bis
man wieder zum Ausgangspunkt kommt.
Wandert man ein Polygon im Gegenuhrzeigersinn ab, dann liegt die Innenseite
links des Weges, und die Aussenseite rechts des Weges.
Fall-Unterscheidungen der Relation Punkt / Polygon
---------------------------------- ----- -------
Ein Punkt kann zu einem Polygon folgende, unterscheidbare Relationen
besitzen :
Er liegt
- _innerhalb_ des Polygons ,
- _auf_ einem Geradenstueck des Polygons ,
- _im Schnittpunkt_ zweier Geradenstuecke eines Polygons ,
- _ausserhalb_ des Polygons .
Andere Relationen gibt es nicht.
Fall-Unterscheidungen von Geraden in einem gegebenen kartesischen
Koordinatensystem
---------------------------------------------------------------------------
--------
Eine wesentliche Eigenschaft einer Gerade ist ihre _Steigung_ .
In einem gegebenen kartesischen Koordinatensystem hat man folgende
Fall-Unterscheidung der moeglichen Geraden-Steigungen vorzunehmen :
Die Geraden-Steigung ist
- positiv
- null
- negativ
- unendlich ( positiv oder negativ ) .
Grundgedanke einer Loesung Ihres Problems
-----------------------------------------
Der Grundgedanke einer Loesung Ihres Problems laesst sich am einfachsten
fuer den Fall erlaeutern, dass ein Punkt _innerhalb_ des Polgyons liegen
soll.
Die Forderung,
dass ein Punkt _innerhalb_ eines Polygons liegen soll,
bedeutet,
dass er beim Abwandern des Polygons im _Gegenuhrzeigersinn_
fuer _alle_ Geradenstuecke
auf der _linken_ Seite des jeweils betrachteten Geradenstueckes liegen
muss.
Wenn der Punkt
fuer _alle_ Geradenstuecke beim Abwandern des Polygons im
_Gegenuhrzeigersinn_
auf der _linken_ Seite liegt,
dann
liegt er auch _im Innern_ des Polygons.
Zur Realisierung dieser Grundidee
---------------------------------
Geradengleichungen beschreiben den Fall, dass ein Punkt _auf_ einer Geraden
liegt.
Man muss offensichtlich Geradengleichungen zu Geraden_Un_Gleichungen
verallgemeinern,
um zu unterscheiden,
ob ein Punkt auf der linken oder rechten Seite einer Geraden liegt.
Danach muss man die Abfrage der Gueltigkeit dieser Bedingung fuer _ein_
Geradenstueck verbinden zur _Verknuepfung_ der Ergebnisse der Abfragen der
Gueltigkeit dieser Bedingung fuer _alle_ Geradenstuecke ( kurz - ein
logisches AND ist gefragt ).
Detaillierung : Zur Realisierung dieser Grundidee
------------- ---------------------------------
Ganz offensichtlich ist die Abfrage,
ob ein Punkt _auf_, _rechts_ oder _links_ von einer Geraden liegt,
abhaengig von den oben erlaeuterten _Steigungsfaellen_ .
Weiter ist die Aufgabenstellung zu detaillieren,
ob man _nur Punkte_ suchen moechte, die _innerhalb_ des Polygons liegen,
oder _allgemeiner_ Punkte nach der Eigenschaft _unterscheiden_ moechte,
dass sie zum Polygon in den oben erwaehnten Relationen liegen :
- innerhalb des Polygons ,
- auf einem Geradenstueck des Polygons ,
- im Schnittpunkt zweier Geradenstuecke eines Polygons ,
- ausserhalb des Polygons .
Verallgemeinerung auf Polyeder
------------------------------
Bei Polyedern sind entsprechend anstelle von Geradenstuecken ebene Polygone
zu betrachten, die jeweils in einer Ebene liegen.
Fachliteratur
-------------
Fachliteratur zum Problem vermute ich unter den Stichwort
"Graphische Datenverarbeitung" .
An weiteren Hinweisen zu diesem Thema bin ich durchaus selbst interessiert
!
Zum guten Schluss
-----------------
Nun muesste die Arbeit an einer geschickten Implementierung dieser
Grundideen beginnen..
Ich hoffe, meine Diskussion ist vollstaendig und fehlerfrei.
Fuer Kommentare und / oder Korrekturen bin ich dankbar.
Mit freundlichen Gruessen
Gunter Woysch
|