------------------------------------------------
             Short Description of the Software 
          for the Two-Dimensional Voronoi Diagram
                   for General Figures

           Kokichi Sugihara (University of Tokyo)
                       November 1997
      ------------------------------------------------

     The present version of the software for constructing the
Voronoi diagram for general figures in the plane consists of 
the following three files.

  readme_sivgf.txt: this text
  sivgf.f:       Fortran source code
  data.dat:   example of the input data

To use this software system in Unix Operating System, first
compile the Fortran program in "sivgf.f" by typing

  f77 sivgf.f

and next execute the program by typing
 
  a.out

The program reads the data about general figures from the file 
"figure.dat".  
     The file "figure.dat" is a text file, in which we can
specify any number of points, line segments, arcs, poligons,
and closed curves represented by cubic B-splines. The following
is an example of the content of "figure.dat". 

POINT
  0.5  0.5
LINE
  0.1  0.3  0.7  0.0
ARC
  -0.5  -0.5  -0.8  -0.5
   135.0  250.0
SPLINE
  5
   -0.8   0.6
   -0.4   0.2
   -0.1   0.3
   -0.1   0.8
   -0.5   0.4
POLYGON
  6
  -0.3   -0.3
  -0.1   -0.7
   0.2   -0.5
   0.3   -0.1
   0.0   -0.4
  -0.1    0.0
END

     A point is specified by two lines

POINT
  x   y

where (x,y) represent the coordinates of the point.

     A line segment is specified by two lines

LINE
    x1  y1  x2  y2

where (x1,y1) and (x2,y2) are the two terminal points of
the line segment.

     A polygon with n vertices is specified by n+2 lines

POLYGON
   n
   x1  y1
   x2  y2
     .
     .
     .
   xn  yn

where (xi,yi) represents the i-th vertex of the polygon. 

     An arc is specified by three lines

ARC
   x0  y0   x1   y1
   d1  d2

where (x0,y0) represents the center of the circle containing
the arc, (x1,y1) represent a point of the circle containing 
the arc, and d1 and d2 are the start and end direction
measured counterclockwise from the x-direction.

     A closed B-spline curve with n control points is 
specified by n+2 lines

SPLINE
   n
   x1  y1
   x2  y2
     .
     .
     .
   xn  yn

where (xi,yi) represents the i-th control point. 

     These geometric elements should be inside the region

   -1  <= x,y <= 1

and they should be disjoint from each other.  They can be 
written in any order in the file "figure.dat".  The file
should end with the line

END

     The present version does not support the case where
all the figures align in a straight line.

    After reading the figure data, the program generates
many points along the figures and constructs the Voronoi
diagrams for those points.  Then, the program removes the
Voronoi edges shared by two points belonging to the same
figure, and thus constructs the approximation of the
Voronoi diagram for the figures.  The output is given in
the file "draw.ps".  The first page of the output is the
approximate Voronoi diagram for the figures, and the second
page is the associated Voronoi diagram for points.

                            ---  end of the description  ---