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

Manhattan-metric Voronoi diagram(Open 5/Sep/2000 : The 5th Revision Thursday, 03-Jun-2010 22:12:47 JST)


Manhattan-metric Voronoi diagram is drawn by using distance function d(p,p(i))
d(p,p(i))=|x-x(i)|+|y-y(i)|
where (x,y) is the coordinate of p, (x(i),y(i)) is the coordinate of p(i), |a| is a sign of absolute value.
Special case
Manhattan Voronoi diagram for square lattice generators
Manhattan Voronoi diagram for radial generators 1
Manhattan Voronoi diagram for radial generators 2
Manhattan Voronoi diagram for triangular lattice generators
Manhattan Voronoi diagram for hexagonal lattice generators

Algorithm
the concept is very close to that of the ordinary Voronoi diagram
Following algorithm is for the 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 at x=0 and x=(the width of the screen) of the bisector of i and 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
but the bisector of Manhattan Voronoi diagram is not line.
it is conbination of horizontal half-line, diagonal line segment and horizontal half-line (type 1) or
                      vertical half-line, diagonal line segment and vertical half-line(type 2)
           (See Okabe et al. Soatial tessellations 2nd ed. Fig. 3.7.2)
  this conbination type is decided by the difference of x-coordinate and difference of y-coordinate.
 that is, if difference of x-coordinates is larger than the difference of y-coordinates then type 2 and
         if difference of y-coordinates is larger than the difference of x-coordinates then type 1
         (I don't consider the case that the differences are exactly same because the probability is 0 since generators are made from random variables.)

By the way, I set y=400 x+? instead of the vertical half-line(x=?) of the type-2, sorry.

Java(man.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