Alpha Shapes Software Requirements Specification
By Duncan Gray

$Revision:$
$Date:$

INTRODUCTION

The alpha shape is a generalization of the convex hull of a point
set. For alpha = infinity, the alpha-shape is the convex hull of S. As
alpha decreases, the alpha-shape shrinks and develops cavities, as
soon as a sphere of radius sqrt( alpha) can be put inside. Finally,
for alpha = 0, the alpha-shape is the set S itself. The construction
of a boundary like this manually, by joining the dots is time
consuming, especially for large problems involving tens of thousands
of points.

OVERALL DESCRIPTION 

The s/w will mainly be used to determine a border around a set of
points.  This is time consuming manually and is needed to define the
boundary of a simulation.

DEFINITIONS

CONSTRAINTS

C1 - It will be written in python (or have a python interface). 
C2 - It will work as a stand-alone application and as a python module.

REQUIREMENTS
R1 - Input co-ordinate values for a list of points.

R2 - Output a boundary/polygon that all the input points are
within. [This could be a list of point indexes] 

R3 - Ability to find and apply the optimum alpha parameter.
 [What is optimum?  Maybe the smallest alpha parameter the encompass
 all points in the same polygon?]
R3.1 - Optionally a specified alpha parameter is applied.

R4 - Be able to handle large data sets ( eg 100,000 - 500,000 )


DEVELOPMENT

A recomended data structure are arrays in Numeric.
The C program 'triangle' could be an option for mesh generation.
A unit test harness will also be developed.  This should be based on
the pyvolution unit test harnessess.