schorn.ch

The XYZ GeoBench for experimental geometric computation

Screen dump of the XYZ GeoBench while animating the computation of a Voronoi diagram

Index

1. Introduction
2. Algorithm animation
3. Test data generation
4. Interface to the outside world
5. Exchangeable arithmetic
6. Exchangeable abstract data types
7. Source code
8. System requirements
9. Download
10. Contact address
11. Appendix: Implemented algorithms

1. Introduction

The XYZ GeoBench (eXperimental geometrY Zurich) is a workbench for geometric computation on Macintosh computers. It provides an interactive user interface similar to a drawing program which can be used to create and manipulate geometric objects such as points, line segments, polygons, etc. Furthermore the user interface provides convenient access 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.

2. Algorithm animation

For applications in education it is important that all operations can be animated. For example one can execute an algorithm step by step in a class room demonstration or students can work by themselves exploring the inner workings of a geometric program. The figure above shows a screen dump while animating the computation of a Voronoi diagram. For a more comprehensive example of an animation take a look here.

3. Test data generation

One must provide geometric objects in order to exercise the built-in operations. This can be done by clicking with the mouse, by reading data from a file or by creating geometric objects using various test data generators. For example one can produce random points, line segments, circles, rectangles, polygons, convex polygons, (directed) graphs, etc.

4. Interface to the outside world

In order to exchange data with other application programs the GeoBench supports the following interface formats:

• The PICT format which is understood by many drawing programs (e.g. MacDraw) and facilitates exchange of geometric objects via Cut / Copy / Paste.
• A LISP like textual format.
• The CABRI-graph format for graphs.

5. Exchangeable arithmetic

The result of a geometric computation may depend on the arithmetic used by the algorithm. This is true in particular for degenerate or special cases. In order to experiment with these effects, the GeoBench provides exchangeable, parametric arithmetic. This means that the same computation can be carried out using different kinds of arithmetic such as integer, built-in floating point and floating point with user selectable basis and precision.

6. Exchangeable abstract data types

The efficiency of an algorithm often depends on the choice of data structures. The GeoBench allows the user in many cases to select the implementation of a data structure at run time, facilitating experiments which measure run time efficiency under the influence of different data structure implementations.

7. Source code

For advanced users the complete source code of the system is provided for educational and research purposes only. The system is written in Object Pascal and currently consists of about 100 modules with about 2.4 MBytes. Most of the modules contain geometric algorithms. One can use the XYZ Library for other applications or one can implement new geometric algorithms (e.g. as thesis projects, exercises, term or research projects, etc.). Implementation of a new algorithm is facilitated by a rich infrastructure which includes geometric primitives and algorithms, abstract data types, support for graphics and animation, file and interactive I/O, memory management, etc.

8. System requirements

GeoBench requires a Macintosh computer with system software later than 6.0.5. An OS X/Carbon version is also available which runs native on PPC and INTEL processors. If you want to use the source code you will either need an older version of Metrowerks CodeWarrior that still supports Object Pascal or you can use the GNU Pascal Compiler. In order to use the .sit files you need a utility to decompress StuffIt files. The sources and the manual is also available in zip-format. Note that the sources still contain some Macintosh dependencies particularly when it comes to graphics and user interaction.

9. Download

The distribution of the GeoBench software currently includes:

• The GeoBench application program program, version 7.0.3 for OS X only (884 kB, for INTEL processors, Mountain Lion compatible but Mavericks is not supported anymore) and the sources (558 kB)
• The author's thesis ("Robust algorithms in a program library for geometric computation") is available for download and viewing in the ETH e-collection.
• The GeoBench application program program, version 5.0.5 for PowerPC (584 kB) version
• The GeoBench application program program, version 6.0.3 for OS X or OS 9.x Carbon (460 kB)
• Source code for version 5.0.5 (724 kB, Object Pascal sources for MetroWerks CodeWarrior, ResEdit resource file, CodeWarrior project file)
• Source code for Carbon version 6.0.3 (677 kB, Object Pascal sources for MetroWerks CodeWarrior, ResEdit resource file, CodeWarrior project file)
• Source code for version 5.0.5 (608 kB, Object Pascal compressed with ZIP)
• Manual 5.0.1 (224 kB, comprehensive documentation, 100 page manual in Word 6 format with index)
• Manual 5.0.1 (212 kB, same as previous but compressed with ZIP)
• Demo data (40 kB, point sets, polygons, maps, etc.)
• Test data (436 kB)

Note that application and source code is distributed as is without any kind of warranty.

10. Contact address

Questions, suggestions, comments, bug reports, enquiries for commercial use, etc. should be addressed to

Dr. Peter Schorn

Culmannstrasse 77

CH-8006 Zürich

Switzerland

Email peter.schorn@acm.org

11. Appendix: Implemented algorithms

• Convex hull of a point set (Graham's scan, divide and conquer)
• Convex hull of a simple polyline (linear time method)
• Convex hull of a splinegon
• 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 [horizontal and vertical] line segments (sweep line)
• 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 objects (points, circles, line segments, 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, simplified sweep line)
• Euclidean minimum spanning tree (EMST)
• Traveling salesman heuristics (nearest neighbor, EMST, convex hull, tour optimizer)
• Exact solution to the traveling salesman problem
• 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, using a uniform grid)
• Delaunay-triangulation (from Voronoi-diagram, from arbitrary triangulation by edge-flipping, using a uniform grid)
• Smallest area disk enclosing a set of points (randomized incremental, also in d-dimensions)
• Test whether an arbitrary polygon is convex
• On line closest pair
• Calculation of a Henneberg 2-sequence for a graph (randomized)
• Clustering of points (EMST)
• Computation of Relative Neighborhood Graph
• Computation of Gabriel Graph
• Boolean operations on layered objects (2.5-d)
• Visualization of layered objects (2.5-d)