Create a Voronoi diagram

Previous Top Next

ic_0056 Purpose of building Voronoi diagram is to construct a set of polygons - areas contouring point objects marked on a map, in accordance with the stringent requirements. Mathematically the model of diagram was described in 1908 by George Fedoseyitch Crows, hence the name of the diagram.

In general, the Voronoi diagram of a finite set of points P on the plane is a such partition of the plane in which each region of this partition forms a set of points that are closer to one of the elements of P, than to any other element of the set.

 

Polygon (cell) of Voronoi :

_engbm5578

 

In practice, the Voronoi diagram is used as a complete solution for a choice of the optimal partitioning the territory.

A classic example of Voronoi diagram - a breakdown of the city into districts based on the distribution of its post offices so that each point of each district office is located just near the center of the neighborhood.

Another example of using the Voronoi diagram is the study of behavior and care of living things that depend on the number of neighbors with whom they compete for food. In this case, the Voronoi diagram is the areas of habitat and the limits of the contact of living beings.

However, the Voronoi diagram can be used to solve other important geometric functions: the search for the nearest neighbor, the construction of the Delaunay triangulation, finding the largest voids (circle, inscribed into a cell), to construct a minimum spanning tree, and others.

As can be seen from figure 1, building of Voronoi diagram consists of an iterative construction of the Voronoi polygons for all specified points. To construct the Voronoi diagram is necessary: mark the dot objects on a map and click the mode button. As a result, polygonal objects corresponding to Voronoi polygons  will be put on the map. Objects are put on the map specified in the configuration "Geodesy Editor" on page "Editor". Thus, the type of polygon object specified in settings is used. Before constructing a Voronoi diagram is recommended to perform the task "Map Sorting" having specified in item "Coordinates precision" the value "Maximum".