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

Automatic versionCenter problemEmpty circle, Largest empty circleLargest empty ellipse
Click versionCenter problemEmpty circle, Largest empty circle-
Voronoi diagram(Automatic version)EVoronoi diagram(Click version)
Farthest point Voronoi diagram(Automatic version)EFarthest point Voronoi diagram(Click version)
Elliptic Voronoi diagram(Automatic version)
Ordinary Voronoi diagram(Open 2/Sep/2000 : The 13th Revision Thursday, 03-Jun-2010 22:12:51 JST)


There are some points (facilities) in a region. Let us assume that consumers use the nearest facility. Then, the Voronoi diagram explains the catchment area of each facility.
Let us define n points as p(1),...,p(n). The Voronoi region of p(i) is explained by
V(p(i)) = {x|d(x,p(i) ? [Note: Please check the change.] d(x,p(j), for all j(not i)}.
In the case of an Ordinary Voronoi diagram, the distance d is Euclidean.
The Voronoi diagram comprises the set of Voronoi regions,
{V(p(1),...,V(p(n))}.
An edge of an ordinary Voronoi diagram is generally a segment of a perpendicular at a midpoint.

Voronoi diagram for square lattice generators
Voronoi diagram like spider web 1
Voronoi diagram like spider web 2
Voronoi diagram like beehive
Voronoi diagram for hexagonal lattice generators

Reference
A.Okabe, B.Boots, K.Sugihara, WILEY, SPATIAL TESSELLATIONS

Source of program


Java(voro.java 6KB)
MS Visual Basic(vbvoro.lzh)

Algorithm

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 i

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