Automatic version | Center problem | Empty circle, Largest empty circle | Largest empty ellipse |
---|---|---|---|

Click version | Center problem | Empty circle, Largest empty circle | - |

Farthest point Voronoi diagram(Automatic version)EFarthest point Voronoi diagram(Click version)

Elliptic Voronoi diagram(Automatic version)

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