This is the README for Voronoi.N.bs.tar.gz [Download] [Browse] [Up]
This directory contains the source and binaries for the VoronoiView BackSpace module. When invoked, VoronoiView scatters a random number of dots (`sites') on the screen, builds the Voronoi tessellation of that point set, and displays the points and Voronoi polygons in vibrant color (unless your screen is monochrome). After remaining idle for some time period, it then clears the display and repeats the process with a new batch of sites. On my NextDimension, VoronoiView consumes very little CPU time when running, which gives it some advantages over some other BackSpace modules that have floated across the Net recently. It also (hopefully) should not cause burn-in. How to install VoronoiView: --------------------------- 1. Set INSTALLDIR in the Makefile. I always put my Views in the app wrapper. 2. Change the parameters in VoronoiViewPart.m if desired (see below) 3. make install Three user-settable parameters at the top of VoronoiViewPart.m -------------------------------------------------------------- The width (in pixels) of the polygon edges and site dots is WIDTH. Its default value is 2.0. The maximum number of sites is BS_MAXSITES (default 100). ******* DANGER ***************************************************** * The voronoi code (see below) uses a parameter called MAXSITES * * (#defined in voronoi,h, default value 4096). BS_MAXSITES SHOULD * * BE NO LARGER THAN MAXSITES. Why you would want more than 4096 * * sites is beyond me. 256 is plenty. * ******* REGNAD ***************************************************** The number of idle seconds between generations is IDLESECONDS (default 30). What's atan2.o doing in there? ------------------------------ Well, I had to extract atan2.o from the math library in order to get VoronoiView to work. atan2() is used by the Voronoi code in VoronoiViewPart.m. It is apparently NOT linked into BackSpace as compiled under the defaults. So we need to supply it to BackSpace in our view class .o file. Voronoi code ------------ The actual code for the 2D voronoi tessellation was written by Seth Teller (of SGI, I think); I ripped it out of 2DLab (available at your fave archive site) and wrote the View glue to make it run within BackSpace. As originally distributed (it is available from many archive sites), the code was in a bunch of .c and .h files. To make this module simple, I took all the C code and mashed it into VoronoiViewPart.m . Yeah, I know that's ugly. misc.h, voronoi.h, headers.s, and vector.h are needed by that code, so don't delete them. Possible additions/changes that I'm too lazy to implement --------------------------------------------------------- 1. Delaunay triangulation (or Gabriel graph, or Relative neighborhood graph) instead of Voronoi diagram. This is probably about 6 lines of code. I suppose you could do the MST as well, or a convex hull. 2. Detect what kind of screen we're running under. (Feh. Why bother? The window is unbuffered). 3. Fill in the polygons instead of outlining them. Or outline the sites instead of filling them. Be my guest. Beware of burn-in! 4. Replace the 2% shrinking-polygon hack with something a little more sophisticated. The whole idea of shrining the polygons was to have edges appear in multiple colors. Unfortunately, sparse site distributions produce disconnected Voronoi polygons. 5. Incorporate some pre-specified, structured site distributions (e.g. samples from a circle, or an ellipse, etc.) instead of the current random (uniform) 2D distribution. Or perhaps samples from a bivariate Gaussian (or some other) distribution. Such ideas should be easy to implement. Author ------ Patrick J. Flynn School of Electrical Engineering and Computer Science Washington State University Pullman, WA 99164-2752 flynn@eecs.wsu.edu
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.