This directory contains C routines for computing a Delaunay tessellation of a finite set of points in general position. Input consists of the dimension of the space, the number of points, and floating point coordinates of the points. The code is written for dimensions greater than one. Output consists of a list of vertices and a list of adjacent simplices for each simplex in the tessellation. Some computations are done in floating point arithmetic. Degenerate point sets that produce non-simplicial convex hulls or non-unique tessellations may generate erroneous results or cause the program to fail. The code has been tested extensively for dimensions two and three with points with pseudo-randomly generated coordinates in a unit [hyper]cube. The algorithm is a gift-wrapping technique described in the paper Facet-Based Tetrahedrizations by Carol Hazlewood, a post-script version of which is in file fbt.ps. The routines are user-callable. A single call to the top-level routine tess produces a Delaunay tessellation. The parameter list is described below, and a sample driver is provided. The files in this directory are also described below. The code is free, and comes with no implicit or explicit guarantees. You may use this program if you acknowledge the source. Copyright (c) 1994 Carol Hazlewood All rights reserved. To install, untar in a suitable directory and enter: make all Please send comments to the author: Carol Hazlewood ch04@academia.swt.edu Department of Computer Science Southwest Texas State University San Marcos TX 78666 USA phone: 512-245-3409 fax: 512-245-8750 This directory contains the following files: README This file contains installation instructions. This is the file you are reading. Makefile This is a sample makefile for building tess with the sample driver. tess.c This file contains the routines that compute a Delaunay tessellation. blas.c This file contains an f2c translation of the Fortran blas (basic linear algebra subprograms). tess.h This header file is included in tess.c, blas.c and driver.c. f2c.h This header file is included in tess.h driver.c This file contains a sample driver for tess. It generates twenty 3D points with random coordinates and prints the points and the tetrahedrization. in.dat This file contains a sample input problem. out.dat This file contains the output corresponding to the data in input.dat. fbt.ps This is a postscript file of a paper describing the algorithm used in the software. The calling sequence and parameters are described below: #include "tess.h" int tess_(mrowp, mp, np, p, mrows, ncols, ms, ns, nsim, nadj, work, llfact, iwork, ierr) integer *mrowp, *mp, *np; real *p; integer *mrows, *ncols, *ms, *ns, *nsim, *nadj; real *work; integer *llfact, *iwork, *ierr; /* ***begin prologue tess */ /* ***date written 950115 (yymmdd) */ /* ***keywords Delaunay tetrahedrization tessellation */ /* ***author Hazlewood, Carol */ /* ch04@academia.swt.edu */ /* Department of Computer Science */ /* Southwest Texas State University */ /* San Marcos, TX 78666 */ /* */ /* ***purpose this routine computes a Delaunay */ /* tetrahedrization of a set of points */ /* in general position. */ /* ***description */ /* argument description *** */ /* on input */ /* *mrowp integer */ /* the row dimension of the array p as declared */ /* by the calling routine. mrowp .ge. mp */ /* *mp integer */ /* the dimension of the space that contains the */ /* points of p. mrowp .ge mp */ /* *np integer */ /* the number of points in p */ /* p real(mrowp*np) */ /* a one dimensional real array that contains the */ /* coordinates of the points to be tessellated. */ /* Conceptually the array p is a two dimensional */ /* array with mrowp rows and np columns, where */ /* each column of p contains the coordinates */ /* of one point. */ /* *mrows integer */ /* the row dimension of arrays nsim and nadj as */ /* declared by the calling routine. mrows .ge. ms */ /* *ncols integer */ /* the column dimension of arrays nsim and nadj as */ /* declared by the calling routine. this is the */ /* maximum number of simplices that can be */ /* represented. the expected number of simplices */ /* in a three dimensional tessellation of np */ /* points is 7*np (see stoyan, kendall, and mecke, */ /* stochastic geometry) */ /* iwork integer(*) */ /* integer array to be used as workspace. */ /* It should be declared by the calling routine */ /* to be of size 140*ncols. */ /* work real(*) */ /* real array to be used as workspace. It should */ /* be declared by the calling routine to be of */ /* size at least 5*mrowp + mrowp*mrowp. */ /* on return */ /* *ms integer */ /* the number of vertices in a simplex. */ /* normally ms = mp + 1 */ /* *ns integer */ /* the number of simplices in the tessellation */ /* nsim integer(mrows*ncols) /* a one-dimensional real array that contains */ /* a representation of the vertices of the */ /* simplices in the tessellation. Conceptually */ /* it is a two dimensional integer array of mrows */ /* rows and ncols columns. Each column of nsim */ /* represents one simplex of the tessellation and */ /* contains the indices in p of the vertices of */ /* the simplex */ /* nadj integer(mrows,ncols) */ /* a one-dimensional real array that contains */ /* a representation of the adjacent simplices */ /* in the tessellation. Conceptually it is a */ /* two dimensional integer array of mrows rows and */ /* ncols columns. Each column of nadj contains */ /* information about the neighbors of one simplex. */ /* nadj(i,j) is the index in nsim of the simplex */ /* that is adjacent to simplex j across the facet */ /* that does into contain vertex i. */ /* *ierr integer */ /* an error flag. if ierr = 0, the tessellation */ /* is complete. if ierr .ne. 0, an error has */ /* occurred */ /* mrowp,mp,p,mrows,and ncols are unchanged. */ /* work and iwork may be discarded. */ /* ***references */ /* ***routines called init,nxtsim */ /* */ /* The code is free, and comes with no implicit or explicit */ /* guarantees. */ /* You may use this program if you acknowledge the source. */ /* Copyright (c) 1994 Carol Hazlewood */ /* All rights reserved. */ /* */ /* ***end prologue tess */