Re: Liegt der Punkt im Dreieck oder nicht

[Hartmut Wolf <hwolf@XXXXXXX.com>]

> "Patzer, Reinhold" wrote:
> 
> Liebe DMUG Kolleginnen und Kollegen,
> 
> ich habe folgendes mathematisches Problem
> (nein, es ist leider nicht Mathematica-spezifisch):
> 
> Gegeben sind 3 Punkte durch ihre Koordinaten
> in der Ebene. Diese 3 Punkte werden als Eckpunkte
> eines Dreiecks aufgefasst.
> Gesucht ist ein Algorithmus, der feststellt, ob ein
> vierter, durch seine Koordianten gegebener Punkt
> innerhalb des Dreiecks liegt oder nicht.
> 
> Mir genuegt die Angabe von Literaturstellen. Eine
> Mathematica Funktion waere natuerlich auch sehr
> hilfreich.
> 
> Vielen Dank und Gruesse aus Darmstadt
> 
> Reinhold Patzer

Lieber Reinhold,

obwohl du schon schöne Antworten bekommen hast, will ich dir noch eine
weiter mitgeben (gestern hat' ich keine Zeit): diese hier hat
(vielleicht?, ich habe das nicht überprüft) Performanz-Vorteile.

In[1]:= Wedge[{x1_, x2_}, {y1_, y2_}] := x1 y2 - x2 y1

Das ist das äußere Produkt (Vektorprodukt) zweier zweidimensionaler
Vektoren (einfach die dritte Komponente, falls man die Vektoren als in
der x-y-Ebebe in 3D eingebettet denkt.

Jetzt hol ich mir die Daten von Martin Weiß (das ist eine echt tolle Art
zu antworten: die Daten mitliefern!)
 
In[3]:= s = OpenRead[
   
"d:\\www\\Mathematics\\Mathematica\MathGroup\\2000\\2000-ii\\dreieck.dat"]
Out[3]=
InputStream["d:\\www\\Mathematics\\Mathematica\\MathGroup\\2000\\2000-ii\\\
dreieck.dat", 4]
In[4]:= data = ReadList[s, Word];
In[5]:= Close[s];

...und mache Punkte p[i] draus

In[6]:= (p[First[#]] = Rest[#]) &@ ToExpression[#] & /@ Partition[data,
3];

Unsere drei Ecken sind:

In[7]:= dreiecken = {p[17], p[31], p[10]}

Wir schauen uns das ganze an:

In[14]:=
Show[Graphics[{{Hue[2/3, 0.1, 1], Polygon[dreiecken]}, 
        PointSize[0.02], {Point[p[#]], Text[#, p[#], {-1.5, 0.5}]} & /@
ix}], 
    PlotRegion -> {{0, 1}, {0.05, 1}}];

Beim Umformen hab ich nicht aufgepasst, ich hole mir die Liste der
möglichen Indices für p zurück (das kannst du natürlich besser machen):

In[9]:= ix = Part[#, 1, 1, 1] & /@ DownValues[p]
Out[9]= {10, 13, 14, 15, 17, 19, 21, 31, 36, 43}
 
Jetzt eine Hilfsfunktion, Set (statt SetDelayed) wurde benutzt, um schon
so weit wie möglich auszuwerten (für unsere 3 Ecken):

In[10]:= inner1[{p1_, p2_}] = 
  MapThread[
    Sign[({p1, p2} - #1)\[Wedge]#2] & , {dreiecken, 
      Subtract[RotateRight[dreiecken], dreiecken]}]
Out[10]=
{Sign[29.465 (-101.042 + p1) - 16.838 (-80.281 + p2)], 
  Sign[-12.034 (-130.009 + p1) + 28.967 (-92.315 + p2)], 
  Sign[-17.431 (-117.88 + p1) - 12.129 (-109.746 + p2)]}

Das ist die nun der gesuchte Test:

In[11]:= innerhalb[p_] := SameQ @@ inner1[p]


Wir führen ihn aus:

In[12]:= innerhalb[p[#]] & /@ ix
Out[12]=
{False, True, True, False, False, False, False, False, False, True}

True für die Punkte im Innern, False außerhalb, auf den Kanten und in
den Ecken.


Gruß aus Darmstadt nach Darmstadt,

Hartmut