Message Boards Message Boards

GROUPS:

[GIF] Voronoi visualization

Posted 1 year ago
2015 Views
|
2 Replies
|
12 Total Likes
|

I recently saw a gif showing the growth of a Voronoi diagram on this wiki page. This gif shows a Voronoi diagram but restricts each cell to lie in a disk that slowly grows over time.

I decided to recreate this with the Wolfram Language and thought I'd share the code and final result here.

Visualization

First and foremost, here's the result:

enter image description here

Code

First I start off with 20 random points in 2D:

pts = RandomReal[{-1, -1}, {20, 2}];

Then I extract each point's Voronoi cell by calling VoronoiMesh and then arranging the primitives to correspond to pts.

voronoi = VoronoiMesh[pts, {{-1, 1}, {-1, 1}}];
prims = BoundaryDiscretizeRegion /@ MeshPrimitives[voronoi, 2];
prims = Table[First[Select[prims, RegionMember[#, p] &]], {p, pts}];

Let's quickly pause to make sure the cells correspond to the correct point.

MapThread[Show[#1, Epilog -> {Red, PointSize[Large], Point[#2]}] &, {prims, pts}][[1 ;; 5]]

enter image description here

Now that we have the primitives, we can show the scene with disks of radius $r$ by applying RegionIntersection at each cell with a disk of radius $r$.

First we will discretize a disk to force RegionIntersection to return a BoundaryMeshRegion.

disk[{x_, y_}, d_, n_:100] := BoundaryMeshRegion[CirclePoints[{x, y}, d, n], Line[Mod[Range[n + 1], n, 1]]]

Now at radius $r$ we intersect, which I packed into a function. First, here's the code for a single cell. It will take the Voronoi cell, its corresponding point, and a color for styling purposes.

colors = RandomColor[RGBColor[_, _, _, 0.3], 20];

PartialVoronoiCell[r_][p_, cell_, color_] := 
  BoundaryMeshRegion[
    RegionIntersection[disk[p, r], cell], 
    MeshCellStyle -> {1 -> Directive[Thick, GrayLevel[.5]], 2 -> color}
  ]

The main function will effectively map over each point. When $r \leq 0$, we just show the points.

PartialVoronoiCells[_?NonPositive] = Graphics[Point[pts], PlotRange -> {{-1, 1}, {-1, 1}}, PlotRangePadding -> Scaled[.0125]];

PartialVoronoiCells[r_] := 
  Show[
    MapThread[PartialVoronoiCell[r], {pts, prims, colors}], 
    Epilog -> Point[pts], PlotRange -> {{-1, 1}, {-1, 1}}, PlotRangePadding -> Scaled[.0125]
  ]

This function is fast enough to visualize the growth with Manipulate.

Manipulate[PartialVoronoiCells[r], {r, 0, 1}]

enter image description here

2 Replies
Posted 1 year ago

Very nice! Could be expanded to include other distance functions such as manhattanDistance etc...enter image description here

See also my Wolfram Demonstrations: expanding Voronoi and: FortunesAlgorithm

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!

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