Hallo, Innenpunkt-Sucher,
ich habe das zweidimensionale Problem einmal folgendermaßen gelöst:
{xm,ym} sei der fragliche Punkt. Betrachte Kanten des Polygons und berechne die
Schnittpunkte {sx[i],sy[i]} mit der Geraden {x,ym} (x beliebig). Interessant sind
überhaupt nur solche Kanten, bei denen (y[i-1]<ym UND y[i]>=ym) ODER
(y[i-1]>=ym UND y[i]<ym) sind, also solche Kanten, die die Horizontale zwischen
ihren Eckpunkten schneiden oder wenigstens berühren.Weiter interessieren nur
Schnittpunkte, bei denen sx[i]>xm ist.
Die Eckpunkte seien mit {x[i],y[i]} bezeichnet. Zähle nun Plus 1, wenn
sx[i]>xm UND y[i-1]<ym UND y[i]>=ym ist.
Zähle Minus 1, wenn
sx[i]>xm UND y[i-1]>=ym UND y[i]<ym ist.
Analog muß man nun die Kante behandeln, die den letzten Polygonpunkt mit
dem ersten verbindet. Der Zähler ist die Umlaufzahl des Polygonzugs um den
Punkt {xm,ym}. Wenn sie größer als 0 ist, ist es ein Innenpunkt.
Dieser Algorithmus behandelt auch Polygone, die einen Punkt mehrfach
einschließen. Mit minimaler Abwandlung geht er auch für mehrfach (orientiert)
berandete Gebiete.
Ob man Randpunkte als Innenpunkte behandelt, ist Definitionssache. Randpunktge
haben mindestens ein sx[i]==xm.
Wenn man für viele benachbarte Punkte auf einem Gitter die Relation
Innen/Außenpunkt bestimmen soll, dann kann man sich die Arbeit dadurch
erleichtern, daß alle Punkte "in der gleichen Zeile" wie ein bereits untersuchter
Punkt bis zun nächsten Kantenschnittpunkt die gleiche Eigenschaft, wie der
untersuchte Punkt haben.
Für das höherdimensionale Problem habe ich keine Lösung parat. Diese
Gedanken sind von der Herleitung des komplex-eindimensionalen Residuen-
satzes inspiriert (daher kommt der Gedanke einer Umlaufzahl). Nun ist es sehr lange
her, daß ich mich mit komplexer Analysis (mehrerer Veränderlicher) beschäftigt habe.
Vielleicht findet man in dem Zusammenhang einen Startpunkt für Überlegungen
im höherdimensionalen Fall.
Viele Grüße
Dipl.-Math. Adalbert Hanßen.
> Liebe Kollegen/innen,
>
> kennt jemand einen einfachen und moeglichst schnellen Weg, um in
> Mathematica festzustellen, ob ein zweidimensionaler Punkt innerhalb
> eines Polygons liegt, welches durch seine Eckpunkte definiert ist, bzw.
> ein Punkt im 3D-Raum inerhalb eines Polyeders (ebenfalls durch die
> Eckpunkte definiert)?
> Mit freundlichen Gruessen,
> Frank Scherbaum
Abteilung/Department: Entwicklung Augenoptik
Ersteller/Author: Dipl.-Math. A. Hanßen
Telefon/Phone:
Fax/Telefax:
|