CW, LW and Karlsruhe are very heavy.
Higher order Voronoi diagram(Open 5/Sep/2000 : The 5th Revision Wednesday, 03-May-2006 23:02:21 JST)
If we use Higher order Voronoi diagram, we can find out the 2nd or 3rd nearest facility.
White is the first order, green is 2nd, and blue is 3rd.
Algorithm for the higher order Voronoi diagrams (If you want draw the l-th order Voronoi diagram, then m=1,2,...,l)
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 points of intersection of bisector(i,j) and bisector(i,k)
next k
Add the points at x=0 and x=(the width of the screen) of the bisector of i and j into points of intersections
Sort points of intersections in turns of x coordinates
k=1,...,the number of interval of points of intersections
Let c be a middle point of interval of points of intersection
Let d be d(c,p(i))
label=0
h=1,...,N except for i and j
Let d' be d(c,p(h))
If d'<d then label=label+1
next h
If label=m-1, then draw the interval of points of intersection by m-th order's color.
next k
next j
next i
And the following is the algorithm of the ordinary Voronoi diagram. It is very similar.
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 points of intersection of bisector(i,j) and bisector(i,k)
next k
Add the points at x=0 and x=(the width of the screen) of the bisector of i and j into points of intersections
Sort points of intersections in turns of x coordinates
k=1,...,the number of interval of points of intersections
Let c be a middle point of interval of points of intersection
Let d be d(c,p(i))
label=0
h=1,...,N except for i and j
Let d' be d(c,p(h))
If d'<d then label=1
next h
If label=0, then draw the interval of points of intersection
next k
next j
next i
Java(hivoro.java)
If you have a message, don't hesitate to send it by using
E-mail:
Easy subject (which starts with 'about nirarebakun.com') to understand, please.
Because I'm afraid to get a virus mail or ad-mail, I delete the mail if the subject is abnormal.
Good example for subject:
About nirarebakun.com:Voronoi diagram
About nirarebakun.com:I'm interested in Steiner problem
Bad example for subject:
'Hello', 'Thank you', 'How do you do', 'Please', 'I love you', 'Re', 'Document', 'Excel file', 'Product' and so on.
And don't attach the file when you send the first mail.
or
BBS
English Home of Takashi Ohyama
Japanese Home of Takashi Ohyama