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 software 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 pairs] 

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. 

ISSUES

What sort of repository? Subversion or CVS?  Hopefully subversion is ok.