[Tutor] Re: Tutor Digest, Vol 8, Issue 67

[Kent Johnson]

A couple more quick ideas:

You may not even need to take the sum of squares in get_distance(). 
max(abs(ax-bx), abs(ay-by)) would probably work fine for your purposes, 
since you are just trying to find points that are visually close.

You could keep a sorted list of (x, y) coordinates and use that for finding 
the nearest neighbor. Use the bisect module to find where to insert a new 
point in the list. To find the closest point search both ways in the list 
looking for points that are close. If you use the distance metric above you 
can stop searching when abs(ax-bx) is greater than your "closeness" cutoff.

HTH
Kent

At 06:03 AM 10/22/2004 -0400, Kent Johnson wrote:
>A few tweaks for your current algorithm:
>
>- Don't do the sqrt in get_distance(), you don't need the actual distance. 
>Change Sequence.distance to 0.005**2 and everything will work the same.
>
>- Keep the dict keys as floats so you don't have to convert every time in 
>get_distance(), the conversion is likely to be expensive.
>
>- This is gross abuse of a dictionary! You are getting the keys as a list 
>and searching the list!!
>         if s.start in endpoints.keys():
>             endpoints[s.start].append(s)
>
>instead use
>         if s.start in endpoints:
>             endpoints[s.start].append(s)
>
>or my preference which only looks up s.start once:
>       try:
>             endpoints[s.start].append(s)
>       except KeyError: pass
>
>Not sure why you have this. s.start will only be in endpoints once:
>>         if self.points[0] == self.points[-1]:
>>             try: endpoints.pop(s.start)
>>             except KeyError: pass # I don't understand why this exc. is 
>> called
>
>Kent
>
>At 09:49 AM 10/22/2004 +0200, Michael Dunn wrote:
>> > Message: 9
>> > Date: Thu, 21 Oct 2004 20:29:42 -0400
>> > From: Kent Johnson <kent_johnson at skillsoft.com>
>> > Subject: Re: [Tutor] Re: processing lines and polygons
>> >
>> > Michael,
>> >
>> > The problem with snap-to-grid is you can still have two points that are
>> > close but snap to different grid points. Maybe you could put all the 
>> points
>> > into a sorted list and go through it looking for points that are close? If
>> > the list contained the point and the list containing the point, you could
>> > merge them...
>> >
>> > Kent
>>
>>Hi Kent,
>>
>>Yeah, the problem with points snapping to different grid points occurred 
>>to me
>>before I got too far, so I went with just iterating through the list of
>>endpoints searching for near points (I specifically don't want to join any
>>lines by their middles, which makes the task easier). Current problems:
>>
>>1. This search is very slow, which is only a bit of a problem, since I don't
>>need to run this script many times once it's working. However, maybe you (or
>>anybody else interested) could take a look at the get_distance function. 
>>There
>>must be some way of sorting the list of points so I don't have to iterate
>>through the entire thing.
>>
>>2. The endpoint matching routine fails if a segment should be matched at both
>>ends. I think I can get around this by filtering the data through the 
>>script a
>>few times (i.e. until no further changes are made) before doing the format
>>conversion.