9
$\begingroup$

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]}]]

enter image description here

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):

enter image description here

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
8
$\begingroup$

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[]]] & /@ 
  (Graphics`PolygonUtils`PolygonIntersection[#, borderpoly] & /@ 
     MeshPrimitives[vm, 2]);

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

enter image description here

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

enter image description here

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[]]] & /@ 
    (Graphics`PolygonUtils`PolygonIntersection[#, 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]}]

enter image description here

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]}]]

enter image description here

Improve this answer
$\endgroup$
7
  • $\begingroup$ .@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. $\endgroup$
    – TumbiSapichu
    Commented May 16, 2020 at 12:51
  • $\begingroup$ .@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. $\endgroup$
    – TumbiSapichu
    Commented May 16, 2020 at 15:14
  • 2
    $\begingroup$ 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. $\endgroup$
    – flinty
    Commented May 16, 2020 at 17:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – kglr
    Commented May 16, 2020 at 17:22
  • 1
    $\begingroup$ @TumbiSapichu, you can use Area /@ pieces2 $\endgroup$
    – kglr
    Commented May 16, 2020 at 18:31
5
$\begingroup$

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] &

disks clipping voronoi mesh

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]]
 ]

voronoi mesh with convex hull

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – TumbiSapichu
    Commented May 16, 2020 at 14:43
  • 1
    $\begingroup$ With respect to masking by the convex hull, see this as well. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented May 16, 2020 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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