Input to sp.cpp

-------------------------------------------------
Overview
	sp.cpp is run as follows:

	% sp < filename.in > filename.out

i.e., it takes its input from stdin and writes to stdout.  Here we
describe the form of the input file.  These files are not intended to be
written by hand; rather they would normally be created by some other
program.  Samples of these other programs are described elsewhere
within these pages.
	The input data is entirely two-dimensional.  It specifies a
collection of triangles, how they are glued together, and where the source
point is.  The source point must be a vertex. If the source is to be
interior to a face, or on an edge, then the user should first partition
the faces so that the source point becomes a vertex.
	Each triangle is described in in its own coordinate system.  Its
three vertices are given local labels 0,1,2, counterclockwise.  Vertex 0
is necessarily at the origin, vertex 1 is necessarily on the positive
x-axis.  And vertex 2 should have a positive y-coordinate.  Although only
three of the six coordinate values need be entered, since three are
required to be zero, the input file must include all six in the order
indicated.  The coordinates are floating point numbers (doubles in the
code), and although they could be entered as integers (when they happen to
be whole numbers), we follow the convention of representing them with
decimal points to visually distinguish them from the vertex labels, which
of course are always integers.
	In addition to the local vertex labels, each vertex has a unique
global label.  Although it would be possible to generate these labels from
the input, we assume they are available ahead of time, and the global
index of each triangle vertex must also be specified.
	How the triangles glue to one another is defined by appropriate
integer indices of faces and vertices.
	Finally, the source face and source vertex are specified at the
end of the file.


-------------------------------------------------
Detailed Specification

Let nV be the number of vertices, and nF the number of faces.
Each face must be a triangle.
Each face has a unique integer index in [0..nF-1].
Each vertex has a unique integer global index in [0..nV-1].
Each vertex also has a local index in {0,1,2}, representing 
	a ccw boundary traversal around each incident face.
Each triangle's shape is specified in 2D, with the 0-th vertex
	at the origin, and the 1st vertex on the positive x-axis,
	and the 2nd vertex with positive y-coordinate.
The gluing between the triangles is specified with the index of
	the three adjacent faces, and the local indices of their
	glued vertices.
An input file for sp.cpp consists of five pieces of information:

-------------------------------------------------
1. nF = number of faces (necessarily triangles)
2. nV = number of vertices
3. 2D coordinates and indices of vertices for each face
4. gluing instructions for each face
5. source vertex specified by: index of source face,
   and local index of vertex on face, {0,1,2}
-------------------------------------------------

Between any of the pieces, comments starting with # in the 
first char position are permitted.
Items 1, 2 should be self-explanatory.
Items 3, 4 and 5 are detailed below.
-------------------------------------------------
3. 2D coordinates and indices of vertices for each face F

nF lines of the form
	x0 y0 v0  x1 y1 v1  x2 y2 v2

where 
	(x0,y0) = (0.,0.) = vertex 0 of face F (long floats)
	(x1,y1) = (x1,0.) = vertex 1 of face F (long floats)
	(x2,y2) =           vertex 2 of face F (long floats)
	v0      = global index of vertex 0 of face F
	v1      = global index of vertex 1 of face F
	v2      = global index of vertex 2 of face F

The faces may be listed in any order.  However, the order is used to
assign face indices, which must be consistent with the gluing instructions
below.

Note that it is important to input the coordinates to as full precision as
is available, to ensure correct distance computations.

-------------------------------------------------
4. gluing instructions for each face F

nF groups of 3 lines, one per face edge, of the form
	af0 i0
	af1 i1
	af2 i2
(or these six numbers could be on one line)

where

	af0 = index of face adjacent to edge 0 of face F
	i0  = local index of the edge glued to edge 0 of face F
	af1 = index of face adjacent to edge 1 of face F
	i1  = local index of the edge glued to edge 1 of face F
	af2 = index of face adjacent to edge 2 of face F
	i2  = local index of the edge glued to edge 2 of face F

This is (admittedly) confusing.  Each of the three vertices of a triangle
face have a local index 0,1,2.  We define the edge ccw after vertex i
to be edge i.  So edge 0 runs from vertex 0 to vertex 1, etc.  Here is
an example.  Suppose F is the face whose gluing is being defined.
F' below is af0, for it is the face adjacent to edge 0 of face F.
In the illustration, the index i0 is 1 (*not* 2), because edge 1
of F' is the edge that glues to edge 0 of F.
               
              2
            /   \ 
           /     \ 
          /   F   \ 
         /0       1\ 
        +-----------+  (Numbers are vertex local indices)
        \ 2       1/
         \    F'  /
          \      /
           \    /
              0


If an edge of face F is a boundary edge, the two corresponding indices are 
-1 -1.
-------------------------------------------------
5. source vertex specified by: index of source face,
   and local index of vertex on face, {0,1,2}

This is straightforward, except that the source should not lie on
the boundary.  So if the data specifies a surface with boundary,
and the source is on the boundary, it is necessary to augment the
data to surround that boundary with dummy points so that the source 
is interior to the surface, and surrounded entirely by incicent faces.
The shortest paths to these dummy points can be ignored in the
output.

-------------------------------------------------