# Selected Developed Software

The research software provided on this web site ("software") is provided by
NIST as a public service. You may use, copy and distribute copies of the
software in any medium, provided that you keep intact this entire notice.
You may improve, modify and create derivative works of the software or any
portion of the software, and you may copy and distribute such modifications
or works. Modified works should carry a notice stating that you changed the
software and should note the date and nature of any such change. Please
explicitly acknowledge the National Institute of Standards and Technology
as the source of the software.

The software is expressly provided "AS IS." NIST MAKES NO WARRANTY OF ANY
KIND, EXPRESS, IMPLIED, IN FACT OR ARISING BY OPERATION OF LAW, INCLUDING,
WITHOUT LIMITATION, THE IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR
A PARTICULAR PURPOSE, NON-INFRINGEMENT AND DATA ACCURACY. NIST NEITHER
REPRESENTS NOR WARRANTS THAT THE OPERATION OF THE SOFTWARE WILL BE
UNINTERRUPTED OR ERROR-FREE, OR THAT ANY DEFECTS WILL BE CORRECTED. NIST
DOES NOT WARRANT OR MAKE ANY REPRESENTATIONS REGARDING THE USE OF THE
SOFTWARE OR THE RESULTS THEREOF, INCLUDING BUT NOT LIMITED TO THE
CORRECTNESS, ACCURACY, RELIABILITY, OR USEFULNESS OF THE SOFTWARE.

You are solely responsible for determining the appropriateness of using and
distributing the software and you assume all risks associated with its use,
including but not limited to the risks and costs of program errors,
compliance with applicable laws, damage to or loss of data, programs or
equipment, and the unavailability or interruption of operation. This software
is not intended to be used in any situation where a failure could cause risk
of injury or damage to property. The software was developed by NIST employees.
NIST employee contributions are not subject to copyright protection within
the United States.

**2-D and 3-D Delaunay, Regular, Voronoi, Power constructs Sofware:**

*deltri.f*, double precision Fortran 77 program for
reading/computing a 2-dimensional Delaunay triangulation for
a set of points, and for accomplishing any of the following tasks
as desired: inserting an additional set of points and/or a set
of line segments into current (Constrained) Delaunay triangulation
and obtaining a (Constrained) Delaunay triangulation that contains
the inserted points and/or line segments; deleting a set of points
that are vertices in the current (Constrained) Delaunay triangulation
and obtaining a (Constrained) Delaunay triangulation that does not
contain the deleted points; computing circumcenters of triangles
(Voronoi vertices) in final (Constrained) Delaunay triangulation.
In addition, if Voronoi vertices are computed and Delaunay triangulation
is unconstrained (no inserted line segments), the corresponding
Voronoi diagram is well defined, and then program can be used
for inserting edges of a rectangle into Voronoi diagram (a rectangle
that contains in its interior set of points for which Voronoi
diagram is defined) so that parts of Voronoi cells outside rectangle
(in particular unbounded cells) are clipped by these edges.
Input coordinates of points can have as many as 14 significant
figures with as many as 9 significant figures to either the left
or the right of the decimal point. Exact arithmetic is used when
necessary.
If a prompt file does not exist the program will create
a file that can be used as such in order to avoid user intervention
in subsequent executions of the program.
[Source code].

*pltvor.f*, double precision Fortran 77 program for
producing data files and script file for plotting Voronoi diagram
of a set of points with matlab. It is assumed that an unconstrained
Delaunay triangulation for the set has already been computed using
program deltri above. It is also assumed that the Voronoi vertices of
the Voronoi diagram of the set were also computed with deltri. From
the output files of program deltri the program here produces data
files and script file vorplot.m that when executed with matlab creates
from the data files a plot of the Voronoi diagram. If as described for
program deltri above, the Voronoi diagram has been clipped by the
edges of a rectangle, files for plotting the clipped Voronoi diagram
will be produced by this program. If a prompt file does not exist the
program will create a file that can be used as such in order to avoid
user intervention in subsequent executions of the program.
[Source code].

*pltdel.f*, double precision Fortran 77 program for
producing data file and script file for plotting a constrained or
unconstrained Delaunay triangulation of a set of points with matlab.
It is assumed that a Delaunay triangulation for the set has already
been computed using program deltri above. From the output files of
program deltri the program here produces data file and script file
delplot.m that when executed with matlab creates from the data file
a plot of the Delaunay triangulation. If as described for program
deltri above, during the execution of deltri an unconstrained Delaunay
was computed and the associated Voronoi diagram was clipped by the
edges of a rectangle, the files produced by this program will be for
plotting the Delaunay triangulation minus some triangles that are
eliminated because of the clipping. Accordingly, the plotted
triangulation may not be convex. If a prompt file does not exist the
program will create a file that can be used as such in order to avoid
user intervention in subsequent executions of the program.
[Source code].

