// Voronoi Diagram in GenerativeComponents

# Voronoi Diagram in GenerativeComponents

Bentley Expert

Share

Voronoi Diagram or Voronoi tessellation is abundantly found in nature. There are also some examplesĀ inĀ architecture where Voronoi is used. It’s not only the aesthetics that makesĀ VoronoiĀ diagramĀ specialĀ but it has some unique properties that makes it very useful in solving real life problems.Ā Ā

In this section, we will see how we can create Voronoi Diagram in GCĀ and alsoĀ how we can use its properties in solving some practical problems.Ā Ā

First letās understand what is Voronoi diagram.Ā Ā

Now, imagine there are few points in a plane, we call it the Voronoi Sites. Thus, Voronoi diagram divides the plane in a set of regions based on the Voronoi Sites.Ā

These regions are called VoronoiĀ Region orĀ Cells. Every cell is associated with its corresponding Voronoi Sites.Ā

Any new points lying inside any Voronoi Cell will be closest to its corresponding Voronoi Site.Ā

To create the Voronoi we will use the Generated-Node-Types(GNT) Voronoi. You can learn more about GNT from thisĀ wikiĀ .Ā

The node required some points as input. We can create some random points as shown in thisĀ wiki. These points will act as the Voronoi Sites.Ā

## Properties of Voronoi Diagram and Its ApplicationsĀ

• A Voronoi Edge is a perpendicular bisector of two Voronoi Sites.Ā Ā

Now, imagineĀ the VoronoiĀ Sites as number of persons in an area. Now you want to traverse through this area with maximumĀ possibleĀ social distancing from everyone. The path formed by the Voronoi edges will be the best path for this situation.Ā  Such paths are also helpful in motion planning for finding obstacle avoiding route.Ā

So, we can extract the Voronoi Edges as line segment with property ‘VoronoiEdges’ of the Voronoi GNT node.Ā

• The point at which 3 perpendicular bisectors meet is a Voronoi Vertex and this vertex act as the center of an empty circle which only contains 3 Voronoi sites in the circle’s boundary.Ā  No other sitesĀ lieĀ inside this circle.Ā Ā

Imagine we want to set up a new food store and this store location should be furthest away from its competitor stores. Then the Voronoi Vertex with largest empty circle will be the ideal location to set up the store.Ā Ā

To find out this location we can use the property ‘LargestEmptyCircleLocation’. Also, for the radius of the circle there is can use the property ‘largestEmptyCircleRadius’.Ā Similarly, thereĀ are also properties ‘SmallestEmptyCircle’ and ‘SmallestEmptyCircleRadius’.Ā Note,Ā thisĀ  propertyĀ always report circle center inside the Convex Hull.Ā

• Delaunay triangulationĀ is the dual graph of Voronoi Diagram.Ā Ā Ā

The pair of Voronoi Sites that form the shortest edge of thisĀ Delaunay triangulationĀ is the closest pair.Ā Ā

To find the closest pair we can use the property ‘ClosestPair’.Ā

## Voronoi Implementation in GenerativeComponentsĀ

First,Ā we create theĀ Delaunay triangulationĀ by using the Mesh Node.Ā Ā

Then we calculate the circumcenter ofĀ each and everyĀ triangle.Ā

And, finally we connect the circumcenters with its adjacent circumcenters to get the Voronoi Diagram.Ā Ā

Ā

## LimitationsĀ

• Even though we are able to query several useful information from the Voronoi DiagramĀ inĀ linear timeĀ complexityĀ but the algorithm used here to generate the Voronoi Diagram has quadratic time complexity. A better alternative would be to use ‘Fortune’s Algorithm’.Ā
• So, The efficiency of the Voronoi Diagram depends upon the quality ofĀ Delaunay triangulation. Delaunay triangulationĀ needs to be formedĀ properly. Otherwise similar toĀ below issues may appear.Ā Ā

Also, to avoid such issues, we can change our point locations or regenerate the random points.Ā

Ā

Relevant Tags