The main answers were the following;

* Sites to check in the WWWW

http://www.cs.cmu.edu/~quake/triangle.html

http://netlib.bell-labs.com/netlib/voronoi/hull.html

http://xarch.tu-graz.ac.at/~rurban/software/hull.html

http://flamingo.stanford.edu/~suresh/theory/software/qhull.html

anonymous ftp to: geom.umn.edu, look for qhull.tar.Z

http://www.geom.umn.edu/software/cglist/lowdvod.html

"The Convex Hull Generator creates

http://www.iinet.com.au/~watson

and

http://www.sfiltd.com/products.htm

the polygon which you would get if each

datapoint were a nail in a board and youstretched a rubber band around

the

outside of all of them. "

This is a MapInfo-based solution.

* Main idea was triangulation, alternatives;

-Rupert Brooks suggested,

An algorithm which could do this is to pick a point known to be on the

boundary (a point on the minimum bounding rectangle). Choose a starting

vector which is known to point outside the dataset, and rotate the

vector clockwise until it intersects a point in the dataset. That point

is your next point, and that vector is your next vector. Eventually you

should circumnavigate the pointset.

Unfortunately, I think this algorithm would be less efficient than

simply triangulating the whole dataset, unless you had some way of

limiting the number of points that you had to calculate angles to. This

may or may not be possible, depending on your data structure. I think

most spatial indices would allow this, if your dataset is already

indexed.

Please bear in mind that this is just a suggestion, and I haven't put

this idea through a shred of mathematical testing :^)

Good Luck

Rupert Brooks

Geomatician, Canada Centre for Remote Sensing

Paloma Urbano Lopez de Meneses wrote:>

--

> Hello to everyone!

>

> I am trying to delimit a boundary out of a disperse set of points

> considering only the most external ones.

> The example should be something like the following,

>

> + +

> +

> + +

> +

> + +

>

> This are the disperse points

>

> The algorithm will delimited the outside boundary.

>

> +-----+

> / + \

> / + +

> + |

> \__ +____+

>

> At the moment we have been triangulating the points and obtaining the

> outline, however we are interested in an algorithm which would

> recognize the most external points of the area and use them to

> create a boundary polygon.

>

> Any help on this, useful web pages or literature would be appreciated.

>

> Thank you in advance,

>

> Paloma Urbano

--

*To post a message to the list, send it to ai-geostats@....

*As a general service to list users, please remember to post a summary

of any useful responses to your questions.