Csdrhrt

Given the following TikZ picture with an irregularly shaped polygon:

documentclass{article}

usepackage{tikz}



begin{document}

begin{tikzpicture}

path[draw=blue] (0,3) -- (5,4) -- (3,2) -- (4,0) -- (1,1) -- cycle;

node [circle,draw=none,fill=green,inner sep=0pt,minimum size=0.3cm] at (3.5,0.4) {};

node [circle,draw=none,fill=green,inner sep=0pt,minimum size=0.3cm] at (1.03,1.3) {};

node [circle,draw=none,fill=red,inner sep=0pt,minimum size=0.3cm] at (3.3,2) {};

node [circle,draw=none,fill=red,inner sep=0pt,minimum size=0.3cm] at (0.7,1.8) {};

end{tikzpicture}

end{document}

The two green circles in the picture lie completely inside the polygon, while the red ones lie partially or fully outside. Is there a way to automate that "ownership" test in TikZ? I know algorithms exist for such kind of tests, but does TikZ already provide this or similar features (e.g. tests for single points)?

Here is a solution using a ray casting method. The c point is an arbitrary point outside of the polygon. The quality of the result depends on the accuracy of the intersection calculation.

Note: to remove help lines, you can comment the draw[help lines,... line and uncomment the path[name path... line.

documentclass[tikz]{standalone}



usetikzlibrary{intersections}

defmycircles{

  {c1/red/3.5,0.4},{c2/blue/1.03,1.3},

  {c3/violet/3.3,2},{c4/lime/0.7,1.8},

  {c5/orange/2,0.55}% 

}

begin{document}

begin{tikzpicture}

  path[draw=blue,name path=polygon] (0,3) -- (5,4) -- (3,2) -- (4,0) -- (1,1) -- cycle;

  foreach cname/ccolor/ccoord in mycircles {

    node [circle,name path global=cname,draw=none,fill=ccolor,minimum size=3mm] (cname) at (ccoord) {};

  }

  begin{scope}[overlay]

    coordinate (c) at (-100,300);

    foreach cname/ccolor/ccoord in mycircles {

      draw[help lines,dashed,name path global=line-cname] (cname.center) -- (c);

      %path[name path global=line-mypath] (mypath.center) -- (c);

    }

  end{scope}



  coordinate (text) at (0,0);

  foreach cname/ccolor/ccoord in mycircles {

    path[%

    name intersections={of=polygon and cname,total=npc},

    name intersections={of=polygon and line-cname,total=nplc},

    ]

    pgfextra{

      node[align=flush left,at=(text),anchor=north west,node font=scriptsize,inner sep=.1em] (desc) {

        pgfmathsetmacromypartial{int((npc != 0)}

        pgfmathsetmacromyin{int(mod(nplc,2)!=0)}

        pgfmathsetmacromytexti{mypartial==1?"intersects":(myin==1?"is in":"is out")}

        pgfmathsetmacromytextii{myin==1?"center is in":"center is out")}

        ccolor{} circle mytexti{} (mytextii)

      };

      coordinate (text) at (desc.south west);

    };

  }

end{tikzpicture}

end{document}

Here is an alternative to Paul Gaborit's nice answer that is specific to polygons (or more generally shapes) of your type. Your shape is called a "star-shape" since there exists (at least) one point with the virtue that any point in the shape can be connected to this point with a straight line that does not intersect with the boundary. Given this point, it is straightforward to test the ownership: a circle is completely inside the polygon if

1. the line connecting its center with the star point does not intersect with the boundary and


2. the circle does not intersect with the boundary.

In the following MWE I picked a star point by hand (and also draw it) and perform the ownership test.

documentclass{article}

usepackage{tikz}

usetikzlibrary{intersections}

makeatletter % https://tex.stackexchange.com/a/38995/121799

tikzset{

  use path/.code={pgfsyssoftpath@setcurrentpath{#1}}

}

makeatother



begin{document}

begin{tikzpicture}[broadcast/.code n args={2}{xdef#2{#1}}]

path[draw=blue,name path=poly] (0,3) -- (5,4) -- (3,2) -- (4,0) -- (1,1) -- cycle;

coordinate (star) at (2,2);

fill[blue] (star) circle (1pt);

foreach X [count=Y] in {(3.5,0.4),(1.03,1.3),(3.3,2),(0.7,1.8)}

{path[name path=aux] X coordinate (X) to[bend left=0] (star);

path[name intersections={of=poly and aux,total=t},broadcast={t}{intT}];

node [circle,draw=none,inner sep=0pt,minimum size=0.3cm,name

path=circ,save path=pathC] (c-Y) at (X) {};

path[name intersections={of=poly and circ,total=t},broadcast={t}{intS}];

pgfmathtruncatemacro{itest}{intS+intT}

ifnumitest=0

fill[green,use path=pathC];

else

fill[red,use path=pathC];

fi}

end{tikzpicture}

end{document}

This method is restricted to star-shaped boundaries. However, there it does not suffer from problems that will arise when the test path hits a corner in Paul Gaborit's very nice answer.