#!/usr/bin/python # neighbor_tree.py # --copyright-- Copyright 2007 (C) Tranzoa, Co. All rights reserved. Warranty: You're free and on your own here. This code is not necessarily up-to-date or of public quality. # --url-- http://www.tranzoa.net/tzpython/ # --email-- pycode is the name to send to. tranzoa.com is the place to send to. # --bodstamps-- # May 10, 2007 bar # November 18, 2007 bar turn on doxygen # November 27, 2007 bar insert boilerplate copyright # May 17, 2008 bar email adr # --eodstamps-- ## \file # # # This module builds a tree that can be quickly added to and searched for cartesian-coordinated items. # The items must have a distance_to() function that returns the distance to another item, where distance is >= 0. # # # From a Dr. Dobbs C++ article # # April 15, 2003 # http://www.ddj.com/dept/cpp/184401449 # # class a_neighbor_tree : """ Store objects ("thangs") in a tree. The objects must implement me.distance_to(another_object), returning a distance >= 0. The tree is quick to store objects and quick to find neighboring objects. The objects can't move once they are put in the tree. """ def __init__(me) : me.l_thang = None me.r_thang = None me.l_child = None me.r_child = None me.l_dist = -1.0 me.r_dist = -1.0 def insert(me, thang) : """ Put the object, 'thang', in the tree. Thang must implement thang.distance_to(another_thang), returning a distance >= 0. """ if not me.l_thang : me.l_thang = thang elif not me.r_thang : me.r_thang = thang else : ld = thang.distance_to(me.l_thang) rd = thang.distance_to(me.r_thang) if ld > rd : if not me.r_child : me.r_child = a_neighbor_tree() me.r_dist = max(me.r_dist, rd) me.r_child.insert(thang) else : if not me.l_child : me.l_child = a_neighbor_tree() me.l_dist = max(me.l_dist, ld) me.l_child.insert(thang) pass pass def _nearest(me, thang, max_dist) : nt = None if me.l_thang : d = me.l_thang.distance_to(thang) if d <= max_dist : nt = me.l_thang max_dist = d pass if me.r_thang : d = me.r_thang.distance_to(thang) if d <= max_dist : nt = me.r_thang max_dist = d pass if me.l_child and (max_dist + me.l_dist >= me.l_thang.distance_to(thang)) : (nnt, md) = me.l_child._nearest(thang, max_dist) if nnt : (nt, max_dist ) = (nnt, md) pass if me.r_child and (max_dist + me.r_dist >= me.r_thang.distance_to(thang)) : (nnt, md) = me.r_child._nearest(thang, max_dist) if nnt : (nt, max_dist ) = (nnt, md) pass return( ( nt, max_dist ) ) def nearest(me, thang, max_dist) : """ Find the nearest thang to the given 'thang' that's within 'max_dist' from 'thang'. """ (ft, md ) = me._nearest(thang, max_dist) return(ft) def _farthest(me, thang, min_dist) : nt = None if me.l_thang : d = me.l_thang.distance_to(thang) if d >= min_dist : nt = me.l_thang min_dist = d pass if me.r_thang : d = me.r_thang.distance_to(thang) if d >= min_dist : nt = me.r_thang min_dist = d pass if me.l_child and (min_dist <= me.l_dist + me.l_thang.distance_to(thang)) : (nnt, md) = me.l_child._farthest(thang, min_dist) if nnt : (nt, min_dist ) = (nnt, md) pass if me.r_child and (min_dist <= me.r_dist + me.r_thang.distance_to(thang)) : (nnt, md) = me.r_child._farthest(thang, min_dist) if nnt : (nt, min_dist ) = (nnt, md) pass return(( nt, min_dist )) def farthest(me, thang, min_dist) : """ Find the farthest thang from the given 'thang' that's farther away than 'min_dist' from 'thang'. """ (ft, md ) = me._farthest(thang, min_dist) return(ft) def _str(me, depth) : s = " " * depth if me.l_thang : s += "l:" + str(me.l_thang) if me.r_thang : s += " r:" + str(me.r_thang) if s : s += "\n" if me.l_child : s += " " * (depth + 1) s += "Left:\n" s += me.l_child._str(depth + 1) if me.r_child : s += " " * (depth + 1) s += "Rite:\n" s += me.r_child._str(depth + 1) pass return(s) def __str__(me) : return(me._str(0)) pass # a_neighbor_tree dcnt = 0 # # # Test code. # # if __name__ == '__main__' : import math import random import sys import TZCommandLineAtFile del(sys.argv[0]) TZCommandLineAtFile.expand_at_sign_command_line_files(sys.argv) class a_p : def __init__(me, x, y) : me.x = float(x) me.y = float(y) def distance_to(me, p) : global dcnt xx = me.x - p.x yy = me.y - p.y dcnt += 1 return(math.sqrt((xx * xx) + (yy * yy))) def __str__(me) : return("%f:%f" % ( me.x, me.y ) ) pass t = a_neighbor_tree() if not len(sys.argv) : print "testing" ps = [ None ] * 500000 for i in xrange(len(ps)) : p = a_p(random.random() * 10000.0, random.random() * 10000.0) ps[i] = p t.insert(p) for i in xrange(1000) : p = a_p(random.random() * 10000.0, random.random() * 10000.0) print p sys.stdout.flush() dcnt = 0 fn = t.nearest( p, 10000000000000000000.0) print " dcnt", dcnt, " nearest", fn, sys.stdout.flush() dcnt = 0 ff = t.farthest(p, 0) print " dcnt", dcnt, " farthest", ff sys.stdout.flush() mind = 10000000000 maxd = 0 dcnt = 0 for j in xrange(len(ps)) : d = p.distance_to(ps[j]) if maxd < d : maxd = d maxp = ps[j] if mind > d : mind = d minp = ps[j] pass print " dcnt", dcnt, print " nearest", minp, print " farthest", maxp sys.stdout.flush() if fn != minp : print "Wrong" sys.exit(102) if ff != maxp : print "Wrong" sys.exit(102) pass pass else : if (len(sys.argv) % 2) or (len(sys.argv) < 4) : print "I expect X Y coordinates. I'll look for the last one in the rest." sys.exit(101) while len(sys.argv) >= 4 : p = a_p(float(sys.argv[0]), float(sys.argv[1])) t.insert(p) sys.argv = sys.argv[2:] print t o = a_p(float(sys.argv[0]), float(sys.argv[1])) print "nearest", t.nearest( o, 10000000000000000000.0) print "farthest", t.farthest(o, 0) pass # # # # eof