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?

Improve this question
$\endgroup$
6
  • $\begingroup$ Take a look at MeshPrimitives. $\endgroup$
    – kirma
    Feb 26, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 18:19

1 Answer 1

Reset to default
9
$\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.

Improve this answer
$\endgroup$
5
  • $\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, 2016 at 20:56
  • $\begingroup$ @Iconoclast What would you want to do with the unbounded cell? $\endgroup$
    – MarcoB
    Feb 26, 2016 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, 2016 at 9:57
  • $\begingroup$ @Iconoclast, why not use ConvexHullMesh[] to pick out the unbounded regions, then? $\endgroup$
    – J. M.'s lack of A.I. ♦
    Feb 27, 2016 at 13:14
  • $\begingroup$ I dont understand. ConvexHullMesh[] still gives bounded regions.... I want to integrate over unbounded domain/region. $\endgroup$
    – Iconoclast
    Feb 27, 2016 at 14:08

Your Answer

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

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