Message Boards Message Boards

GROUPS:

3D version of the built-in VoronoiDiagram

Posted 14 days ago
246 Views
|
6 Replies
|
15 Total Likes
|

Open in Cloud | See Original | Download to Desktop via Attachments Below

enter image description here

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[10000];
pts = RandomReal[1, {10, 3}];

vc = VoronoiCells[pts]

enter image description here

Show[MapIndexed[
  BoundaryMeshRegion[#, MeshCellStyle -> {1 -> {Black, Thick}, 2 -> {ColorData[112][First[#2]]}}] &, 
  Values[vc]
]]

enter image description here

Show[
  MapIndexed[
    BoundaryMeshRegion[#, MeshCellStyle -> {1 -> Black, 2 -> {Opacity[0.5], ColorData[112][First[#2]]}}] &, 
    Values[vc]
  ], 
  Graphics3D[{PointSize[Large], Point[pts]}], 
  Method -> {"RelieveDPZFighting" -> True}
]

enter image description here

Note that this works in 2D too:

SeedRandom[10000];
pts = RandomReal[1, {10, 2}];

vc = VoronoiCells[pts];

Show[MapIndexed[
  BoundaryMeshRegion[#, MeshCellStyle -> {1 -> {Black, Thick}, 2 -> {ColorData[112][First[#2]]}}] &, 
  Values[vc]
], Epilog -> {PointSize[Large], Point[pts]}]

enter image description here

Attachments:
6 Replies

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]

Aha, thanks!

Posted 13 days 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?

A most excellent function and one that is needed. Thanks ! the function should be scaled up and made part of version 12.0 !

enter image description here - 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!

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract