Multiplicatively weighted Voronoi diagram(Open 5/Sep/2000 : The 4th Revision Wednesday, 30-Jun-2010 23:04:07 JST)

Multiplicatively 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 are generally circular arc.

Algorithm

Multiplicatively weighted Voronoi diagram 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) Apporonius' circle; they mean that points are the rate of distance from i and distance from j is same. for x=left edge of circle to right edge of circle compute y for x, upper arc of the circle 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) compute y for x, lower arc of the circle 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 for y=bottom of circle to top of circle same logic of x next y next j next i Ordinary Voronoi diagram i=1,...,N-1 j=i+1,...,N Consider a bisector of p(i) and p(j) k=1,...,N except for i and j Consider a bisector of p(i) and p(k) Calculate the points of intersection of bisector(i,j) and bisector(i,k) next k Add the points x=0 and x=(the width of screen) of the bisector (i,j) into the points of intersections Sort the points of intersections in terms of x coordinates k=1,...,the number of intervals of the points of intersections Let c be a midpoint of the interval of the points of intersection. Let d be d(c,p(i)) h=1,...,N except for i and j Let d' be d(c,p(h)) If d'<d then shout (Out!) next h If we did not shout, then draw the interval of the points of intersection next k next j next iJava(mwvoro.java)

VB code(voromwexe.lzh)

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