18

How can I draw (and paint) Voronoi regions of a series of points in plane using Tikz? How about if the points are in 3d space?

5
  • 2
    do you want a completely automatic way? Would some manual geometric construction be ok? Algorithms to do it are usually either inefficient or require rich data-structures which are difficult to code in TeX. For a completely automatic solution I would recommend generating the coordinates of the diagram from an external tool (or using LuaTeX?)
    – Bordaigorl
    Commented Oct 13, 2013 at 17:06
  • @Bordaigorl I prefer an automatic tool and I am not familiar with LuaTeX capabilities. Matlab has some tools for this, but I prefer to be able to do it on a PC with no Matlab.
    – per
    Commented Oct 13, 2013 at 17:17
  • 2
    You could also specify your requirements: does it need to be fast? How many points on average? Are you trying to draw a specific voronoi diagram or actually generate diagrams as needed? Is there a reason why you want to do it in TikZ or it's just that you want the "graphical rendering" to be done in TikZ?
    – Bordaigorl
    Commented Oct 13, 2013 at 17:24
  • I think that the first part of this question is clear : given a set of points, how can we draw the Voronoi diagram ? The 3D part is not clear. This question can be edited in a way to make it clear ... but for this it must be reopened ;)
    – Kpym
    Commented Jul 17, 2015 at 13:20
  • For the 2D Voronoi diagram, see Is there a way to draw a Voronoi diagram with pgfplots? (uses Octave/Matlab and PGFPlots).
    – Jake
    Commented Jul 17, 2015 at 13:45

1 Answer 1

12

Here is one solution using TikZ.

\documentclass[preview, border=7mm]{standalone}
\usepackage{xinttools} % for the \xintFor***
\usepackage{tikz}
\usetikzlibrary{calc}


\def\biglen{20cm} % playing role of infinity (should be < .25\maxdimen)
% define the "half plane" to be clipped (#1 = half the distance between cells)
\tikzset{
  half plane/.style={ to path={
       ($(\tikztostart)!.5!(\tikztotarget)!#1!(\tikztotarget)!\biglen!90:(\tikztotarget)$)
    -- ($(\tikztostart)!.5!(\tikztotarget)!#1!(\tikztotarget)!\biglen!-90:(\tikztotarget)$)
    -- ([turn]0,2*\biglen) -- ([turn]0,2*\biglen) -- cycle}},
  half plane/.default={1pt}
}

\def\n{23} % number of random points
\def\maxxy{4} % random points are in [-\maxxy,\maxxy]x[-\maxxy,\maxxy]

\begin{document}

  \begin{tikzpicture}
    % generate random points
    \pgfmathsetseed{1908} % init random with the year Voronoi published his paper ;)
    \def\pts{}
    \xintFor* #1 in {\xintSeq {1}{\n}} \do{
      \pgfmathsetmacro{\ptx}{.9*\maxxy*rand} % random x in [-.9\maxxy,.9\maxxy]
      \pgfmathsetmacro{\pty}{.9*\maxxy*rand} % random y in [-.9\maxxy,.9\maxxy]
      \edef\pts{\pts, (\ptx,\pty)} % stock the random point
    }

    % draw the points and their cells
    \xintForpair #1#2 in \pts \do{
      \edef\pta{#1,#2}
      \begin{scope}
        \xintForpair \#3#4 in \pts \do{
          \edef\ptb{#3,#4}
          \ifx\pta\ptb\relax % check if (#1,#2) == (#3,#4) ?
            \tikzstyle{myclip}=[];
          \else
            \tikzstyle{myclip}=[clip];
          \fi;
          \path[myclip] (#3,#4) to[half plane] (#1,#2);
        }
        \clip (-\maxxy,-\maxxy) rectangle (\maxxy,\maxxy); % last clip
        \pgfmathsetmacro{\randhue}{rnd}
        \definecolor{randcolor}{hsb}{\randhue,.5,1}
        \fill[randcolor] (#1,#2) circle (4*\biglen); % fill the cell with random color
        \fill[draw=red,very thick] (#1,#2) circle (1.4pt); % and draw the point
      \end{scope}
    }
    \pgfresetboundingbox
    \draw (-\maxxy,-\maxxy) rectangle (\maxxy,\maxxy);
  \end{tikzpicture}

\end{document}

enter image description here

Some comments on the code :

  • Given two points, A and B, the points that are closer to A is a half plane, delimited by the perpendicular bisector, and containing A.
  • So to construct the Voronoi cell of A we can take the intersection of all this half planes when B runs over all other points (different from A).
  • In the code, taking this intersection is done by clipping big rectangles that plays the role of "half planes".
  • I was not able to use \foreach because clipping inside such a loop is not available outside the loop (\foreach creates a group). So I'm overcoming this by using \xintFor.
6
  • Nice. It is if I'm not wrong O(n^2) complexity but it should do for small number of samples although I would simply call Lua or Python and be done with it. And by the way infinity is kept under the register \maxdimen.
    – percusse
    Commented Jul 18, 2015 at 13:15
  • @percusse Yes O(n^2). I'll be happy to see here LuaTeX, PythonTeX, metapost or another solution that is faster ;)
    – Kpym
    Commented Jul 18, 2015 at 13:46
  • My concern is more to the fact that it is consuming PDF objects rather too quickly. Speed is TeX speed anyways. I had a half answer with pgfplots. I'll try to find it.
    – percusse
    Commented Jul 18, 2015 at 13:50
  • @percusse actually \biglen should be smaller than .25\maxdimen.
    – Kpym
    Commented Jul 18, 2015 at 13:54
  • @percusse Ah ok. For example for 50 points this is ~2500 PDF objects and a file of ~50k. Is this unreasonable ?
    – Kpym
    Commented Jul 18, 2015 at 14:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .