How to add 'border' to Voronoi diagram

Suppose I have a set of points pts, from which I generate a Voronoi diagram VD:

pts = RandomReal[{-1, 1}, {100, 2}];
VD = Show[VoronoiMesh[pts], Graphics[{Red, Point[pts]}]]


Now, as per the geometric transformation made with Voronoiesh[], we can observe that the area of the "outer" cells project themselves indefinitely until their edges intersect with another cell, so their area is much larger than that of the 'interior' cells.

My question is, how could I 'bound' the Voronoi diagram so that the outer cells have roughly the same area as the interior ones?

I'm thinking that a possible solution would require generating a 'mask' that bounds the region covered by pts, and then excluding the area outside this mask. I was thinking of generating such a mask as the merge of circles centered at each point, with a radius producing roughly the same area as the interior points.

A second solution I've been thinking of is to generate some excess of points ptsOuter, which cover an area external to the area within pts, roughly equally spaced than the pts. Then, make the Voronoi mesh on the set {pts, ptsOuter}, which I'd think would bound the points in pts by using the points in ptsOuter.

I am wondering if there is an easier or more efficient way than these ideas I currently have.

Thanks!

Edit: By 'border' I mean a limit that follows the distribution of the points in pts, imagine something like this at the end (the drawn border here, which would exclude the area outside it):

• May 16, 2020 at 12:40
• May 16, 2020 at 13:28

2 Answers

Update 2: An alternative way to specify the cropping region:

ClearAll[bsf, explode]
bsf = BSplineFunction[outerpoints[[FindShortestTour[outerpoints][[2]]]],
SplineDegree -> Automatic, SplineClosed -> True];

explode[f_] := f[#] + {{0, -#2}, {#2, 0}}.Normalize[f'[t] /. t -> #] &;

borderpoly = Polygon[explode[bsf][#, .2] & /@ Subdivide[100]];

pieces2 = BoundaryDiscretizeRegion[#, BaseStyle -> Opacity[.25,  RandomColor[]]] & /@
(GraphicsPolygonUtilsPolygonIntersection[#, borderpoly] & /@
MeshPrimitives[vm, 2]);

Show[pieces2, Graphics[{Red, Point[pts], Purple, PointSize[Medium],
Point @ outerpoints}], ImageSize -> Medium]


Use explode[bsf][#, .4] & when defining borderpoly to get

Update: Cropping frontier polygons and lines:

SeedRandom[1]
pts = RandomReal[{-1, 1}, {100, 2}];
vm = VoronoiMesh[pts];

mc = MeshCells[VoronoiMesh[pts], {1 | 2, "Frontier"}];

intm = RegionDifference[vm, MeshRegion[MeshCoordinates[vm], mc]];

borderpolygon = MeshPrimitives[BoundaryDiscretizeRegion[
TransformedRegion[intm, ScalingTransform[1.3 {1, 1}]]], 2][[1]];

pieces = BoundaryDiscretizeRegion[#,
BaseStyle -> Opacity[.25, RandomColor[]]] & /@
(GraphicsPolygonUtilsPolygonIntersection[#, borderpolygon] & /@
MeshPrimitives[vm, 2]);

outerpoints = Select[pts, Not @* RegionMember[intm]];

Row[{Show[vm, pieces, Graphics[{Red, Point[pts], Purple, PointSize[Medium],
Point @ outerpoints}], ImageSize -> Medium],
Show[pieces, Graphics[{Red, Point[pts], Purple, PointSize[Medium],
Point @ outerpoints}], ImageSize -> Medium]}]


Original answer:

You can use the second argument of VoronoiMesh to specify coordinate bounds:

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

Show[VoronoiMesh[pts, 1.1 {{-1, 1}, {-1, 1}}], Graphics[{Red, Point[pts]}]]


• .@kglr the issue is how to get these points so that they follow the 'border' of my points. I added a small edit to the question. May 16, 2020 at 12:51
• .@kglr thanks! The answer by @flinty is closer to what I was thinking of, but it uses a convex hull, which would obscure 'dents' in a blob of points, highlighting only the 'protrusions'. So, my hand-drawn boundary currently is my best illustration of the ideal solution to the problem. May 16, 2020 at 15:14
• If I follow correctly, it finds the shortest tour of the boundary points and creates a smooth BSpline bubble going through them.The 'explode' inflates that bubble in the direction of the normal vector to the spline. Really clever. May 16, 2020 at 17:02
• Thank you @flinty. That's exactly what the combination of bsf & explode does. ScalingTransform in the first update has the limitation to work in two directions only. Working with the normal vector we avoid this limitation.
– kglr
May 16, 2020 at 17:22
• @TumbiSapichu, you can use Area /@ pieces2
– kglr
May 16, 2020 at 18:31

You can do it like this in Cropping a Voronoi diagram but the result is a bit ugly

pts = RandomReal[{-1, 1}, {100, 2}];
vmsh = VoronoiMesh[pts];

poly2disk[cell_, radius_] :=
Block[{pts = MeshPrimitives[cell, 0][[All, 1]]},
Return[Disk[Mean[pts], radius]]
]
disks = DiscretizeRegion[
RegionUnion[poly2disk[#, 0.3] & /@ MeshPrimitives[vmsh, 2]]];

DeleteCases[
RegionIntersection[DiscretizeGraphics@#, disks] & /@
MeshPrimitives[vmsh, 2], _RegionIntersection] //
RegionPlot[#, AspectRatio -> Automatic] &


You could also mask the mesh with the convex hull if you're happy with the points lying on the edge having no space around them. Here I show the result on top.

cvxh=ConvexHullMesh[pts];
Show[
vmsh,
DeleteCases[
RegionIntersection[DiscretizeGraphics@#, cvxh] & /@
MeshPrimitives[vmsh, 2], _RegionIntersection] //
RegionPlot[#, AspectRatio -> Automatic] &
,
Graphics[Point[pts]]
]


Maybe scaling up the new mesh about the center of all points would expand the convex hull enough to include some space around the edges too if that's desired.

• This is something closer to what I was thinking about. The only problem I see is that my points usually are blobs with protrusions/depressions, so the convex hull would mask the 'depressions' in the shape, only highlighting the protrusions. May 16, 2020 at 14:43
• With respect to masking by the convex hull, see this as well. May 16, 2020 at 15:49