Home / Software Posts / Voronoi Diagram in GenerativeComponents

Voronoi Diagram in GenerativeComponents

Bentley Expert Profile Image

Bentley Expert

GenerativeComponents

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.  

Voronoi Diagram GenerativeComponents 14 - KB


Image: Recreating Voronoi Pattern and its close resemblance with Giraffe Pattern 
(image source: https://quantdare.com/k-means-algorithm/giraffe-59009_1920/) 

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. 

Voronoi Diagram GenerativeComponents 14 - KB

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

Voronoi Diagram GenerativeComponents 14 - KB

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

Voronoi Diagram GenerativeComponents 14 - KB

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.  

    Voronoi Diagram GenerativeComponents 14 - KB

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. 

Voronoi Diagram GenerativeComponents 14 - KB

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.  

    Voronoi Diagram GenerativeComponents 14 - KB

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. 

Voronoi Diagram GenerativeComponents 14 - KB

  • 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 Diagram GenerativeComponents

Voronoi Implementation in GenerativeComponents 

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

Voronoi Diagram GenerativeComponents

Then we calculate the circumcenter of each and every triangle. 

Voronoi Diagram GenerativeComponents

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

Voronoi Diagram GenerativeComponents

 

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.  

    Voronoi Diagram GenerativeComponents

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

Additionally, an example of Façade generated using Voronoi Pattern.  

Voronoi Diagram GenerativeComponents

 

Relevant Tags

Both CAD (Computer-Aided Design) and BIM (Building Information Modeling) are popular software technologies used in the architecture, engineering, and construction ...
Whether it is a small renovation project or a massive university campus, centralized storage and sharing of this ever-increasing amount ...
Save valuable project time, increase productivity, and streamline your workflow with MicroStation’s default shortcuts! Shortcuts provide easy and quick access ...