Loading ...
Sorry, an error occurred while loading the content.

GEOSTATS: Re: Boundary delimiter algorithm!

Expand Messages
  • Paloma Urbano Lopez de Meneses
    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 11:18 PM
    • 0 Attachment
      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
      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.
    Your message has been successfully submitted and would be delivered to recipients shortly.