*arelen.f*, double precision Fortran 77 program for computing
areas of Voronoi cells in the Voronoi diagram of a set of points in
2-dimensional space, lengths of faces of these cells, and the
distances obtained by computing for each face the distance between the
two points in the set that define the face (inter-neighbor distances).
It is assumed that an unconstrained Delaunay triangulation for the set
has already been computed using program deltri above. It is also assumed
that the Voronoi vertices of the Voronoi diagram of the set were also
computed with deltri.
[Source code].

*dynvor.f*, double precision Fortran 77 program for computing
Delaunay triangulations and Voronoi diagrams of dynamic data, i. e., of a
set of moving points in 2-d space. Currently program is set up to handle
999 or fewer input files making up dynamic data. Each input data set
contains the same number of distinct data points (no duplicates)
in the plane. Each time an input data set is read the current Delaunay
triangulation and Voronoi diagram are updated on a local basis, i. e.,
taking into account only those points that have moved. If the percentage
of points that have moved is too high then the whole Delaunay
triangulation and Voronoi diagram are computed. Exact arithmetic is
used when necessary.
[Source code].

*pltdyn.f*, double precision Fortran 77 program for producing
data files and script file for plotting with matlab in the form of a
movie Voronoi diagrams of dynamic data, i. e., of a set of moving
points in 2-d space. It is assumed that another existing program,
program dynvor, has been executed thus producing the Delaunay
triangulations and Voronoi diagrams of the dynamic data and the
corresponding output files. From the output files of program dynvor
the program here produces data files and script file dynplot.m that
when executed with matlab creates from the data files a movie of the
plots of the Voronoi diagrams of the dynamic data in the order in which
program dynvor reads the input data files that define the dynamic data.
Note that during the execution of dynplot.m with matlab the return key
should be pressed each time the execution pauses.
[Source code].

*dynamic_input_data.zip*, 100 sample input dynamic data sets
for programs dynvor.f and pltdyn.f for testing purposes: pn001,
pn002, ..., pn100.
[Sample data].

*aggres.f*, double precision Fortran 77 program for computing
an estimate of the surface of an aggregate as a power crust from a
point cloud obtained from the surface of the aggregate. Besides a power
crust of the object, the program also produces the area of the power
crust and the volume of the solid it encloses. Here an aggregate is
defined as an object in 3-dimensional space that has no holes and
contains its center of mass in its interior. Output file with power crust
information will be formatted for the purpose of plotting the power crust
with matlab and a script for processing this file with matlab and
obtaining the plot of the power crust is included in the main routine of
the code. Actually the requirement in the definition of an aggregate about
the center of mass can be ignored if a point is known that lies in the
interior of the object at a reasonable distance from the surface.
Exact arithmetic is used when necessary.
[Source code].

*regtet.f*, double precision Fortran 77 program for computing
with incremental topological flipping a Regular tetrahedralization for
a set of points in 3-dimensional space. Input coordinates and weights
of points can have as many as 14 significant figures with as many as
9 significant figures to either the left or the right of the decimal
point. In the absence of weights the program computes a Delaunay
tetrahedralization. A Regular tetrahedralization is the dual of a Power
diagram. It is essentially a Delaunay tetrahedralization for a set of
points with weights. In this program artificial points are handled
lexicographically. Exact arithmetic is used when necessary. As a result
this program is both fast and robust. If a prompt file does not exist
the program will create a file that can be used as such in order to
avoid user intervention in subsequent executions of the program.
[Source code].

*ragtat.f*,
same as program regtet.f above but with the option of either computing
from scratch a Regular/Delaunay tetrahedralization for a set of points
in 3-d space or inserting a new set of points in 3-d space into an
existing Regular/Delaunay tetrahedralization. If a prompt file does not
exist the program will create a file that can be used as such in order
to avoid user intervention in subsequent executions of the program.
[Source code].

*pwrvtx.f*, double precision Fortran 77 program for computing
the Power/Voronoi vertices and unbounded edges for a set of points in
3-dimensional space from a Regular/Delaunay tetrahedralization for the
set. It is assumed that a Regular/Delaunay tetrahedralization for the set
has already been computed using program regtet/ragtat above with logical
variable artfcl set to .false.. The output tetrahedron list from
regtet/ragtat is then used as input for this program. As in the case of
regtet/ragtat, exact arithmetic is used when necessary. The lengths of
input coordinates and weights follow the same rules as when using
regtet/ragtat.
[Source code].

