The modules in this package fall under three basic groups.

(1) necessary for a real implemenation involving arrangements
(2) useful debugging code
(3) sample application code, which uses the data structures



***************************************************************
       modules necessary for implementation 
***************************************************************

----------------
Module:  arrange
----------------

This module is in charge of the core of this software.  It defines the
data structures for the representation of the arrangement, as well as
the routines for initializing and building the arrangement from the
input.

Related files:

arrange_type.h --- This file has the definitions of the data
  structures used in representing the arrangement.  It also has
  several 'private' functions which may be useful to other low
  level modules that want to look in depth at the data structures.
  This file should be included by any module that wishes to look in
  depth at the arrangement data structure.  (as opposed to viewing the
  arrangment as an abstract structure)  This is sort of the 'private'
  or 'friends' part of the module definition.  (that is, using C++
  terminology) 

arrange.h  ---  This file has the routine specification for the
  initialization functions as well as the insertion functions.
  This is the fully 'public' part of the module.

arrange.c --- This is the full implemenation of all the initialization
  and insertion routines for building up arrangements.

arrange_macros.h --- This is a special file that is optional but
  *strongly* suggested.  This defines macros to sit ontop of the
  data structures in arrange_type.h, and allows users to inquire about
  most of the fields in the arrangement data structures.  This file
  was created to allow code to be written which will allow a
  completely transparent upgrade to future possible changes in the
  arrangement data structures.  Also some macros access fields in
  a more intuitive way, whereas the original structures require
  following several pointers.  If the code were written in C++, these
  featuers would simply be inline inquiry functions.  In fact, if
  this software is encorporated into a project written in C++, it
  would be very natural to write a "shell" around this file to make
  the arrangement data structures appear to be C++ objects.  (Also,
  I would greatfully accept such a shell and add it to the available
  code if anyone volunteers such a shell)



---------------------
Module:  arrange_geom
---------------------

This module makes abstract data types to represent the geometry of
vertices and edges that appear in the arrangement.  The functions
provided here implement the basic geometric primitives such as testing
whether a vert is above or below and edge, or calculating the
intersection vertex from two edges.

This serves two purposes.  First, all code to handle various
degeneracies are built into these functions, allowing the main
arrangement module to view the world in a cleaner way.

Also, there are two strategies for dealing with possible numerical
accuracy.  One scheme is to use floating point data and to be
extremely careful about several possible problems that may arise due
to the precision problems inherent in any floating point calculations.
Of course, such a scheme is somewhat based on "hacks" in certain
cases, and it is very difficult to provided foolproof claims of
consistency.  However, the original software was based on such
floating point calculations, and thus a great deal of work has been
done towards handling such pitfalls in a bug-free manner.

Another solution to the problem of consistency is to force all of the
original input data to lie on an integral lattice.   In this way, all
calculations can be implemented using integer arithemetic and all
results can be done *exactly* without any later need to round or fudge
results or comparisons.   However, this scheme either reqires the
original data to be contained in a lattice of bounded size so that all
calculations can be done without fear of overflow, or it must be built
upon a package for large number arithmetic so that calculations can be
done on integers that do not necessarily fit into the standard sized
data types.  We've implemented a simple integer package based on using
a bounded lattice.


Related files:

arrange_geom.h --- This file has the definitions for the abstract
  geometric data types for a vertex and an edge.  It is not specific
  to what type of calculations are being done, or to the surface on
  which the arrangement lies.   That is, this file can be used for
  either floating point or integer based calculations.  Also, it may
  be used for arrangements on either a hemisphere or a plane.
  Instead, this gives the function definitions for a set of primitives
  which are maintained by the corresponding implementation of the
  module.  There are geometric test functions which answer queries
  such as whether a vertex or edge lies on the horizon, or whether a
  given vertex is incedent to an edge.  There are also functions to
  create new data such as taking two edges and returning a vertex
  at the intersection point.


arrange_geom_float.c --- This implements the geometric data types as
  floating point vectors.  Vertex geometries are represented as
  vectors on the unit sphere.  Edge geometries are represented by the
  unit normal to the edge.  (of course, these can also be thought of
  in terms of homogeneous coordinates as opposed to the spherical
  interpretation.)

