GEOSTATS: Re: Boundary delimiter algorithm!
- Thanks to everyone that reply my question.
The main answers were the following;
* Sites to check in the WWWW
anonymous ftp to: geom.umn.edu, look for qhull.tar.Z
"The Convex Hull Generator creates
the polygon which you would get if each
datapoint were a nail in a board and youstretched a rubber band around
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
Please bear in mind that this is just a suggestion, and I haven't put
this idea through a shred of mathematical testing :^)
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.