[GRASS5] Q. How do you find the islands for a given area?

[Michel Wurtz]

Rich Shepard wrote:
> 
> On Sun, 25 Feb 2001, Eric G. Miller wrote:
> 
> > There's probably alot I can do to speed it up, by being more efficient
> > about memory dupes.  The biggest killer is the search for the closest tie
> > point between the outer polygon and it's inner islands.  I'm doing a real
> > lame nested looping thing through two polygons to find the closest points.
> > Maybe you'all have a better method to identify appropriate points to tie
> > to two polygons together at?
> 
> Eric,
> 
>   I'm not sure about this, but throwing out the idea. Pick a reference point
> on the outer polygon. Test each inner polygon node by examining the length of
> a vector between the reference node (on the outer polygon) and each node of
> the inner polygon. I've no idea how to calculate the speed, but (in my
> naivety) it might be O(n) because you calculate the vector once per pair of
> points.

"Some" years ago, I've written a polygon filling algorythm. I was also
faced to the problem of included polygons. I used a sorted list of vector.
The sort was done first by X ascendent, then by Y ascendent.  For each
vector, i used the lower X end. You do not even sort them : with a double
linked list, you can easely fit them in place while building the list.
For any fixed X value, you can then traverse all the map and know where
you hit a polygon. Just draw a little exemple, you will see what I mean.
You can even deal with multple leve inclusions (isle in an isle in an isle)

Well, sorry to be so short, and not very constructive on the list those days,
but I have some important meeting to prepare for next week.  I'll be back
next friday

--
Michel WURTZ - DIG - Maison de la télédétection
               500, rue J.F. Breton
               34093 MONTPELLIER Cedex 5

---------------------------------------- 
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo at geog.uni-hannover.de with
subject 'unsubscribe grass5'