README for Geometry-0.02
		      Computional geometry module tree

			         Reini Urban
                               rurban@x-ray.at

MODULE DESCRIPTION

Name              DSLI  Description                                  Info
-----------       ----  -------------------------------------------- ------
Geometry          adpO  Computional geometry                         RURBAN

INTRODUCTION

  The perl Geometry module tree holds various modules for computional geometry.

  Some simple functions and data structures for the needed linear
  algebra, matrix and coordinate transformation, intersections, ...
  Advanced space or time efficient algorithms and data structures,
  dealing with pointsets (2D, 3D, nD) and 2D polygons, like decompositions,
  convex hulls, intersections, location queries.

  Geometry::Points   - Unordered 2D/3D Pointsets and Meshes
  Geometry::Polygon  - Simple and General Polygons in 2D with holes.
  Geometry::Delaunay  - Simple Mesh Generation without constraints
      Based on David Eberly's Magic Software code. In 2D or 3D
  Geometry::Triangle  - Quality and Constraint Mesh Generation
      based on Jonathan Shewchuk's triangle. Creates also a
      Voronoi diagram or the convex hull of a pointset.
  Geometry::Hull2D  - Convex Hulls in 2D
  Geometry::QHull   - Convex Hulls in arbitrary dimensions
  Geometry::MapOverlay  - Intersection of two maps
      Intersect a 3D mesh with a set of 2D polygons, project the
      polygons on to the mesh and create all intermediate polygon
      segments.

  You might need it for CAD, GIS or other graphics. This is a rewrite of
  existing lisp modules and interfaces which is in extensive use since years.
  Perl might be more appealing for converters and web-graphics.
  There will be also seperate AutoCAD module for DWG and DXF handling.
  (currently in alpha)

  There also exist various diverse modules like Math::Trig, Math::Matrix,
  Math::MatrixReal, Math::Geometry, but none is sufficient for computional
  geometry and simpler geometric calculations.

INSTALLATION

  Get the perl module at ftp://xarch.tu-graz.ac.at/pub/autocad/urban/perl/
    or http://www.perl.com//CPAN/authors/id/RURBAN/
    Also get an updated Tie::CArray if needed.
  If needed get triangle at http://www.cs.cmu.edu/~quake/triangle.research.html
  All other sources are included.

  Prerequisites needed:
      perl5.005 or 5.6  Earlier versions might need some CPAN modules which are
      			standard now.
			The xs modules use the Perl_ and PL_ prefixes which
			must be removed for 5.004 and earlier.
    * Math::Trig 1.00	Standard since 5.005. Not the CPAN module 0.02!
    * Tie::CArray       A copy is included with this package. The
      			latest module may be obtained seperately at CPAN.
      C compiler        (tested with egcs-1.1.2, gcc-2.95.2, msvc5+6)
      C++ compiler      for Geometry::Delauney
      triangle          for Geometry::Triangle
      			http://www.cs.cmu.edu/~quake/triangle.research.html

  Geometry installs as a standard Perl module:

      perl Makefile.pl
      make
      make test
      make install

  Tested Platforms:
      Win32

      Geometry::Polygon was developed under Win32 - MSVC6 - perl5.00502,
      5.00558 w/wo threads/debugging and additionally tested
      with cygwin32 - gcc 2.95 - 5.00563.
      It should be 5.6 ready and namespace safe.

      Please report other platforms to the author.
      I see no major difficulty for CC/gcc supported platforms,
      though Win32 is less strict than others.
      All external C/C++ sources are reported to compile fine under the
      major platforms. Hope my RCS didn't mess up the eof lines.
      You might tweak the makefiles, see polytri/makefile for rand48 and
      time.h defines.

  This is beta. Not fully tested and implemented yet!
  The interface is stable.

AUTHORS
  Atul Narkhede (narkhede@cs.unc.edu) and Dinesh Manocha wrote polytri,
    based on a paper by Raimund Seidel 1991.

  Graham Barr (gbarr@pobox.com) wrote reduce.

  David Eberly (eberly@magic-software.com) wrote Delaunay, based on a paper
    and on code by Dave Watson.

  Jonathan Shewchuk (jrs@cs.cmu.edu) wrote Triangle.

  Ken Clarkson wrote 2dch.c

  C. Bradford Barber (barber@geom.umn.edu) and Hannu Huhdanpaa
    (hannu@geom.umn.edu) wrote qhull.

  Reini Urban (rurban@x-ray.at) wrote the rest.

