Compute the Voronoi matrix of a set of points by incremetal algorithm.
[M] = NL_F_VoronoiIncremental(nx,ny,Lx,Ly,d)
x-coordinates of points.
y-coordinate of points.
y-coordinate of the point.
Area width.
Area height.
Precision.
Voronoi matrix.
NL_F_VoronoiIncremental computes the Voronoi matrix M=(P1;P2; ... ;Pn) of a set of n>3 points of coordinates (nx,ny) by the following incremental algorithm (WIKIPEDIA). It is assumed that no triple of colinear points is present. The Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. In our approach, it is a subdivision of the plane into n cells of center Pi with i in [1:n]. let assume that we have already built the Vononoi diagram . If we add a new site
. We should first find the site whose Voronoi polygone contains
. Then we dray the perpendicular bisection between
and
. The bisection crosses the boundary polygon of
at two points N1 and N2. As a consequence N1N2 divides the Voronoi polygon
into 2 parts, whose one element belongs to the Voronoi polygon of
. We obtain a Voronoi Edge on the boundary of the Voronoi polygon of
. Afterwards we expand the boundary of the Voronoi polygon by finding the sequence of segments of perpendicular bisections of s and the neighboring sites until we reach the boundary of the plane.
nx=[100 200 500 600 750 900]; ny=[100 750 450 200 800 600]; Lx=1000; Ly=1000; he=[]; ta=[]; g=NL_G_MakeGraph('Voronoi',length(nx),ta,he,nx,ny); f=NL_G_ShowGraphN(g,1); [M]=NL_F_VoronoiIncremental(nx,ny,Lx,Ly,0.1);//application of NL_F_VoronoiIncremental dt=getdate(); seed=dt(10); rand('seed',seed);//initialization of the random values generator nx=int(NL_F_RandVectorCoord(10,Lx)); ny=int(NL_F_RandVectorCoord(10,Ly)); C=NL_F_ColinearSet(nx,ny); while (C <> []) nx=int(NL_F_RandVectorCoord(10,Lx)); ny=int(NL_F_RandVectorCoord(10,Ly)); C=NL_F_ColinearSet(nx,ny); end g=NL_G_MakeGraph('Voronoi',length(nx),ta,he,nx,ny); f=NL_G_ShowGraphN(g,2); [M]=NL_F_VoronoiIncremental(nx,ny,Lx,Ly,0.1);//application of NL_F_VoronoiIncremental NL_F_VoronoiPlot(M,2); | ![]() | ![]() |