[Tutor] processing lines and polygons

[Kent Johnson]

Actually at the end of this algorithm map.values() will be a list of 
consolidated sequences, but each sequence will appear once for each point 
in the sequence. It would be easy to keep a separate list with just the 
unique sequences.

Kent

At 06:05 AM 10/20/2004 -0400, Kent Johnson wrote:
>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
>
>_______________________________________________
>Tutor maillist  -  Tutor at python.org
>http://mail.python.org/mailman/listinfo/tutor