*volare.f*, double precision Fortran 77 program for computing
volumes of Power/Voronoi cells in the Power/Voronoi diagram of a set of
points in 3-dimensional space, areas of facets of these cells, and the
distances obtained by computing for each facet the distance between the
two points in the set that define the facet (inter-neighbor distances).
It is assumed that a Regular/Delaunay tetrahedralization for the set has
already been computed using program regtet/ragtat above with logical
variable artfcl set to .false.. It is also assumed that the Power/Voronoi
vertices of the Power/Voronoi diagram of the set have already been
computed using program pwrvtx above with the output tetrahedron list
from regtet/ragtat as input. The output Power/Voronoi vertex and
tetrahedron lists from pwrvtx are then used as input for this program.
[Source code].

*dtread.f*, double precision Fortran 77 program for exhibiting
how output data produced by program volare above must be read and used.
[Source code].

*pwrtet.f*, double precision Fortran 77 program for doing 3D
nearest point searches. It identifies Power cells in the Power
diagram of a 3-dimensional set of points S that contain points in a
3-dimensional set R. In other words, for each point in R this program
finds a point in S that is as Power close to the point in R as any
other point in S. If no weights are present then it identifies Voronoi
cells in the Voronoi diagram of S that contain points in R. In
addition, this program determines where with respect to the convex hull
of S the points in R are located. It is assumed that a Regular/Delaunay
tetrahedralization for S has already been computed using program regtet
above with logical variable artfcl set to .true.. The output tetrahedron
list from regtet is then used as input for this program. As in the case
of regtet, exact arithmetic is used when necessary. The lengths of input
coordinates and weights follow the same rules as when using regtet.
The program is based on an algorithm for constructing Regular
tetrahedralizations with incremental topological flipping.
However no actual flippings take place. Given a point in R,
if weights are present a weight is assigned to the point so that
the Power cell of the point in the Power diagram of S together
with the point contains the point. The program then goes through
the motions of inserting the point into the Regular/Delaunay
tetrahedralization for S without actually doing it. This way a
subset of points in S is identified that contains what would be
the Voronoi/Power neighbors of the point in the Voronoi/Power
diagram of S together with the point. The desired point in S
is then a point in this subset closest to the the point in R
in the Power sense. If weights are present care is taken in
choosing the weight assigned to the point in R so that it is as
small as possible.
[Source code].

*tritet.f*, double precision Fortran 77 program for
inserting a set of 2-dimensional triangles into a tetrahedralization.
The resulting tetrahedralization is then constrained by the triangles.
Topological flipping is used whenever possible in order to obtain the
desired tetrahedralization. Steiner points are used as a last resort.
Since the insertion of the 2-d triangles causes the resulting
tetrahedralization to be partitioned into regions having pair-wise
disjoint interiors, on output tetrahedra are marked according to
the region they belong to. Regions are numbered either arbitrarily
by program or as requested by user. If requested by user the volume of
each region is computed. In this program exact arithmetic is used when
necessary.
[Source code].

*pntloc.f*, double precision Fortran 77 program for
locating points in a tetrahedralization by moving in a straight
line to each point from a point whose location is known.
In this program exact arithmetic is used when necessary.
[Source code].

**Other Sofware:**

*km_anyd.f*, double precision Fortran 77 program for
computing k-means clustering of a set of points in any dimension.
If a rectangle in the form of a 2-d rectangular grid can be
associated with the input points, the option exists for creating
a txt file of k-means cluster indices on the rectangular grid
that can then be used as input to create an image with imagej of
the rectangle partitioned into clusters.
[Source code].

*em_anyd.f*, double precision Fortran 77 program for
computing k-Gaussian mixture clustering of a set of points in
any dimension with EM (Expectation Maximization) algorithm.
If a rectangle in the form of a 2-d rectangular grid can be
associated with the input points, the option exists for creating
a txt file of k-Gaussian mixture cluster indices on the rectangular
grid that can then be used as input to create an image with imagej
of the rectangle partitioned into clusters. If the program does not
produce a satisfactory k-Gaussian mixture clustering, it is
recommended that a k-means clustering be computed instead with
program km_anyd.f above.
[Source code].

*spline.f*, single precision Fortran 77 program for
computing cubic spline interpolation under the "not a knot"
condition. Results from this program appear to be exactly the
same as those obtained with the matlab spline function. Program
is based on original code in Slatec package obtained from Guide
to Available Mathematical Software (GAMS) web site at the
National Institute of Standards and Technology.
[Source code].