2
$\begingroup$

I have this application at hand: I need to find the Voronoi Regions of a finite set of point and then i have to find the center of mass of each of these Voronoi regions for a given mass distribution. The Voronoi regions can be constructed through VoronoiMesh function, simple enough. But from this MeshRegion object I want to select individual cells and make each a MeshRegion so that I can pass it on to NIntegrate that computes the center of mass. How to do this selection and construction of meshregions out of the cells?

$\endgroup$
  • $\begingroup$ Take a look at MeshPrimitives. $\endgroup$ – kirma Feb 26 '16 at 9:13
  • $\begingroup$ that just returns a list of polygons. how do i make say each individual polygon into a new MeshRegion? $\endgroup$ – Iconoclast Feb 26 '16 at 11:07
  • $\begingroup$ You can extract coordinates of MeshRegion with MeshCoordinates, and construct a new mesh regions with each individual cell in MeshCells list from it, but that's a bit excessive. Points, lines, polygons and three-dimensional regions provided by MeshPrimitives should be directly usable in symbolic regions computation, such as a specification of region of integration using Element. $\endgroup$ – kirma Feb 26 '16 at 11:41
  • $\begingroup$ @kirma is right: the primitives returned by MeshPrimitives can be used directly in further computation. However, if you absolutely positively have to have mesh regions, you can use DiscretizeRegion. For example if vm is the output of VoronoiMesh, then DiscretizeRegion /@ MeshPrimitives[vm, 2] will give you a list of mesh regions corresponding to the cells of the Voronoi tessellation. $\endgroup$ – MarcoB Feb 26 '16 at 11:45
  • 1
    $\begingroup$ @kirma Since the original regions are polygons more complex than triangles, they are definitely going to be split into smaller components (i.e. triangular cells). That shouldn't affect the integration though. Also, you may be able to minimize the number of mesh cells by specifying a high MaxCellMeasure value for DiscretizeRegion. $\endgroup$ – MarcoB Feb 26 '16 at 18:19
7
$\begingroup$

A Voronoi mesh is composed of convex polygons. If you can assume that the density of each mesh cell is uniform, then the center of mass corresponds to the centroid of the polygon. If that's the case, you can use RegionCentroid to determine the centroid of a geometrical region.

Generate a mesh from random points:

SeedRandom[25]
vm = VoronoiMesh@(pts = RandomReal[{0, 100}, {10, 2}]);
Show[vm, Graphics[{Black, PointSize[0.01], Point[pts]}]]

Voronoi diagram

Extract the graphics primitives corresponding to each mesh cell:

primitives = MeshPrimitives[vm, 2]
{Polygon[{{40.3579, 40.0372}, {15.2559, 39.468},
            {5.3674, 0.590703}, {34.8597, 19.3549}}], 
   Polygon[{{49.1342, 45.0309}, {73.7966, -7.1283},
            {96.6581, 62.1957}, {58.2447, 59.6855}}], <...> }

Calculate the position of the centroids:

RegionCentroid /@ primitives

(* Out:
{{22.5691, 24.3983}, {72.383, 36.8604}, {22.599, -3.52749}, {24.7894, 94.0762}, 
 {-7.97345, 79.5994}, {97.9175, 18.2534}, {-6.58202, 17.9851}, {79.3346, 91.7492}, 
 {52.4768, 8.87061}, {28.6069, 54.4739}}
*)

Show them on the diagram:

Graphics[{
   (* Generating points *)
   PointSize[0.01], Black, Point@pts,
   (* Voronoi cells *)
   EdgeForm[Black], FaceForm[None], primitives,
   (* centroids *)
   PointSize[0.02], Red, Point@centroids
}]

Mathematica graphics


If you still need to use integration (e.g. your density is non-uniform), you can use the Polygon regions directly as integration domains.

For instance, the following calculates the area of each primitive:

NIntegrate[1, {x, y} ∈ #] & /@ primitives

(* Out:
{738.533, 1721.1, 1018.74, 2155.02, 1844.03, 2324.13, 1808.98, 3795.38,
 1484.51, 1309.37}
*)

Note that the same result could have been obtained using Area, or RegionMeasure.

$\endgroup$
  • $\begingroup$ Thanks MarcoB. I did the same. Now another thing, which I think is actually a bigger problem. The outermost cells are actually unbounded regions (they extend to the entire plane. I have non-uniform mass density. How can I modify the outermost polygons/cells/regions so that NIntegrate treats them as unbounded, $\endgroup$ – Iconoclast Feb 26 '16 at 20:56
  • $\begingroup$ @Iconoclast What would you want to do with the unbounded cell? $\endgroup$ – MarcoB Feb 26 '16 at 21:01
  • $\begingroup$ I am trying to run the Loyd-Max algorithm for building a Vector Quantizer for a 2D Gaussian dsistribution. The Gaussian distribution is the mass density in my case and is unbounded. The algorithm is simple. first pick N random points. Build a Voronoi Regions for those points, find the center of mass of those regions and make these center of masses the starting new points and repeat until convergence. the problem is that the points for the outer regions do not seem to converge as they are unbounded. $\endgroup$ – Iconoclast Feb 27 '16 at 9:57
  • $\begingroup$ @Iconoclast, why not use ConvexHullMesh[] to pick out the unbounded regions, then? $\endgroup$ – J. M. will be back soon Feb 27 '16 at 13:14
  • $\begingroup$ I dont understand. ConvexHullMesh[] still gives bounded regions.... I want to integrate over unbounded domain/region. $\endgroup$ – Iconoclast Feb 27 '16 at 14:08

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.