# 3D version of the built-in VoronoiDiagram

Posted 2 years ago
10659 Views
|
12 Replies
|
35 Total Likes
|
 Open in Cloud | See Original | Download to Desktop via Attachments Below Here I will show how to create 3D version of VoronoiDiagram in Wolfram Language.Note that there's currently no way to represent a collection of 3D Voronoi mesh cells in a MeshRegion or BoundaryMeshRegion.Here's a routine that takes the dual of the DelaunayMesh and returns an Association where the keys are the points and the values are their respective Voronoi cells. pad[?_][{min_, max_}] := {min, max} + ?(max-min){-1, 1} VoronoiCells[pts_] /; MatrixQ[pts, NumericQ] && 2 <= Last[Dimensions[pts]] <= 3 := Block[{bds, dm, conn, adj, lc, pc, cpts, hpts, hns, hp, vcells}, bds = pad[.1] /@ MinMax /@ Transpose[pts]; dm = DelaunayMesh[pts]; conn = dm["ConnectivityMatrix"[0, 1]]; adj = conn . Transpose[conn]; lc = conn["MatrixColumns"]; pc = adj["MatrixColumns"]; cpts = MeshCoordinates[dm]; vcells = Table[ hpts = PropertyValue[{dm, {1, lc[[i]]}}, MeshCellCentroid]; hns = Transpose[Transpose[cpts[[DeleteCases[pc[[i]], i]]]] - cpts[[i]]]; hp = MapThread[HalfSpace, {hns, hpts}]; BoundaryDiscretizeGraphics[#, PlotRange -> bds]& /@ hp, {i, MeshCellCount[dm, 0]} ]; AssociationThread[cpts, RegionIntersection @@@ vcells] ] Example: SeedRandom; pts = RandomReal[1, {10, 3}]; vc = VoronoiCells[pts] Show[MapIndexed[ BoundaryMeshRegion[#, MeshCellStyle -> {1 -> {Black, Thick}, 2 -> {ColorData[First[#2]]}}] &, Values[vc] ]] Show[ MapIndexed[ BoundaryMeshRegion[#, MeshCellStyle -> {1 -> Black, 2 -> {Opacity[0.5], ColorData[First[#2]]}}] &, Values[vc] ], Graphics3D[{PointSize[Large], Point[pts]}], Method -> {"RelieveDPZFighting" -> True} ] Note that this works in 2D too: SeedRandom; pts = RandomReal[1, {10, 2}]; vc = VoronoiCells[pts]; Show[MapIndexed[ BoundaryMeshRegion[#, MeshCellStyle -> {1 -> {Black, Thick}, 2 -> {ColorData[First[#2]]}}] &, Values[vc] ], Epilog -> {PointSize[Large], Point[pts]}]  Attachments: Answer
12 Replies
Sort By:
Posted 2 years ago
 Thanks for this function! will be very useful actually! The code can be slightly simplified: MinMax also has padding built in, second argument: MinMax[,paddingspec] Answer
Posted 2 years ago
 Aha, thanks! Answer
Posted 2 years ago
 Some time ago, I submitted this Wolfram Demonstration: Three-Dimensional Voronoi Mesh but, since I did not use the Regions functionality, I had to limit it to 2D cross sections of the 3D mesh. Hope they includeChip's excellent function in V12? Answer
Posted 2 years ago
 A most excellent function and one that is needed. Thanks ! the function should be scaled up and made part of version 12.0 ! Answer
Posted 2 years ago - Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming, and consider contributing your work to the The Notebook Archive! Answer
Posted 1 year ago
 Hi. This is very interesting. Is it possible to link the points with the face centres of their cells? It will be nice to visualise this. Great post. Thanks Fotos Stylianou Answer
Posted 1 year ago
 Very nice. Have you thought about submitting this to the function repository?Also, do you know if this has a relationship to power diagrams? Answer
Posted 1 year ago
 He's had to think about contributing it to the WFR; I put in a request a couple of days ago. Answer
Posted 1 year ago
 I hope that such an important function can go beyond the function repository and can be incorporated in the next Mathematica release. Answer
Posted 1 year ago
 I have been using your method with more points (like 1000) and it has some issues due to probably an internal bug in BoundaryDiscretizeGraphics. You may want to check my post here https://mathematica.stackexchange.com/questions/219100/weird-behaviour-with-boundarydiscretizegraphics Answer
Posted 1 year ago
 I spent nearly a week programming this in Mathematica (v.5, as I recall) around 2001 for half of Figure 4.10 in my book Pattern classification (2nd ed). At that time, there was no Opacity[] functionality either. I believe mine is the first book to include such a figure. I am so glad Wolfram has included this functionality, and thank Chip Hurst for his contributions to it. It looks great! Answer
Posted 7 months ago
 Chip and me were discussing his function a few days ago, when I mentioned to him that this can be used to implement Lloyd relaxation in 3D. In the spirit of this 2D Lloyd implementation and this spherical Lloyd implementation, I present the following: VoronoiCells[pts_List, ibds : (_?MatrixQ | Automatic) : Automatic] /; MatrixQ[pts, InternalRealValuedNumericQ] && 2 <= Last[Dimensions[pts]] <= 3 := Module[{bds, dm, conn, adj, lc, pc, cpts, hpts, hns, hp, vcells}, If[ibds === Automatic, bds = CoordinateBounds[pts, Scaled[0.1]], bds = ibds]; dm = DelaunayMesh[pts]; conn = dm["ConnectivityMatrix"[0, 1]]; adj = conn . Transpose[conn]; lc = conn["MatrixColumns"]; pc = adj["MatrixColumns"]; cpts = MeshCoordinates[dm]; vcells = Table[hpts = PropertyValue[{dm, {1, lc[[i]]}}, MeshCellCentroid]; hns = Transpose[Transpose[cpts[[DeleteCases[pc[[i]], i]]]] - cpts[[i]]]; hp = MapThread[HalfSpace, {hns, hpts}]; BoundaryDiscretizeGraphics[#, PlotRange -> bds] & /@ hp, {i, MeshCellCount[dm, 0]}]; AssociationThread[cpts, RegionIntersection @@@ vcells]] BlockRandom[SeedRandom["voronoi"]; pts = RandomReal[{-1, 1}, {32, 3}]]; lloyd = With[{maxit = 50,(*maximum iterations*) tol = 0.005 (*distance tolerance*)}, FixedPointList[Function[pts, RegionCentroid /@ Values[VoronoiCells[pts, {{-1, 1}, {-1, 1}, {-1, 1}}]]], pts, maxit, SameTest -> (Max[MapThread[EuclideanDistance, {#1, #2}]] < tol &)]]; frames = Function[pt, Show[MapIndexed[BoundaryMeshRegion[#, MeshCellStyle -> {1 -> Black, 2 -> {Opacity[0.5], ColorData @@ #2}}] &, Values[VoronoiCells[pt, {{-1, 1}, {-1, 1}, {-1, 1}}]]], Graphics3D[{PointSize[Large], Point[pt]}], Axes -> True, Boxed -> True, Method -> {"RelieveDPZFighting" -> True}]] /@ lloyd; ListAnimate[frames] `  Answer