6

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}

enter image description here

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)?

  • 2
    As far as I am aware, tikz does not provide any tools for this sort of thing but, visually, you could use the even odd rule (section 15.5.2 of the manual) to test this. Of this would almost certainly be subject to rounding errors. – Andrew Dec 26 '18 at 7:20
13

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.

enter image description here

\documentclass[tikz]{standalone}

\usetikzlibrary{intersections}
\def\mycircles{
  {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) {
        \pgfmathsetmacro\mypartial{int((\npc != 0)}
        \pgfmathsetmacro\myin{int(mod(\nplc,2)!=0)}
        \pgfmathsetmacro\mytexti{\mypartial==1?"intersects":(\myin==1?"is in":"is out")}
        \pgfmathsetmacro\mytextii{\myin==1?"center is in":"center is out")}
        \ccolor{} circle \mytexti{} (\mytextii)
      };
      \coordinate (text) at (desc.south west);
    };
  }
\end{tikzpicture}
\end{document}
|improve this answer|||||
  • 1
    I like it! +1. Nevertheless I cannot resist remarking that if you were to move the red circle a bit to the right such that the dashed line hits the corner precisely, you'd find two, i.e. an even number of, intersections and hence conclude the red circle is outside. This is regardless of the accuracy with which you compute the intersections. – user121799 Dec 26 '18 at 18:37
7

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}
\ifnum\itest=0
\fill[green,use path=\pathC];
\else
\fill[red,use path=\pathC];
\fi}
\end{tikzpicture}
\end{document}

enter image description here

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.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.