Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Does anyone have any suggestions how to determine the perimeter, area and number of sides of each Voronoi cell in Voronoi diagram?

share|improve this question

2 Answers 2

up vote 16 down vote accepted

Look at TileAreas in ComputationalGeometry:

Needs["ComputationalGeometry`"]
boundary = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};
pts = RandomReal[{0, 10}, {100, 2}]
(Print[DiagramPlot[##]]; TileAreas[##]) & @@ 
 Prepend[BoundedDiagram[boundary, pts], pts]
(* {{0.261033,5.7592},{6.21362,4.0213},{4.44609,9.30305},
{7.10641,0.810209},{2.57901,9.65954},{2.34204,1.84401},
{7.76384,0.109391},{2.23168,6.84915},{5.59156,7.56046},{9.12543,8.8625}} *)

(* {6.3428,19.1094,4.97912,9.55327,5.70216,
17.6009,4.37766,10.6483,10.719,10.9674} *)

Simple Voronoi diagram

EDIT: Wait, you wanted perimeters too.

Function[{vert, adj},
  (Total[Norm /@ Subtract @@@ Partition[vert[[#[[2]]]], 2, 1, 1]]) & /@ 
   adj] @@ BoundedDiagram[boundary, pts]
(* {12.8885,17.3528,9.88682,14.4774,10.2263,16.1023,
      10.1097,13.5522,13.3678,14.3459} *)

SECOND EDIT: Number of sides

Length /@ BoundedDiagram[boundary, pts][[2, All, 2]]
(* {4, 6, 5, 5, 5, 6, 3, 6, 4, 5} *)

If you keep reusing the BoundedDiagram of many points, you should probably save it instead of recomputing each time like I'm doing.

share|improve this answer
    
Thank you very much. You are great. I just updated the question and added the number of sides. Sorry about that. Many thanks. –  DeeDee Mar 5 '13 at 1:41
    
once again, many thanks. –  DeeDee Mar 5 '13 at 1:48

It's been over a year but since v10 introduced some nice functionalities to do this elegantly, let's revisit this question:

SeedRandom[0]

We generate some points and get their voronoi diagram using VoronoiMesh

pts = RandomReal[4, {20, 2}];
vor = VoronoiMesh[pts, {{0, 4}, {0, 4}}]; (* bounded Voronoi diagram *)

We can visualize it:

HighlightMesh[vor, {Style[2, White], Style[1, Thick, Red], Labeled[2, "Index"]}]

Mathematica graphics

We compute the area:

cells = MeshCells[vor, 2]; (* The polygons that make up the Voronoi diagram *) 

cellcoord = Map[MeshCoordinates[vor][[#]] &, cells, {2}];

Now for the areas of the cells:

areas = Area /@ cellcoord
{0.268351623, 0.363854348, 0.593530101, 0.551019589, 0.2100959, 
0.834387817, 1.23476475, 0.974387879, 0.402543688, 0.7598375, 
0.367406133, 0.602977633, 1.44528808, 1.09751887, 0.737070268, 
0.957965221, 1.99269004, 1.00297181, 0.665233774, 0.938104973}

Edit: A cleaner way to compute the areas is to do:

areas = PropertyValue[{vor, 2}, MeshCellMeasure]
{0.268351623, 0.363854348, 0.593530101, 0.551019589, 0.2100959,
0.834387817, 1.23476475, 0.974387879, 0.402543688, 0.7598375,
0.367406133, 0.602977633, 1.44528808, 1.09751887, 0.737070268,
0.957965221, 1.99269004, 1.00297181, 0.665233774, 0.938104973}

We can check that the total area is indeed 16 (the area of the bounded Voronoi diagram $4^2$)

Total[areas]

16.

To compute the perimeters we use RegionMeasure, convert the Polygon primitives to Line primitives and be careful to rejoin the lines.

RegionMeasure /@ (MeshPrimitives[vor, 2] /. Polygon[{x_, y__}] :> Line[{x, y, x}])
{2.77069922, 2.75359368, 3.55025756, 3.18751374, 2.08804226,
3.88434627, 4.40972038, 4.1388012, 2.60374389, 3.63582752,
3.21414867, 3.35140366, 5.40562321, 4.33439806, 3.61356349,
4.20548555, 5.5852835, 3.99708806, 3.40604006, 4.05182545}

Finally for the number of sides of each cell, we simply do:

Length @@@ cells    

{4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 7, 8, 8}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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