README - 9/91 PJF This directory contains sources for 2DLab, an interactive tool for visualizing some common geometric algorithms. The source code for Voronoi diagrams and Delaunay tesselations was writen by Seth Teller (of SGI?) and available on many archive sites. Ignore the warning messages that appear during compilation. ------------- Info from Help window --------------------------- 2DLab animates a few algorithms from computational geometry. It was originally released in early 1990, back when I was a graduate student at Michigan State University. In the process of updating the program for 2.0, things changed substantially, and many features were added. I hope you like the program. Running the program Two windows will appear when 2DLab is fired up. The Geometry Window contains the data and the results of any algorithms run on the data. The 2DLab Control window allows you to configure the data set, the algorithm, and the drawing that takes place. When the program is invoked, the Geometry Window will contain ten points, and the selected algorithm (Prim's MST algorithm by default) will be applied to these points. New points can be created by clicking in the window. There is a `margin' around the border of the window within which points will not be displayed, so If you click the mouse button and no point appears, you're probably too close to the edge (this margin was put in to make the Voronoi tesselation have a nice border. A new set of random points (uniformly distributed within the window's usable region) can be generated by entering the desired number of points in the editable text field and pressing the Generate button. The highlighted button in the RadioButton array in the Control Window identifies the particular algorithm to be `animated.' The Anim/Disp button will run the appropriate animation when pressed. The Disp button will simply display the resulting data structure without animating. It only works when the data structure has already been previously computed (i.e. ya gotta Anim before you can Disp). The Auto-Go checkbox specifies the program's behavior when new points are created with the mouse. If the box is checked, the selected algorithm is run immediately when a new point is added. The three color wells allow you to pick background, foreground, and highlighting colors. When the display is drawn, points and line segments appear in the foreground color. During animation, transient drawing is done using the highlight color. By default, these colors are white, black, and 67% gray, respectively. You can set them to anything you want using the standard color well tricks. The line width slider controls how thickly everything is drawn (both points and lines). The `Status' item displays informative (?) messages about the progress of the algorithm currently being animated, the drawing taking place, etc. The Document menu allows you to save the current data set in a `generic' form, load a similarly-formatted file in for animation, and save the generated imagery as TIFF or EPS. The file format for the data is simple. The first number is the number of ordered pairs (%d), and the remaining numbers are the pairs (%f %f). The error checking for I/O is pathetic, so please feed 2DLab well-behaved data files. The Copy item of the Edit menu may be selected. It sticks the contents of the Geometry window in the pasteboard. Algorithms In the following brief descriptions, N is the number of 2D points, and the O-notation refers to time complexity rather than space complexity. When the algorithms are invoked, those with quick eyes will notice some graphical razzle-dazzle as the data structure is constructed. After the algorithm has completed, the `resulting' data structure will remain in the window. - Prim's O(N^2) Minimal Spanning Tree (MST) algorithm. - Kruskal's O(E log E) MST algorithm. WARNING: the implementation in this program is NOT optimal (it's actually O(N^2)). Anybody who wants to hack together the priority queue stuff to implement the optimal algorithm is free to do so (lazy, that's me). - Jarvis' O(N log N) convex hull construction algorithm. - Graham's O(N log N) convex hull construction algorithm. - Somebody's O(N log N) Voronoi diagram algorithm. - Somebody's O(N log N) Delaunay triangulation algorithm. (code for these last two algorithms was written by Seth Teller, who apparently used Fortune's netlib code as a basis). - my own Gabriel Graph construction algorithm (it uses the Delaunay triangulation as a starting point). - my own Relative Neighborhood Graph construction algorithm (again, using the Delaunay triangulation as a starting point). Those interested in the details of the algorithms should refer to Preparata and Shamos' book on computational geometry. Sedgewick's book also has covers geometric algorithms. The GG and RNG haven't been used much, and are a little harder to find in the literature. Consult Toussaint, `The relative neighborhood graph of a finite point set', Pattern Recognition 12, 261-268 for info about the RNG. The Gabriel graph was used in Matula and Sokal, `Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane', Geographical Analysis 12, 205-222. However, I don't have either of those papers in my posession. This software was based on the discussion in Tuceryan and Chorzempa, `Relative Sensitivity of a family of closest-point graphs in computer vision applications', Pattern Recognition 24, 361-374. About the author; feedback This program was written by: Patrick Flynn Assistant Professor School of Electrical Engineering and Computer Science Washingon State University Pullman, WA 99164-2752 (flynn@eecs.wsu.edu) If you find bugs, let me know. If you add functionality, let me know. If you like/hate it and just want to tell me, let me know. Date: 9/91
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.
