10
$\begingroup$

Consider the following:

SeedRandom["blah"];
pts = RandomReal[1, {50, 2}];

{cm = ConvexHullMesh[pts],
 vm = VoronoiMesh[pts, Epilog -> {Red, PointSize[Small], Point[pts]}]} // GraphicsRow

convex hull and Voronoi diagram

I want to generate the Voronoi diagram bounded by the convex hull. I had tried using RegionIntersection but all I get is the original convex hull. Is there a way to cut out the parts of the Voronoi diagram that are outside the convex hull, such that the result is still a MeshRegion object?

$\endgroup$
14
$\begingroup$

Here is an approach that should get you there:

SeedRandom["blah"]; pts = RandomReal[1, {50, 2}];
cm = ConvexHullMesh[pts];
vm = VoronoiMesh[pts, Epilog -> {Red, PointSize[Small], Point[pts]}];

The idea is to find the RegionIntersection of the Voronoi cells with the convex hull of the sites, and to combine these regions to get the Voronoi diagram bounded by the convex hull:

prim = MeshPrimitives[vm, 2];
allreg = RegionIntersection[cm, BoundaryDiscretizeRegion @ #] & /@ prim;
allprim = Map[MeshPrimitives[#, 2] &, allreg][[All, 1]];

We now have the Voronoi cells bounded by the convex hull. Let's visualize it:

gr = Graphics[{{EdgeForm[Black], RandomColor[], #} & /@ allprim, Point[pts]}]

Mathematica graphics

Together with the original Voronoi diagram:

Show[vm, gr]

Mathematica graphics

To obtain a MeshRegion from the bounded Voronoi diagram we simply do the following:

reg = DiscretizeGraphics @ RegionPlot @ allreg

Mathematica graphics

We can check that it is indeed a MeshRegion:

{MeshRegionQ[reg], Head[reg]}

{True, MeshRegion}

Update

Here is a simplified approach thanks to @J.M.:

SeedRandom["blah"]; pts = RandomReal[1, {50, 2}];
cm = ConvexHullMesh[pts];
vm = VoronoiMesh[pts];
ch = MeshPrimitives[cm, 2][[1]];
DiscretizeGraphics[RegionIntersection[ch, #] & /@ MeshPrimitives[vm, 2]]
$\endgroup$
  • 2
    $\begingroup$ As it turns out, generating the bounded Voronoi diagram can be done quite compactly: ch = MeshPrimitives[cm, 2][[1]]; DiscretizeGraphics[RegionIntersection[ch, #] & /@ MeshPrimitives[vm, 2]] $\endgroup$ – J. M. is away Dec 21 '16 at 13:03
  • $\begingroup$ @J.M. That's a better approach. Do you want to add that as an answer? $\endgroup$ – RunnyKine Dec 21 '16 at 19:19
  • $\begingroup$ I'm okay with you editing your answer to show the simplification. :) $\endgroup$ – J. M. is away Dec 22 '16 at 1:30
  • $\begingroup$ @J.M. Done. :) ${}$ $\endgroup$ – RunnyKine Dec 22 '16 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.