<< NL_F_Vector2MatrixColumn NL_F: Function NL_F_VoronoiPlot >>

NARVAL >> NL_F: Function > NL_F_VoronoiIncremental

NL_F_VoronoiIncremental

Compute the Voronoi matrix of a set of points by incremetal algorithm.

Calling Sequence

[M] = NL_F_VoronoiIncremental(nx,ny,Lx,Ly,d)

Arguments

nx :

x-coordinates of points.

ny :

y-coordinate of points.

y :

y-coordinate of the point.

Lx :

Area width.

Ly :

Area height.

d :

Precision.

M :

Voronoi matrix.

Description

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.

Examples

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);

Dependency

NL_F_Bisection, NL_F_InterPolygonLine, NL_F_PointOfPolygon, NL_F_DistanceSiDj, NL_V_GrahamScan, NL_F_RemoveFirstOcc

Report an issue
<< NL_F_Vector2MatrixColumn NL_F: Function NL_F_VoronoiPlot >>