Reload

Voronoi diagrams (Automatic version)	Ordinary	Multiplicatively Weighted /Area	Additively W /Area	PW(additively Weighted Power)	Compoundly W	LW(L_{weight} norm)
	Higher-order	HMW	HAW	HPW	HCW	HLW
	Elliptic	Manhattan	Supremum	Karlsruhe	Farthest-point
	HElliptic	HManhattan Farthest-Point Manhattan	HSupremum	HKarlsruhe	Higher-order Farthest-point
	line-segment		line-segments sometimes cross each other		line-segments need to cross each other	largest empty circle in a polygon
	Higher order line-segment		Higher 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 Tessellation	order-2 Delaunay	Order-3 Delaunay	Farthest Delaunay
	Delaunay some edges deleted	-	-	Extended Voronoi Edges	-	-
	Voronoi area game for two	for three	for four	for five	for six	-
Voronoi diagrams (Click version)	Ordinary	-				Largest Empty circle in a polygon
	Higher-order
	-	Manhattan	Supremum	Karlsruhe	Farthest-point
		HManhattan Farthest-Point Manhattan	HSupremum	HKarlsruhe
	Area of Voronoi Region	Delaunay Tessellation	order-2 Delaunay	Order-3 Delaunay	Farthest Delaunay
	Voronoi area game for two	for three	for four	for five	for six	-

CW, LW and Karlsruhe are very heavy.

Screensaver for Win 95,98

Automatic version	Center problem	Empty circle, Largest empty circle	Largest empty ellipse
Click version	Center problem	Empty 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)

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

Mail Form