## GEOSTATS: Re: Boundary delimiter algorithm!

Expand Messages
• Thanks to everyone that reply my question. The main answers were the following; * Sites to check in the WWWW http://www.cs.cmu.edu/~quake/triangle.html
Message 1 of 1 , Feb 9, 1997
Thanks to everyone that reply my question.

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
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.
>