extern/qhull/README.txt

   1 Name
   2
   3       qhull, rbox         2002.1           August 20, 2002
   4
   5 Convex hull, Delaunay triangulation, Voronoi diagrams, Halfspace intersection
   6
   7       Documentation:
   8         html/index.htm
   9
  10       Available from:
  11         <http://www.geom.umn.edu/software/qhull>
  12         <http://savannah.gnu.org/projects/qhull>
  13         <http://www.thesa.com/software/qhull>
  14
  15       Version 1 (simplicial only):
  16         <http://www.geom.umn.edu/software/qhull/qhull-1.0.tar.gz>
  17         <http://www.geom.umn.edu/software/qhull/qhull.sit.hqx>
  18
  19       News and a paper:
  20         <http://www.geom.umn.edu/~bradb/qhull-news.html>
  21         <http://www.geom.umn.edu/software/qhull/qhull-96.ps>
  22
  23 Purpose
  24
  25   Qhull is a general dimension convex hull program that reads a set
  26   of points from stdin, and outputs the smallest convex set that contains
  27   the points to stdout.  It also generates Delaunay triangulations, Voronoi
  28   diagrams, furthest-site Voronoi diagrams, and halfspace intersections
  29   about a point.
  30
  31   Rbox is a useful tool in generating input for Qhull; it generates
  32   hypercubes, diamonds, cones, circles, simplices, spirals,
  33   lattices, and random points.
  34
  35   Qhull produces graphical output for Geomview.  This helps with
  36   understanding the output. <http://www.geomview.org>
  37
  38
  39 Environment requirements
  40
  41   Qhull and rbox should run on all 32-bit and 64-bit computers.  Use
  42   an ANSI C or C++ compiler to compile the program.  The software is
  43   self-contained.
  44
  45   Qhull is copyrighted software.  Please read COPYING.txt and REGISTER.txt
  46   before using or distributing Qhull.
  47
  48 To contribute to Qhull
  49
  50   Qhull is on Savannah, http://savannah.gnu.org/projects/qhull/
  51
  52 Qhull on Windows 95, 98, ME, NT, 2000, XP
  53
  54   The zip file contains rbox.exe, qhull.exe, qconvex.exe, qdelaunay.exe,
  55   qhalf.exe, qvoronoi.exe, documentation files, and source files.
  56
  57   To install Qhull:
  58   - Unzip the files into a directory.  You may use WinZip32 <www.hotfiles.com>
  59   - Open a DOS window for the directory.
  60   - In Windows 95, the DOS window needs improvement.
  61       - Double-click on qhull\eg\qhull-go.bat to call doskey (arrow keys).
  62       - Increase the size of the screen font to 8x12.
  63       - If the text is too dim, fix the screen colors with shareware (e.g., crt.exe)
  64   - If you use qhull a lot, consider using the Cygwin Unix shell,
  65         Cygwin tools (http://sources.redhat.com/cygwin/)
  66   - Execute 'qconvex' for a synopsis and examples.
  67   - Execute 'rbox 10 | qconvex' to compute the convex hull of 10 random points.
  68   - Execute 'rbox 10 | qconvex i TO file' to write results to 'file'.
  69   - If an error occurs, Windows 95 sends the error to stdout instead of stderr
  70       - use 'TO xxx' to send normal output to xxx and error output to stdout
  71   - Browse the documentation: qhull\html\index.htm
  72
  73 Compiling for Unix
  74
  75   The gzip file, qhull.tgz, contains documentation and source files for
  76   qhull and rbox.
  77
  78   To unpack the gzip file
  79   - tar zxf qhull.tgz
  80   - cd qhull
  81
  82   Compiling with the Debian Make:[R. Laboissiere]
  83   - cd src
  84   - ./Make-config.sh
  85   - cd ..
  86   - configure
  87   - make
  88
  89   Compiling with Makefile (i.e., Makefile.txt)
  90   - cd src
  91   - in Makefile, check the CC, CCOPTS1, PRINTMAN, and PRINTC defines
  92       - the defaults are gcc and enscript
  93       - CCOPTS1 should include the ANSI flag.  It defines __STDC__
  94   - in user.h, check the definitions of qh_SECticks and qh_CPUclock.
  95       - use '#define qh_CLOCKtype 2' for timing runs longer than 1 hour
  96   - type: make
  97       - this builds: qhull qconvex qdelaunay qhalf qvoronoi rbox libqhull.a
  98   - type: make doc
  99       - this prints the man page
 100       - See also qhull/html/index.htm
 101   - if your compiler reports many errors, it is probably not a ANSI C compiler
 102       - you will need to set the -ansi switch or find another compiler
 103   - if your compiler warns about missing prototypes for fprintf() etc.
 104       - this is ok, your compiler should have these in stdio.h
 105   - if your compiler warns about missing prototypes for memset() etc.
 106       - include memory.h in qhull_a.h
 107   - if your compiler is gcc-2.95.1, you need to set flag -fno-strict-aliasing.
 108       - This flag is set by default for other versions [Karas, Krishnaswami]
 109   - if your compiler reports "global.c: storage size of 'qh_qh' isn't known"
 110       - delete the initializer "={0}" in global.c, stat.c and mem.c
 111   - if your compiler warns about "stat.c: improper initializer"
 112       - this is ok, the initializer is not used
 113   - if you have trouble building libqhull.a with 'ar'
 114       - try 'make -f Makefile.txt qhullx'
 115   - if the code compiles, the qhull test case will automatically execute
 116   - if an error occurs, there's an incompatibility between machines
 117       - For gcc-2.95.1, you need to set flag -fno-strict-aliasing.
 118             It is set by default for other versions of gcc [Karas, Krishnaswami]
 119       - If you can, try a different compiler
 120       - You can turn off the Qhull memory manager with qh_NOmem in mem.h
 121       - You can turn off compiler optimization (-O2 in Makefile)
 122       - If you find the source of the problem, please let us know
 123   - if you have Geomview (www.geomview.org)
 124        - try  'rbox 100 | qconvex G >a' and load 'a' into Geomview
 125        - run 'q_eg' for Geomview examples of Qhull output (see qh-eg.htm)
 126   - to install the programs and their man pages:
 127       - define MANDIR and BINDIR
 128       - type 'make install'
 129
 130 Compiling for Windows NT, 2000, XP with cygwin (www.cygwin.com)
 131
 132     - install cygwin with gcc, make, ar, and ln
 133     - cd qhull/src
 134     - make -f Makefile.txt
 135
 136 Compiling for Windows 95, 98, NT, 2000, XP
 137
 138   Qhull compiles as a console application in Visual C++ 5.0 at warning
 139   level 3.
 140
 141   Visual C++ quickstart for qhull.exe:
 142     - create a "Win32 console application" called "qhull"
 143         - add the following files:
 144             geom.c geom2.c global.c io.c mem.c merge.c poly.c poly2.c qhull.c
 145                 qset.c stat.c unix.c user.c
 146     - create a "Win32 console application" called "rbox"
 147         - add rbox.c
 148
 149   Visual C++ quickstart for qhull library, qconvex.exe, etc.
 150     - To simplify setting up lots of projects,
 151         - create a temporary "Win32 console application" called "source"
 152         - add all .c files from .../src/...
 153         - In Tools::Options::Tab
 154           Set tab size to 8 and indent size to 2
 155
 156     - create a "Win32 console application" called "rbox"
 157         - move rbox.c from "qhull source"
 158         - for Project:Settings..., Link
 159           you only need the default libraries
 160         - build the project
 161
 162     - create a "Win32 static library" called "library"
 163         - move these files from "qhull source"
 164             geom.c geom2.c global.c io.c mem.c merge.c poly.c poly2.c qhull.c
 165                 qset.c stat.c user.c
 166         - set the library file (use the same for debug and release)
 167         - build the project
 168
 169     - create a "Win32 console application" called "qhull"
 170         - move unix.c from "qhull source"
 171         - Set the library file in Project:Settings..., Link
 172         - Qhull does not use other libraries
 173
 174     - create a "Win32 console application" called "qconvex"
 175         - move qconvex.c from "qhull source"
 176         - Set the library file in Project:Settings..., Link
 177
 178     - do the same for qdelaun.c, qhalf, qvoronoi.c, user_eg.c, user_eg2.c
 179         - delete "qhull sources" since it is no longer needed
 180         - Set the library file in Project:Settings..., Link
 181         - use Project:Settings to make any changes
 182         - use batch build to rebuild everything
 183
 184   Qhull compiles with Borland C++ 5.0 bcc32.  A Makefile is included.
 185   Execute 'make -f MBorland'.  If you use the Borland IDE, set the ANSI
 186   option in Options:Project:Compiler:Source:Language-compliance.
 187
 188   Qhull compiles with Borland C++ 4.02 for Win32 and DOS Power Pack.
 189   Use 'make -f MBorland -D_DPMI'.  Qhull 1.0 compiles with Borland
 190   C++ 4.02.  For rbox 1.0, use "bcc32 -WX -w- -O2-e -erbox -lc rbox.c".
 191   Use the same options for Qhull 1.0. [D. Zwick]
 192
 193   Qhull compiles with Metrowerks C++ 1.7 with the ANSI option.
 194
 195   If you turn on full warnings, the compiler will report a number of
 196   unused variables, variables set but not used, and dead code.  These are
 197   intentional.  For example, variables may be initialized (unnecessarily)
 198   to prevent warnings about possible use of uninitialized variables.
 199
 200 Compiling for the Power Macintosh
 201
 202   Qhull compiles for the Power Macintosh with Metrowerk's C compiler.
 203   It uses the SIOUX interface to read point coordinates and return output.
 204   There is no graphical output.  For project files, see 'Compiling for
 205   Windows 95'.  Instead of using SIOUX, Qhull may be embedded within an
 206   application.
 207
 208   Version 1 is available for Macintosh computers by download of qhull.sit.hqx
 209   It reads point coordinates from a standard file and returns output
 210   to a standard file.  There is no graphical output.
 211
 212
 213 Compiling for other machines
 214
 215   Some users have reported problems with compiling Qhull under Irix 5.1.  It
 216   compiles under other versions of Irix.
 217
 218   If you have troubles with the memory manager, you can turn it off by
 219   defining qh_NOmem in mem.h.
 220
 221   You may compile Qhull with a C++ compiler.
 222
 223
 224 Distributed files
 225
 226   README.txt           // instructions for installing Qhull
 227   REGISTER.txt         // Qhull registration
 228   COPYING.txt          // copyright notice
 229   Announce.txt         // announcement
 230   Changes.txt          // change history for Qhull and rbox
 231   qh-faq.htm           // Frequently asked questions
 232   qh-home.htm          // Home page
 233   qh-get.htm           // Download page
 234   html/index.htm       // Manual
 235   Makefile.txt         // Makefile for Unix or cygwin 'make'
 236   MBorland             // Makefile for Borland C++/Win32
 237   Make-config.sh       // Create Debian configure and automake
 238
 239 src/
 240   rbox consists of:
 241      rbox.exe          // Win32 executable (.zip only)
 242      rbox.htm          // html manual
 243      rbox.man          // Unix man page
 244      rbox.txt
 245      rbox.c            // source program
 246
 247   qhull consists of:
 248      qhull.exe         // Win32 executables (.zip only)
 249      qconvex.exe
 250      qdelaunay.exe
 251      qhalf.exe
 252      qvoronoi.exe
 253      qhull-go.bat      // DOS window
 254      qconvex.htm       // html manuals
 255      qdelaun.htm
 256      qdelau_f.htm
 257      qhalf.htm
 258      qvoronoi.htm
 259      qvoron_f.htm
 260      qh-eg.htm
 261      qh-impre.htm
 262      qh-in.htm
 263      index.htm
 264      qh-opt*.htm
 265      qh-quick.htm
 266      qh--4d.gif,etc.   // images for manual
 267      qhull.man         // Unix man page
 268      qhull.txt
 269      q_eg              // shell script for Geomview examples
 270      q_egtest          // shell script for Geomview test examples
 271      q_test            // shell script to test qhull
 272
 273   top-level source files:
 274      src/index.htm     // index to source files
 275          qh-...htm         //   specific files
 276      user.h            // header file of user definable constants
 277      qhull.h           // header file for qhull
 278      unix.c            // Unix front end to qhull
 279      qhull.c           // Quickhull algorithm with partitioning
 280      user.c            // user re-definable functions
 281      user_eg.c         // example of incorporating qhull into a user program
 282      user_eg2.c        // more complex example
 283      qhull_interface.cpp // call Qhull from C++
 284
 285   other source files:
 286      qhull_a.h         // include file for *.c
 287      geom.c            // geometric routines
 288      geom2.c
 289      geom.h
 290      global.c          // global variables
 291      io.c              // input-output routines
 292      io.h
 293      mem.c             // memory routines, this is stand-alone code
 294      mem.h
 295      merge.c           // merging of non-convex facets
 296      merge.h
 297      poly.c            // polyhedron routines
 298      poly2.c
 299      poly.h
 300      qset.c            // set routines, this only depends on mem.c
 301      qset.h
 302      stat.c            // statistics
 303      stat.h
 304
 305 Authors:
 306
 307   C. Bradford Barber                    Hannu Huhdanpaa
 308   bradb@geom.umn.edu                    hannu@geom.umn.edu
 309
 310                     c/o The Geometry Center
 311                     University of Minnesota
 312                     400 Lind Hall
 313                     207 Church Street S.E.
 314                     Minneapolis, MN 55455
 315
 316   This software was developed under NSF grants NSF/DMS-8920161 and
 317   NSF-CCR-91-15793 750-7504 at the Geometry Center and Harvard
 318   University.  If you find Qhull useful, please let us know.