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)
Line-segment Voronoi diagram(Open 4/Jul/2009 : The 2nd Revision Sunday, 23-Jan-2011 13:32:30 JST)



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


Algorithm
Consider N line segments.
i=1,...,N-1
    j=i+1,...,N
        Consider bisector of i and j
        1) bisector of two edge points of line segments
        1-1) bisector of i's left vertex and j's left vertex
        1-2) bisector of i's right vertex and j's right vertex
        1-3) bisector of i's left vertex and j's right vertex
        1-4) bisector of i's right vertex and j's left vertex
        In these 4 cases, compute slope a and intercept b of perpendicular bisector of two edge points, y=ax+b 
        for x=left point of the screen to right point of screen
            compute y=ax+b
            compute d=distance between (x,y) and edge points(distance to i and distance to j are same)
            compute d_epsi=distance between (x,y) and edge point of i*0.999+j*0.001 (this means inner point of line segment) 
            compute d_epsj=distance between (x,y) and edge point of j*0.999+i*0.001 (this means inner point of line segment) 
            if d_epsj<d or d_epsi<d then next x
            for k=1,...,N but not i,j
                compute d_k=distance from (x,y) to k (that is edge points or intersection of perpendicular line from k)
                if d_k<d then next x
            next k
            plot (x,y)
        next x

        2) Next, consider the bisector of two line segments, that is, the image is the bisector of an angles.
        There are two bisectors of an angles for line segments i and j.Compute these bisectors of an angles as (gux1,guy1)-(gux2,guy2) and (gux3,guy3)-(gux4,guy4)
        2-1) For (gux1,guy1)-(gux2,guy2)
        Compute a, b of y=ax+b for (gux1,guy1)-(gux2,guy2)
        for x=gux1 to gux2
            Compute y=ax+b
            Compute intersection of line segment i and perpendicular line from (x,y) to i.
            If the intersection is outside of line segment i, then next x
            Compute intersection of line segment j and perpendicular line from (x,y) to j.
            If the intersection is outside of line segment j, then next x
            Compute d, distance from (x,y) to i or j(to i and to j are same).
            For k=1,...,N but not i,j
                Compute d_k, distance from (x,y) to k.
                If d_k is less than d then next x
            next k
            plot (x,y)
        next x
        2-2) For (gux3,guy3)-(gux4,guy4). This is another bisector of an angle. 
        Use same logic of 2-1)

        3) Finally, consider the bisector of one line segment and one edge point of another line segment
        3-1) line segment i and left point of segment j
        3-2) line segment i and right point of segment j
        3-3) line segment j and left point of segment i
        3-4) line segment j and right point of segment i
        For these 4 cases, apply following method.
        When the line (directrix) is x=-lp and the point (focus) is (lp,0) then the parabola line is y^2=4lpx.
        At first, lp is set to the half of distance between segment i and edge point of j.
        Rotate segment i and edge point of j by the angle of segment i, that is, make line segment i x=lp. Next, move segment i and edge point of j such that the middlepoint of segment i and edge point of j become origin point, (0,0). From these actions, we can draw y^2=4lpx for segment i and edge point of j.
        Later, rotate back and move back. then you can draw exact parabola.
        Compute (gpboriginx,gpboriginy). This is origin point for segment i and edge point of j for y^2=4lpx.
        Compute gpbijep. This is lp when bisector is y^2=4lpx for line segment i and edge point of j.
        Compute gpbijetheta. This is angle of rotation when bisector is y^2=4lpx for line segment i and edge point of j.
        for(y=-height of screen to height of screen
            compute x=y^2/(4lp)
            Rotate back (x,y) for segment i and edge point of j.
            compute d as distance from edge point j to (x,y).
            compute da as distance from another edge point j to (x,y).
            if da<d then next y
            compute deps as distance from edge point*0.999+another edge point*0.001 j to (x,y). This means inner point very small epsilon.
            if deps<d then next y
            for k=1,...,N but not i,j
                compute d_k as distance from k to (x,y).
                if d_k<d then next y
            next k
            Plot (x,y)
        next y

    next j
next i

Source of program
Java(segvoro.java)
VB files and exe file(svoro.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