[Tutor] processing lines and polygons

[Kent Johnson]

Dictionaries are very helpful with this type of problem. I would try 
building a dictionary that maps individual points to the sequence 
containing the point. When you create a new sequence from the input, look 
up each of its points in the dict. If you find any of them, then combine 
the two sequences. Finally add the new points to the dict. Something like this:

map = {}
for each sequence s:
   sfinal = s
   for each point p in s:
     s2 = map.get(p)
     if s2:
       add the points in s to s2
       sfinal = s2 # remember the new sequence containing points of the 
original s
       break
   for each point p in s:
     map[p] = sfinal

When you are done, map.values() is the list of consolidated sequences.

Two things that could complicate the algorithm
- if the test for whether to join to sequences is more complicated than 
just having points in common then you will have to make the test 'if s2:' 
more complex
  - if a point can be in two sequences that should not be joined, then the 
map entries have to be lists of sequences rather than single sequences. 
This will add a little complexity but not much.

HTH
Kent

At 10:50 AM 10/20/2004 +0200, Michael Dunn wrote:
>Hi Tutors,
>
>I'm doing some GIS work using coastlines extracted from the nifty web form at:
>
>http://rimmer.ngdc.noaa.gov/mgg/coast/getcoast.html
>
>It produces a huge list of longtitude-latitude points joined up in sections
>delimited by "# -b" (representing zigzag lines) . These can be easily
>converted into e.g. MapInfo import format. However the data is slightly
>messy--some of the lines are broken up into smaller lines, which means that
>once imported into MapInfo I can't easily select what should be a single piece
>of coastline. It seems like it should be a reasonably simple piece of
>text-processing to get them all together: if I have a sequence of points 
>(a, b,
>c) and a sequence (c, d, a) then I just need to transform them into a sequence
>(a, b, c, d, a).  However I've spend while working on it, and I can't come
>up with a suitable algorithm to do this. Any pointers?
>
>My problem is algorithmic rather than syntactic, so I won't post any of the
>code I've already written until I've got a better handle on what how I'm 
>trying
>to go about it.
>
>This is a simplified example of the data (I've deleted ~5MB of points): the
>first section is a polygon (i.e. the startpoint is the same as the endpoint)
>and so can be left untouched; the next two are lines which should be joined up
>to make a polygon, and the last three are lines which should be joined up to
>make a line
>
># -b
>146.781336      -19.195938
>146.781336      -19.194178
>146.781336      -19.195938
># -b
>146.929480      -19.296558
>146.931534      -19.298025
>146.932414      -19.296265
># -b
>146.932414      -19.296265
>146.930947      -19.295385
>146.929480      -19.296558
># -b
>146.752881      -19.119079
>146.753468      -19.119666
># -b
>146.754054      -19.119666
>146.754934      -19.118786
>146.756108      -19.117612
># -b
>146.756108      -19.117612
>146.755815      -19.117026
>146.752881      -19.118199
>
>Looking forward to hearing any ideas...
>
>Michael
>
>_______________________________________________
>Tutor maillist  -  Tutor at python.org
>http://mail.python.org/mailman/listinfo/tutor