Reload
Voronoi
diagrams
(Automatic
version)
OrdinaryMultiplicatively Weighted
/Area
Additively W
/Area
PW(additively Weighted Power)Compoundly WLW(L_{weight} norm)
Higher-order HMWHAWHPWHCWHLW
EllipticManhattanSupremumKarlsruheFarthest-point
HEllipticHManhattan
Farthest-Point Manhattan
HSupremumHKarlsruheHigher-order Farthest-point
line-segmentline-segments sometimes cross each otherline-segments need to cross each otherlargest empty circle in a polygon
Higher order line-segmentHigher order line-segment
(segnebts sometimes cross each other)
Higher order line-segment
(segments need to cross each other)
Area of Voronoi Region
/MW Area
/AW Area
Delaunay Tessellationorder-2 DelaunayOrder-3 DelaunayFarthest Delaunay
Delaunay
some edges deleted
--Extended Voronoi Edges--
Voronoi area game
for two
for threefor fourfor fivefor six-
Voronoi
diagrams
(Click
version)
Ordinary-Largest Empty circle in a polygon
Higher-order
-ManhattanSupremumKarlsruheFarthest-point
HManhattan
Farthest-Point Manhattan
HSupremumHKarlsruhe
Area of Voronoi RegionDelaunay Tessellationorder-2 DelaunayOrder-3 DelaunayFarthest Delaunay
Voronoi area game
for two
for threefor fourfor fivefor six-
CW, LW and Karlsruhe are very heavy.
Screensaver for Win 95,98

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