Additively weighted Voronoi diagram(Open 5/Sep/2000 : The 2nd Revision Saturday, 03-Jul-2010 21:13:45 JST)

Additively weighted Voronoi diagram is drawn by using distance function d(p,p(i))

d(p,p(i))=dis(p,p(i))-w(i)

where dis is Euclidean distance and w(i) is the weight of p(i).

An edge is generally a hyperbolic arc.

Algorithm

Sort generators such that w[1]<w[2]<...<w{N] i=1,...,N-1 j=i+1,...,N Consider a bisector of p(i) and p(j) hyperbolic arc; that is, difference of two distances (distance to i and distance to j) is constant. At first, rotate i and j such that two y-coordinates are same. Next, move two points such that middle point of i and j become origin point. That is, i and j become two foci as (-a,0) and (a,0). Compute hyperbolic arc (x,y) for (-a,0), (a,0) and rotate back, move back. Regarding to parameters, see Okabe, Boots, Sugihara, Chiu. Spatial Tessellations, Wiley. for x=0 to right edge of screen compute y for x, hyperbolic arc compute d from (x,y) to i set cnt=0 k=1,...,N except for i and j compute d_k from (x,y) to k if d_k<d then cnt=1 and break next k if cnt=0 then plot (x,y) next x make y loop if need next j next i

Java(awvoro.java)

If you have a message, don't hesitate to send it by using

E-mail:Mail Form

or

BBS

Use of Takashi Ohyama's website

English Home of Takashi Ohyama

Japanese Home of Takashi Ohyama