Example: C(n,4) points of intersection

Published 2010-02-13 | Author: Hugues Vermeiren

It is an elementary though interesting problem of combinatorial geometry. Given n points on a circle (a convex closed curve might do), draw the segments joining two of these points and build the intersection points of these segments. The number of generated points is C(n,4). The code uses a classical algorithm to generate these combinations.

Download as: [PDF] [TEX]  •  [Open in writeLaTeX]

C(n,4) points of intersection

Do you have a question regarding this example, TikZ or LaTeX in general? Just ask in the LaTeX Forum.
Oder frag auf Deutsch auf TeXwelt.de.

% C(n,4) points of intersection
% Author: Hugues Vermeiren
\documentclass{article}
\usepackage{tikz}
\usepackage{ifthen}
\usepackage{amsmath}
\usetikzlibrary{arrows,calc,intersections}

% 1) Represent n points on a circle
% 2) Draw the complete graph on these points 
% 3) Draw all the intersection points of any two of these segments
\begin{document}

\def\r{4}
\def\n{8} \def\myangles{{25,50,85,125,160,220,250,280,340}}
%This vector contains the angles determining the position of the points.
%-----------------------------------------------------------
% Variables and counters used to generate the 4-combinations
\newcounter{np} \pgfmathsetcounter{np}{\n+1}
\newcounter{na} \newcounter{nb} \newcounter{nc}
\newcounter{ia} 
\pgfmathsetcounter{na}{\n-1}    % saves some computations later
\pgfmathsetcounter{nb}{\n-2}    % ""
\pgfmathsetcounter{nc}{\n-3}    %   ""
\newcounter{q} \setcounter{q}{0}    % if flag q=1 then exit the whiledo loop
\newcounter{e} \setcounter{e}{0}    % e counts the combinations!
\newcounter{a} \setcounter{a}{0}    % element of the 4-combination
\newcounter{b} \setcounter{b}{1}    % ""
\newcounter{c} \setcounter{c}{2}    % ""
\newcounter{d} \setcounter{d}{2}    % ""
%Watch out! The initial value {0,1,2,2} is not a 4-combination
%-----------------------------------------------------------

Consider $n$ randomly placed points on a circle.

\begin{enumerate}
    \item The complete graph on the $n$ points has $\begin{pmatrix}n\\2\end{pmatrix}$ edges.
    \item Each pair of edges yields an intersection point and there are (at most) $\begin{pmatrix}n\\4\end{pmatrix}$ such points.
\end{enumerate}

\begin{center}
\begin{tikzpicture}
    % Draw the complete graph
    \fill[fill=blue!10!green!10!,draw=blue,dotted,thick] (0,0) circle (\r);
    \pgfmathparse{\n-1} \let\nn\pgfmathresult 
    \foreach \i in {0,...,\nn}{
        \pgfmathparse{\i+1} \let\ii\pgfmathresult
        \pgfmathparse{\myangles[\i]} \let\t\pgfmathresult
        \foreach \j in {\ii,...,\n}
            \pgfmathparse{\myangles[\j]} \let\u\pgfmathresult
            \draw[blue,very thick] ({\r*cos(\t)},{\r*sin(\t)})--({\r*cos(\u)},{\r*sin(\u)});
        }
    \foreach \i in {0,...,\n}{
        \pgfmathparse{\myangles[\i]}    \let\t\pgfmathresult
        \pgfmathsetcounter{ia}{\i+1}
        \fill[draw=blue,fill=blue!20!,thick]
                ({\r*cos(\t)},{\r*sin(\t)})circle (2.5mm) node{$\mathbf{\theia}$};
        }
        % Points and segments are now drawn
        %
    \whiledo{\theq=0}{ % this loop generates the 4-combinations
        \stepcounter{e}
        \ifthenelse{\thee=1000}{\setcounter{q}{1}}{}% just to be sure to get out of the loop some day...
        \ifthenelse{\thed=\n}
            {\ifthenelse{\thec=\thena}
                {\ifthenelse{\theb=\thenb}
                    {\ifthenelse{\thea=\thenc}
                        {\setcounter{q}{1}}
                        {   \stepcounter{a}
                            \pgfmathsetcounter{b}{\thea+1}
                            \pgfmathsetcounter{c}{\thea+2}
                            \pgfmathsetcounter{d}{\thea+3}                  
                        }
                    }
                    {   \stepcounter{b}
                        \pgfmathsetcounter{c}{\theb+1}
                        \pgfmathsetcounter{d}{\theb+2}                      
                    }
                }
                {   \stepcounter{c}
                    \pgfmathsetcounter{d}{\thec+1}
                }
            }
            {\stepcounter{d}}
        \ifthenelse{\theq=0}{
            % Construction of the intersection points of the segments
            \pgfmathparse{\r*cos(\myangles[\thea])} \let\xa\pgfmathresult
            \pgfmathparse{\r*sin(\myangles[\thea])} \let\ya\pgfmathresult
            \pgfmathparse{\r*cos(\myangles[\theb])} \let\xb\pgfmathresult
            \pgfmathparse{\r*sin(\myangles[\theb])} \let\yb\pgfmathresult
            \pgfmathparse{\r*cos(\myangles[\thec])} \let\xc\pgfmathresult
            \pgfmathparse{\r*sin(\myangles[\thec])} \let\yc\pgfmathresult
            \pgfmathparse{\r*cos(\myangles[\thed])} \let\xd\pgfmathresult
            \pgfmathparse{\r*sin(\myangles[\thed])} \let\yd\pgfmathresult
            %               
            \coordinate  (A) at (\xa,\ya);
            \coordinate  (B) at (\xb,\yb);
            \coordinate  (C) at (\xc,\yc);
            \coordinate  (D) at (\xd,\yd);
            % Name the coordinates, but do not draw anything!               
            \path[name path=sega] (A) -- (C);
            \path[name path=segb] (B) -- (D);
            \path [name intersections={of=sega and segb}];
            \coordinate (X) at (intersection-1);
            \fill[fill=green!50!,draw=blue] (X) circle (0.8mm);             
            %-----------------------------------------------------
            }{}
    }% End of the whiledo loop
\end{tikzpicture}
\end{center}
\addtocounter{e}{-1}
Number of generated intersection points : \thee

\end{document}

Comments

Adding comments is currently not enabled.