Up

The XYZ GeoBench for experimental geometric computation

Screen dump of a XYZ GeoBench session
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

GeoBench Logo
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:

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: 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