Version 0.0-9 (??? 2 June 2009) Added a new function tile.centroids() --- which does the obvious. Motivated by an inquiry from Leandro Moreira. Version 0.0-8 (4 April 2009) Removed the labels from the x and y vectors in the tile descriptions produced by tile.list. These labels (which were the row numbers in the dirsgs data frame returned by deldir()) served no useful purpose and were potentially confusing. ***************************** Versions 0.0-2 through 0.0-7 were not tracked here. :-( Simply forgot about doing this. I thouroughly *intend* [ :-) ] to get the archives from CRAN and try to document the changes. Recent ones involved fixing bugs in and adding features to the tile.list() and plot.tile.list() functions. ***************************** Version 0.0-1 (21 February 2002) This version is simply an adaptation of the Splus version of the package to R. ***************************** Version date: 14 February 2002. This version supercedes the version dated 24 April 1999. ***************************** The changes from the version dated 24 April 1999 to the version dated 14 February 2002 were: A bug in the procedure for eliminating duplicated points was fixed. Thanks go to Dr. Berwin Turlach of the Department of Maths and Stats at the University of Western Australia, for spotting this bug. ***************************** The changes from the version dated 26 October 1998 to the version dated 24 April 1999 were: (1) The function mipd(), stored in mipd.sf, and the corresponding Fortran subroutine mipd, stored in mipd.r, have been replaced by mnnd() in mnnd.sf and mnnd in mnnd.r. The function mipd calculated the mean interpoint distance, to be used in constructing dummy point structures of a certain type. After some reflection it became apparent that the mean interpoint distance was much too large for the intended purpose, and that a more appropriate value was the ``mean nearest neighbour distance'' which is calculated by the new function. This new value is now used in constructing dummy point structures. Note that the operative result is that the resulting dummy point structures contain many more points than before. The old value caused large numbers of the dummy points to fall outside the data window and therefore to be clipped. ***************************** The changes from the version dated 6 December 1996 to the version dated 26 October 1998 were: (1) A ratfor/Fortran routine named ``inside'' has been renamed ``dldins'' to avoid conflict with a name built in to some versions of Splus. (2) Some minor corrections have been made to dangerous infelicities in a piece of the ratfor/Fortran code. (3) The dynamic loading procedure has been changed to use dyn.load.shared so that the package is easily usable on IRIX systems as well as under SunOS/Solaris. (4) The package has been adjusted slightly so that it can easily be installed as a section of a library. In particular, the dynamic loading is now done by the .First.lib() function rather than from within deldir() itself; reference to an environment variable DYN_LOAD_LIB is no longer needed. ***************************** This package computes and plots the Dirichlet (Voronoi) tesselation and the Delaunay triangulation of a set of of data points and possibly a superimposed ``grid'' of dummy points. The tesselation is constructed with respect to the whole plane by suspending it from ideal points at infinity. ORIGINALLY PROGRAMMED BY: Rolf Turner in 1987/88, while with the Division of Mathematics and Statistics, CSIRO, Sydney, Australia. Re-programmed by Rolf Turner to adapt the implementation from a stand-alone Fortran program to an S function, while visiting the University of Western Australia, May 1995. Further revised December 1996, October 1998, April 1999, and February 2002. Adapted to an R package 21 February 2002. Current address of the author: Department of Mathematics and Statistics, University of New Brunswick, P.O. Box 4400, Fredericton, New Brunswick, Canada E3B 5A3 Email: rolf@math.unb.ca The author gratefully acknowledges the contributions, assistance, and guidance of Mark Berman, of D.M.S., CSIRO, in collaboration with whom this project was originally undertaken. The author also acknowledges much useful advice from Adrian Baddeley, formerly of D.M.S. CSIRO (now Professor of Statistics at the University of Western Australia). Daryl Tingley of the Department of Mathematics and Statistics, University of New Brunswick provided some helpful insight. Special thanks are extended to Alan Johnson, of the Alaska Fisheries Science Centre, who supplied two data sets which were extremely valuable in tracking down some errors in the code. Don MacQueen, of Lawrence Livermore National Lab, wrote an Splus driver function for the old stand-alone version of this software. That driver, which was available on Statlib, is now deprecated in favour of this current package. Don also collaborated in the preparation of this current package. Bill Dunlap of MathSoft Inc. tracked down a bug which was making the deldir() function crash on some systems, and pointed out some other improvements to be made. Berwin Turlach of the Department of Maths and Stats at the University of Western Australia pointed out a bug in the procedure for eliminating duplicated points. ***************************** The man directory, contains, in addition to the R documentation files deldir.Rd and plot.deldir.Rd: (a) This READ_ME file. (b) A file err.list, containing a list of meanings of possible error numbers which could be returned. NONE of these errors should ever actually happen except for errors 4, 14, and 15. These relate to insufficient dimensioning, and if they occur, the driver increases the dimensions and tries again (informing you of this fact). (c) A file ex.out containing a printout of the object returned by running the example given in the help file for deldir. The src directory contains many, many *.f (Fortran) files, which get compiled and dynamically loaded. The Fortran code is ponderous --- it was automatically generated from Ratfor code, which was pretty ponderous to start with. It is quite possibly very kludgy aw well --- i.e. a good programmer could make it ***much*** more efficient I'm sure. It contains all sorts of checking for anomalous situations which probably can/will never occur. These checks basically reflect my pessimism and fervent belief in Murphy's Law. The program was also designed with a particular application in mind, in which we wished to superimpose a grid of dummy points onto the actual data points which we were triangulating. This fact adds slightly to the complication of the code. ***************************** Here follows a brief description of the package: (1) The function deldir computes the Delaunay Triangulation (and hence the Dirichlet Tesselation) of a planar point set according to the second (iterative) algorithm of Lee and Schacter, International Journal of Computer and Information Sciences, Vol. 9, No. 3, 1980, pages 219 to 242. The tesselation/triangulation is made to be **** with respect to the whole plane **** by `suspending' it from `ideal' points (-Inf,-Inf), (Inf,-Inf) (Inf,Inf), and (-Inf,Inf). (2) The tesselation/triangulation is also enclosed in a finite rectangle with corners (xmin,ymax) * ------------------------ * (xmax,ymax) | | | | | | | | | | (xmin,ymin) * ------------------------ * (xmax,ymin) The boundaries of this rectangle truncate some Dirichlet tiles, in particular any infinite ones. This rectangle is referred to elsewhere as `the' rectangular window. === (2) The function plot.deldir is a method for plot. I.e. it may be invoked simply by typing ``plot(x)'' provided that ``x'' is an object of class ``deldir'' (as produced by the function deldir). The plot (by default) consists of the edges of the Delaunay triangles (solid lines) and the edges of the Dirichlet tiles (dotted lines). By default the real data points are indicated by circles, and the dummy points are indicated by triangles.