COPYRIGHTS
  Since this consists of various modules by different authors the different
  licenses are listed here for your convenience in decreasing strictness.
  See the specific docs as well, esp. for warranties.

* triangle is Copyright (c) 1996 by Jonathan Richard Shewchuk

    These programs may be freely redistributed under the condition that the
    copyright notices (including the copy of this notice in the code comments
    and the copyright notice printed when the `-h' switch is selected) are
    not removed, and no compensation is received.  Private, research, and
    institutional use is free.  You may distribute modified versions of this
    code UNDER THE CONDITION THAT THIS CODE AND ANY MODIFICATIONS MADE TO IT
    IN THE SAME FILE REMAIN UNDER COPYRIGHT OF THE ORIGINAL AUTHOR, BOTH
    SOURCE AND OBJECT CODE ARE MADE FREELY AVAILABLE WITHOUT CHARGE, AND
    CLEAR NOTICE IS GIVEN OF THE MODIFICATIONS.  Distribution of this code as
    part of a commercial system is permissible ONLY BY DIRECT ARRANGEMENT
    WITH THE AUTHOR.  (If you are not directly supplying this code to a
    customer, and you are instead telling them how they can obtain it for
    free, then you are not required to make any arrangement with me.)

* 2dch.c is Copyright (c) 1996 by AT&T

    Permission to use, copy, modify, and distribute this software for any
    purpose without fee is hereby granted, provided that this entire notice
    is included in all copies of any software which is or includes a copy
    or modification of this software and in all copies of the supporting
    documentation for such software.

* The Delaunay C++ code is Copyright (c) 1998 by David Eberly

    This free software is supplied under the following terms:
    1. You may distribute the original source code to others at no charge.
    2. You may modify the original source code and distribute it to others at
       no charge.  The modified code must be documented to indicate that it is
       not part of the original package.
    3. You may use this code for non-commercial purposes.  You may also
       incorporate this code into commercial packages.  However, you may not
       sell any of your source code which contains my original and/or modified
       source code (see items 1 and 2).  In such a case, you would need to
       factor out my code and freely distribute it.
    4. The original code comes with absolutely no warranty and no guarantee is
       made that the code is bug-free.

* qhull is Copyright (c) 1993 by The National Science and Technology
    Research Center for	Computation and Visualization of Geometric Structures
    (The Geometry Center), University of Minnesota.

    This software is copyrighted as noted above.  It is free software and
    may be obtained via anonymous ftp from geom.umn.edu.  It may be freely
    copied, modified, and redistributed under the following conditions:
    1. All copyright notices must remain intact in all files.
    2. A copy of this file (COPYING) must be distributed along with any
       copies which you redistribute; this includes copies which you have
       modified, or copies of programs or other software products which
       include this software.
    3. If you modify this software, you must include a notice giving the
       name of the person performing the modification, the date of
       modification, and the reason for such modification.
    4. When distributing modified versions of this software, or other
       software products which include this software, you must provide
       notice that the original source code may be obtained as noted
       above.
    5. There is no warranty or other guarantee of fitness for this
       software, it is provided solely "as is".  Bug reports or fixes may
       be sent to qhull_bug@geom.umn.edu; the authors may or may not act
       on them as they desire.

* reduce is Copyright (c) 1997 by Graham Barr. Same license as below.

* The rest (perl modules, xs, MapOverlay, Boolean, ...) is
    Copyrighted (c) 1999 by Reini Urban.

  This is free software; you can redistribute it and/or modify it under
  the same terms as Perl itself.

* polytri is in the public domain.

URL'S
  Perl Module:
    ftp://xarch.tu-graz.ac.at/pub/autocad/urban/perl/
    http://www.perl.com//CPAN/authors/id/RURBAN/
  Delaunay:
    http://www.magic-software.com
  polytri:
    http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
  triangle:
    http://www.cs.cmu.edu/~quake/triangle.research.html
  More:
    http://www.geom.umn.edu/software/cglist/trap.html

LAST CHANGED
    2000-01-11 02:16