# How can I define a 3D version of the built-in VoronoiDiagram function?

Can anybody point me in a direction that will guide me to extend the VoronoiDiagram function in Mathematica to handle 3D (three dimensional) situations (i.e. points in 3D)? Any help will be greatly appreciated.

-
–  kguler Feb 1 at 23:24
@kguler, the VoronoiDiagram function only takes 2D data points and outputs the Voronoi diagram of points in a plane. What I'm trying to create is an equivalent VoronoiDiagram that accepts 3D vectors. –  RunnyKine Feb 1 at 23:43

Update: Using Raster3D and a variation of func that returns 4-tuples

 data3C = RandomReal[1, {10, 6}];
func3C = Nearest[{#, #2, #3} -> {##4, .03} & @@@ data3C];
tbl3C = Table[  First[func3C[{x, y, z}]] // Quiet, {x, 0, 1, .01},
{y, 0, 1, .01}, {z, 0, 1, .01}];


Examples:

 Row[Labeled[Graphics3D[Raster3D[tbl3C, ColorFunction -> #,
Method -> {"InterpolateValues" -> True}],
Background -> Black, ImageSize -> 400,
SphericalRegion -> True], #, Top] & /@
{Hue, RGBColor, (GrayLevel[#[[1]], .03] &)}, Spacer[5]]


colorRules = Thread[# -> (ColorData[1, "ColorList"][[;; Length@#]])] &[
Flatten[tbl3C, 2] // DeleteDuplicates] /.  RGBColor -> List;
Row[Labeled[ Graphics3D[Raster3D[tbl3C /. colorRules, ColorFunction -> #,
Method -> {"InterpolateValues" -> True}],
Background -> Black, ImageSize -> 400,
SphericalRegion -> True], #, Top] & /@
{(RGBColor[#[[1]], #[[2]], #[[3]], .01] &),
(RGBColor[#[[1]], #[[2]], #[[3]], .03] &),
(RGBColor[#[[1]], #[[2]], #[[3]], .05] &)}, Spacer[5]]


Using version-9 built-in Image3D with @Mr.Wizard's func:

  data = RandomReal[1, {20, 4}];
func = Nearest[{#, #2, #3} -> #4 & @@@ data];
dta = Table[func[{x, y, z}] // Quiet, {x, 0, 1, .005}, {y, 0, 1, .005}, {z, 0,    1, .005}];

Grid[Partition[
Image3D[dta,
ImageSize -> 350, ColorFunction -> #, Background -> Black] & /@
{"SunsetColorsOpacity", "RainbowOpacity", "WhiteBlackOpacity",
(Append[Blend[{LightBlue, Blue, Yellow}, #], #] &)}, 2]]


-

Mathematica ships with a TetGen interface called TetGenLink. To learn how to use TetGenLink is a bit more work than using the usual Mathematica functions, so I am not going to post a complete solution now.

But the way to go is using TetGenLink. It can compute a Delaunay tetrahedral mesh, which is the dual of the Voronoi partitioning. TetGen can also compute Voronoi partitions, but I am not sure if this function is exposed in TetGenLink, you'd have to check.

The function to use is TetGenTetrahedralize and I think you need to read the TetGen docs to understand the second argument (those flags should be the same as the command line options to TetGen).

-
Yes, TetGenLink is the way to go. –  user21 Feb 2 at 3:17
@ruebenko If you post an answer with the precise command, I'll delete this one. I'd have to keep reading the docs for a while to figure out the right syntax. –  Szabolcs Feb 2 at 3:18
well TetGen will not give you the Voronoi directly. You will need to construct the Voronoi from the tetrahedralization. –  user21 Feb 2 at 5:55
Have you found any undocumented Mathematica feature of the TetGenLink regarding Voronoi partitioning yet? I was not able to find any command which does the trick. –  Rainer Sep 22 at 22:02

mPower is what your are looking for, which interfaces with Qhull

I have used this package with Mathematica 7 and 8 regularly on both Mac and Windows. let' do a testing installation with Mathematica 9 on Mac 10.8, you can just delete the folder directly after testing

mPower 1.0 for Mathematica 6.0

Qhull 12.01 Mac Bindary

for Windows binary, you can grab it directly from qhull.org

uzip both packages, create a folder "qhull" under mpower folder, then copy "bin" folder from uzipped qhull package, put it under qhull folder you just created

in mPower folder open mPower.m in Mathematica

$QHULL::usage="$QHULL should contain the name (as a string) of the folder that contains the QHULL binaries on your system.
$QHULL=ToFileName[{$UserBaseDirectory, "Applications", "qhull", "src"}];


modify it to

\$QHULL=ToFileName[{NotebookDirectory[],"qhull","bin"}];


or you can use absolute path directly

then create a new notebook file "test.nb" at the mPower folder

SetDirectory[NotebookDirectory[]]
<< "mPower.m"


you will get two warnings

ignore them, you are ready to use qhull interface now.

run the following code for testing:

(* random 3D points *)
points = RandomReal[1, {40, 3}];
(* construct 3D convexhull *)
ch = convexHull[points, convexHullFormat -> {facetNormals -> True, facets -> True}];
(* generate facets for 3D convexhull *)
facetIndices = facets /. ch;
loop[alist_] := Append[alist, alist[[1]]];
loopedFacetIndices = loop /@ facetIndices;
index2xyz[ijklist_] := points[[#]] & /@ ijklist;
loopedFacetCoordinates = index2xyz /@ loopedFacetIndices;
(* visulization 3D convexhull *)
convexObject =
Graphics3D[{PointSize[Large], Point[points], FaceForm[],
EdgeForm[Blue], Polygon /@ loopedFacetCoordinates},
ImageSize -> 500]


check the documentation on boundedCellVoronoi, you can run the example code by copying them into test.nb you just created.

-
This is quite a bare-bones answer. Please consider extending it, and adding an example if possible. –  Mr.Wizard Feb 2 at 5:53
@Mr.Wizard It's a link to a ready-made package that contains the functionality. The package seems to interface with a mature library, i.e. I expect it to be fast and accurate. I think this is a very useful answer and it leads the way to a solution that is much better than anything with Nearest. Lately I have the feeling that on this site we expect too much. Answers which don't give working code are not upvoted even if they give the key to the solution. The OP should really be able to handle it from here. If I were the OP, I'd focus on this answer first and accept as soon as I got it working. –  Szabolcs Feb 2 at 18:11
I took a look at the package, and it seems it's not immediately trivial to set it up with the current version of qhull. So I agree with MrW, if anyone gets it working, please describe how to do it. @Tuku did you get it working? –  Szabolcs Feb 2 at 20:25
@Szabolcs I don't discount that we ask a lot on this site, but I disagree that it is too much. Your reversal in the following comment is proof enough of this to me. Answers must be more than a signpost to the information needed to do it yourself, or half the Q's could be answered with a naked link to mathprogramming-intro.org. It is often very hard to determine what what is or is not trivial until you attempt it yourself, and those who would vote on such as answer are negligent in their duty if they vote without the knowledge from doing do. And that would be expecting too much. –  Mr.Wizard Feb 3 at 4:55

It would help if you gave an example of a 3D Voronoi diagram.

Perhaps you want something like this, using Nearest as I did here.

Warning: this is very slow and uses a lot of memory!

data = RandomReal[1, {20, 4}];

func = Nearest[{#, #2, #3} -> #4 & @@@ data];

ContourPlot3D[
func[{x, y, z}] // Quiet,
{x, 0, 1}, {y, 0, 1}, {z, 0, 1},
ColorFunction -> (Hue@#3 &)
]


Is that roughly what you want?

-