# How to draw (and paint) the Voronoi regions of a series of points using Tikz?

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?

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

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}


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.
• 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. 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. 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