arrange_geom_int.c --- This implements the geometric data types as
  integer vectors.  Vertex geometries are represented as vectors on
  a bounded lattice.  Edge geometries are represented by the normal to
  the edge.  (of course, these can also be thought of in terms of
  homogeneous coordinates as opposed to the spherical interpretation.)



---------------------
Module:  polygon
---------------------

This module has the representation of the input polygons which are
given as the highest level of input to the arrangment.   Many of the
decision for the design of this structure are due to the original
application for which this was developed.  This structure is used to
represent a polygon made up of sections of great circle arcs on the
unit sphere.  (again, this can be interpeted as homogeneous
coordinates, however on a two-sided projective plane.)

Besides the data structure definition, this module also provides some
useful functions such as reading/writing polygons from/to text, or
determining if a point is in the interior of a polygon.

Related files:

polygon.h --- This file has the data structure definition as well as
  the specifications for the related functions.

polygon.c --- This file has the implementation for the related
  functions.





---------------------
Module:  spheregeom
---------------------

This is a small module that has some functions and macros specific to
geometry on the sphere.  The macros here are for vector arithmetic.
The functions mostly involve the concept of a directed edge, that is one
which uses the choice of normals to represent a direction of travel
along the edge.

Related files:

spheregeom.h --- macro definition and function specifications

spheregeom.c --- function implementations


---------------------
Module:  lists
---------------------

This is a module which provides support for a basic doubly-linked list
structure.  A basic data type is defined as well as a library of
useful functions.

Related files:

lists.h   ---  the definitions and specifications
lists.c   ---  the function implementations


---------------------
Module:  dheap
---------------------

This module creates a very simple memory manager that can be used to
reduce the number of system calls and to help reduce page faults.
This can only be sued in cases where some group of objects may be
allocated individually, but can all be deleted simultaneously.  This
object will grab memory in chunks as needed and dole it out into
individual pieces.  The memory can only be deallocated as a group.

Related files:

dheap.h   ---  the function specifications
dheap.c   ---  the implementation


---------------------
Module:  standards
---------------------

Okay..this isn't really a module.  It's just a header file that has a
lot of garbage in it.  This is included by all other files, and it
allows for some very simple definitions and macros to be shared
throughout the project.  These could be moved elsewhere or combined
with another file when this software is merged with a larger program.

Related files:

standards.h ---  This is the header file





***************************************************************
       useful debugging code
***************************************************************

---------------------
Module:  arrange_debug
---------------------

This package has support for several different debugging tools for the
arrangement software.  None of these tools are necessary for using the
main software, however they will provide useful tools for debug
versions.  Four features are offered.   First, this allows an
arrangement to be dumped to a (long) text format which can then be
examined in detail.  Secondly, this allows an arrangement to be dumped
to a graphical package which will display the arrangement on a
hemisphere.  [See 'graphics' module below.]  Thirdly, this offers an
automated "sanity check" on an arrangement, which will attempt to find
any topological inconsistencies that may have resulted from a
potential bug in the construction of the arrangement.  Finally, this
package offers a text driven driver which allows someone to create
arrangements by hand by adding single vertices, edges, or whole
polygons directly. Also, this driver allows various other options such
as printing the arrangement to text and drawing the arrangement
graphically.

This also acts as an example application that used the main software
in various ways.  The sanity check routine, especially, demonstrates
how to poke around in the lowest levels of the arrangement data
structure.

Related files:

arrange_debug.h ---  This file defines the function specs.

arrange_debug.d ---  This file contains the implementation.


---------------------
Module:  debug_graphics
---------------------

This is a graphics package which provides some low level drawing
routines for displaying an arrangement on a hemisphere.  It is written
on top of the X.


Related files:

debug_graphics.h   ---  function declarations.

debug_graphics.c   ---  function implementation.


***************************************************************
       sample application code
***************************************************************

---------------------
Module:  main
---------------------

This is a very simple top level stencil that starts up the sample
driver for creating arrangements interactively.

Related files:

main.c  ---- The top level code


---------------------
Module:  traverse
---------------------

This is a sample of code that uses an arrangement that has already
been built.  It traverses the entire arrangement while keeping track
of what polygons are entered and exited during the traversal.  It
gives routines to perform a depth first search of the arrangment
either at the level of individual trapezoids or at the level of the
faces of the true arrangement without the artificial threads.

Related files:

traverse.h  --- some basic definitions and function declarations.

traverse.c  --- the function implementation.
