🚀 go-pugleaf

Archive-name: auto/sci.math/XYZ-GeoBench-V4-4-0-available-via-anonymous-ftp

The XYZ GeoBench software for geometric computation has been upgraded to
version 4.4.0. A summary of changes is at the end of this article. 

The XYZ GeoBench (eXperimental geometrY Zurich) is a workbench for geometric
computation for Macintosh computers (requires the mathematical coprocessor,
2MB of memory, system software 6.0.5 or higher, large screen preferable).
It provides an interactive front-end with algorithm animation to the
XYZ Program Library that contains many standard algorithms for 2-d problems,
several for restricted 3-d problems, and one for d-dimensional computational
geometry. The 2-d algorithms currently in the library include:

- Convex hull of a point set (Graham's scan, divide and conquer)
- Convex hull of a simple polyline (linear time algorithm)
- Diameter, distance and intersection of convex polygons
- Tangents common to two convex polygons
- Boolean operations (union, intersection, difference) on polygons
- Contour of a set of rectangles
- Winding number
- Point(s) in polygon test (sweep line)
- Intersection of line segments (sweep line for the first intersection and for
  reporting all intersections, sweep line for the special case of horizontal
  and vertical line segments)
- Closest pair of points (sweep line [with heuristic], projection method,
  divide and conquer, probabilistic)
- Closest pair of line segments (sweep line)
- Closest pair of convex polygons (sweep line)
- All nearest neighbors (sweep line, simplified sweep line, extraction from
  Voronoi diagram, box shrinking method, projection method)
- All nearest neighbors in a sector (sweep line)
- Voronoi diagram (sweep line)
- Euclidean minimum spanning tree (EMST)
- Traveling salesman heuristics (nearest neighbor, EMST, convex hull,
  tour optimizer)
- 2-d tree operations (insert, range query, show partition)
- Quad-tree operations (creation, boolean operations)
- Lower envelope of a set of line segments
- Triangulation of a (monotone) polygon [with holes] (trapezoidal
  decomposition, sweep line)
- Triangulation of a set of points (randomized incremental)
- Delaunay Triangulation (from Voronoi-diagram, from arbitrary triangulation
  by edge-flipping)
- Smallest area disk enclosing a set of points (randomized incremental,
  also in d-dimensions)


The execution of all algorithms can be animated and experimentation is
facilitated by

- test data generators (random and degenerate configurations)
- exchangeable, parametric arithmetic
- exchangeable abstract data types
- interfaces to the outside world: cut and paste and a textual format


Availability: Object code and documentation via anonymous ftp from
neptune.inf.ethz.ch (129.132.101.33) in directory XYZ:

XYZDemoData.sea.Hqx         55814 (Demo data)
XYZGeoBench.sea.Hqx        365314 (Program, version 4.4.0, public domain)
XYZGeoBenchNoFPU.sea.Hqx   376315 (Program, doesn't need coprocessor, slow)
XYZImplementation.sea.Hqx  272398 (Describes implementation aspects,MacWrite II)
XYZManualWord4.sea.Hqx     187710 (GeoBench manual 4.4.0, Word 4.0 format)
XYZOverview.sea.Hqx        269830 (Overview of the XYZ project, MacWrite II)
XYZProject.sea.Hqx         266404 (Describes the XYZ project, MacWrite II)
XYZTestData.sea.Hqx        469717 (Test data)
readme                       4078 (This file)


Decoding: Transfer the file using ftp, decode it with BinHex and
          double click the Self Extracting Archive (.sea).


Changes and improvements made in version 4.4.0:

* manual was updated to version 4.4.0

* much improved and extended algorithms for triangulations with new operations

* improved interactive manipulation of 3-d views

* more user selectable preferences

* more interactive operations (triangulation, distance of convex polygons,
  winding number)

* some minor bug fixes


The system is written in Object Pascal (approximately 1.8 MByte source,
THINK Pascal V4.0.1). Source code is available for SFr. 1000 which grants
all rights.


For enquiries contact:
           Peter Schorn
           Informatik, ETH
           CH-8092 Zurich
           schorn@inf.ethz.ch