Liebe MMA-User,
das von Frank Scherbaum gestellte Problem, zu entscheiden, ob ein Punkt im
Inneren eines Polygons bzw. Polyeders liegt, lässt sich zumindest für Polygone
leicht mit Hilfe der Umlaufzahl beantworten:
(1) Die Umlaufzahl eines Punktes p bezüglich einer geschlossenen Kurve g, wie
in der Funktionentheorie definiert, hilft uns hier sehr gut weiter, ohne dass
Konvexität nötig ist. Die Umlaufzahl einer einfach geschlossenen Kurve ist
2*Pi oder -2*Pi, je nach Orientierung der Kurve, wenn p im Inneren der Kurve
liegt. Liegt p im Äußeren der Kurve, so ist die Umlaufzahl 0. Ein Polygon ohne
Selbstüberschneidung ist ist eine einfach geschlossene Kurve.
(2) Es folgt nun eine einfache Mathematica-Realisierung der obigen Idee, die
die Argumentfunktion für komplexe Zahlen benutzt:
In[1]: a:={2,3}; b:={1,5}; c:={-2,1}; d:={-1,-3}; e:={0,-2}
In[2]:
f[a_,poly_]:=Sum[Arg[((Part[poly,k+1]-a).{1,I})/((Part[poly,k]-a).{1,I})],{k,1
,Length[poly]-1}];
f[{0,0},{a,b,c,d,e,a}]//N
Out[2]: 6.28319
In[3]: f[{20,0},{a,b,c,d,e,a}]//N
Out[3]: 0.
In[4]: f[{0,0},{a,e,d,c,b,a}]//N
Out[4]: -6.28319
(3) Benutzt man nicht die N-Funktion, so erhält man eine Summe von ArcTan-
Werten, die Mathematica nicht ohne Weiteres vereinfachen kann.
(4) Es ist bei dieser Lösung mit der Umlaufszahl auch erlaubt, dass eine
Kurve, bzw. ein Polygon sich überschneidet. Auf diese Weise wird die Ebene in
mehrere einfach zusammenhängende Gebiete unterteilt. Eines dieser Gebiete ist
unbeschränkt und heißt das Äußere der Kurve, bzw. des Polygons. Liegt p nun in
diesem Äußeren des Polygons, dann liefert die von mir mit f bezeichnete
Funktion den Wert 0, liegt p dagegen in einer der beschränkten Komponmenten,
so liefert f je nach Orientierung 2*Pi, bzw. -2*Pi.
Das folgende Beispiel demonstriert diese beiden Fälle:
In[5]: f[{0,0},{a,b,e,d,c,a}]//N
Out[5]: -6.28319
In[6]: f[{1,1},{a,b,e,d,c,a}]//N
Out[6]: 0.
(5) Die Idee der Umlaufzahl lässt sich auch auf Polyeder ausweiten, dann muss
man aber mit sphärischen Winkeln arbeiten. Auch da lässt sich auf die
Konvexität verzichten.
Viele Grüße
Stefan Welke
|