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