[Tutor] processing lines and polygons

Kent Johnson kent_johnson at skillsoft.com
Wed Oct 20 13:39:14 CEST 2004

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.


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.
>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:
>>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 
>>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 
>>(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 
>>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...
>>Tutor maillist  -  Tutor at python.org
>Tutor maillist  -  Tutor at python.org

More information about the Tutor mailing list