# # Copyright (c) 2003, 2004, 2005 Art Haas # # This file is part of PythonCAD. # # PythonCAD is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 2 of the License, or # (at your option) any later version. # # PythonCAD is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with PythonCAD; if not, write to the Free Software # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA # # # quadtree class definition # # TODO: Look at using weak references ... from __future__ import generators from PythonCAD.Generic import message class QTreeNode(message.Messenger): messages = { 'subdivided' : True, 'reparented' : True, 'adjusted' : True, 'full' : True, } NENODE = 1 NWNODE = 2 SWNODE = 3 SENODE = 4 def __init__(self): super(QTreeNode, self).__init__() self.__subnodes = None self.__bounds = None self.__parent = None self.__threshold = 5 self.__objects = [] def __len__(self): return len(self.__objects) def setBoundary(self, xmin, ymin, xmax, ymax): if self.__subnodes is not None or self.__parent is not None: raise RuntimeError, "Node cannot have boundary changed." _xmin = xmin if not isinstance(_xmin, float): _xmin = float(xmin) _ymin = ymin if not isinstance(_ymin, float): _ymin = float(ymin) _xmax = xmax if not isinstance(_xmax, float): _xmax = float(xmax) if _xmax < _xmin: raise ValueError, "Illegal values: xmax < xmin" _ymax = ymax if not isinstance(_ymax, float): _ymax = float(ymax) if _ymax < _ymin: raise ValueError, "Illegal values: ymax < ymin" self.__bounds = (_xmin, _ymin, _xmax, _ymax) def unsetBoundary(self): if self.__subnodes is not None or len(self.__objects) != 0: raise RuntimeError, "Node cannot have boundary changed." self.__bounds = None def getBoundary(self): return self.__bounds def setThreshold(self, count): _t = self.__threshold _count = count if not isinstance(_count, int): _count = int(_count) if _count < 1: raise ValueError, "Invalid threshold: %d" % _count if _count != _t: self.__threshold = _count self.sendMessage('adjusted', _t) if len(self.__objects) > _t: self.sendMessage('full') def getThreshold(self): return self.__threshold def setParent(self, parent): _p = self.__parent if parent is not None and not isinstance(parent, QTreeNode): raise TypeError, "Invalid QTreeNode parent: " + `parent` if parent is not _p: self.__parent = parent self.sendMessage('reparented', _p) def getParent(self): return self.__parent def addObject(self, obj): _seen = False for _obj in self.__objects: if _obj is obj: _seen = True break if not _seen: self.__objects.append(obj) if len(self.__objects) > self.__threshold: self.sendMessage('full') def getSubnode(self, subnode): if self.__subnodes is None: raise RuntimeError, "QTreeNode has no subnodes." _ne, _nw, _sw, _se = self.__subnodes if subnode == QTreeNode.NENODE: _sub = _ne elif subnode == QTreeNode.NWNODE: _sub = _nw elif subnode == QTreeNode.SWNODE: _sub = _sw elif subnode == QTreeNode.SENODE: _sub = _se else: raise ValueError, "Unknown subnode code: %d" % subnode return _sub def delObject(self, obj): _objs = self.__objects for _obj in _objs[:]: if obj is _obj: _objs.remove(_obj) break def getObjects(self): return self.__objects[:] def delObjects(self): del self.__objects[:] def hasSubnodes(self): return self.__subnodes is not None def getSubnodes(self): return self.__subnodes def delSubnodes(self): if self.__subnodes is None: raise RuntimeError, "QTreeNode has no subnodes." for _subnode in self.__subnodes: _subnode.setParent(None) self.__subnodes = None def canSubdivide(self): return len(self.__objects) > self.__threshold def subdivide(self): if len(self.__objects) < self.__threshold: return _xmin, _ymin, _xmax, _ymax = self.__bounds _xmid = (_xmin + _xmax)/2.0 _ymid = (_ymin + _ymax)/2.0 # # NE Node # _nenode = QTreeNode() _nenode.setBoundary(_xmid, _ymid, _xmax, _ymax) _nenode.setThreshold(self.__threshold) _nenode.setParent(self) # # NW Node # _nwnode = QTreeNode() _nwnode.setBoundary(_xmin, _ymid, _xmid, _ymax) _nwnode.setThreshold(self.__threshold) _nwnode.setParent(self) # # SW Node # _swnode = QTreeNode() _swnode.setBoundary(_xmin, _ymin, _xmid, _ymid) _swnode.setThreshold(self.__threshold) _swnode.setParent(self) # # SE Node # _senode = QTreeNode() _senode.setBoundary(_xmid, _ymin, _xmax, _ymid) _senode.setThreshold(self.__threshold) _senode.setParent(self) # self.__subnodes = (_nenode, _nwnode, _swnode, _senode) self.delObjects() self.sendMessage('subdivided') def sendsMessage(self, m): if m in QTreeNode.messages: return True return super(QTreeNode, self).sendsMessage(m) class Quadtree(message.Messenger): messages = { } def __init__(self): super(Quadtree, self).__init__() self.__objects = {} self.__queued = [] self.__splitnode = None self.__splitting = False self.__node = QTreeNode() self.__node.connect('full', self.splitTreeNode) def __nonzero__(self): return len(self.__objects) != 0 def __len__(self): return len(self.__objects) def __contains__(self, obj): _oid = id(obj) return _oid in self.__objects def getTreeRoot(self): return self.__node def getNodes(self, *args): _nodes = [self.__node] while len(_nodes): _node = _nodes.pop() if _node.hasSubnodes(): _nodes.extend(_node.getSubnodes()) else: yield _node def addObject(self, obj): _oid = id(obj) if _oid not in self.__objects: self.__objects[_oid] = obj if self.__splitnode is not None and not self.__splitting: self.__splitting = True _node = self.__splitnode _objs = _node.getObjects() _node.subdivide() for _subnode in _node.getSubnodes(): _subnode.connect('full', self.splitTreeNode) for _obj in _objs: _oid = id(_obj) if _oid not in self.__objects: raise ValueError, "Lost object: " + str(_obj) del self.__objects[_oid] self.addObject(_obj) if _oid not in self.__objects: raise ValueError, "self.addObject() failed: " + str(_obj) self.__splitnode = None self.__splitting = False # set to False for Quadtree consistency testing if True or self.__splitnode is not None: return _objcount = len(self.__objects) _nodes = [self.__node] _nobj = {} while len(_nodes): _node = _nodes.pop() if _node.hasSubnodes(): _nodes.extend(_node.getSubnodes()) else: for _obj in _node.getObjects(): _oid = id(_obj) if _oid not in _nobj: _nobj[_oid] = True _nc = len(_nobj) if _nc > _objcount: print "Count inconsistency: %d > %d" % (_nc, _objcount) print "Quadtree objects:" for _obj in self.__objects.values(): print "obj: " + str(_obj) _bounds = self.__node.getBoundary() print "tree bounds: " + str(_bounds) _nodes = [self.__node] _nobj = {} while len(_nodes): _node = _nodes.pop() _bounds = _node.getBoundary() if _node.hasSubnodes(): print "Node with subnodes: " + str(_bounds) _nodes.extend(_node.getSubnodes()) else: print "Base node: " + str(_bounds) for _obj in _node.getObjects(): print "obj: " + str(_obj) _oid = id(_obj) if _oid not in _nobj: _nobj[_oid] = _obj if _oid not in self.__objects: print "###Object lost###" raise RuntimeError, "Inconsistent quadtree" def getObject(self, obj): _oid = id(obj) return self.__objects.get(_oid) # returns None if _oid not found def getObjects(self): return self.__objects.values() def delObject(self, obj): _oid = id(obj) if _oid in self.__objects: del self.__objects[_oid] def delObjects(self): _nodes = [self.__node] while len(_nodes): _node = _nodes.pop() if _node.hasSubnodes(): _nodes.extend(_node.getSubnodes()) _node.delSubnodes() else: for _obj in _node.getObjects(): _obj.disconnect(self) _node.delObjects() if _node.getParent() is not None: _node.setParent(None) _node.disconnect(self) self.__objects.clear() self.__node.unsetBoundary() def queueObject(self, obj): _oid = id(obj) if _oid in self.__objects: raise ValueError, "Object already stored in Quadtree: " + `obj` self.__queued.append(obj) def emptyQueue(self): _objs = self.__queued[:] del self.__queued[:] return _objs def find(self, *params): return None def getClosest(self, x, y, tol): return None def getInRegion(self, xmin, ymin, xmax, ymax): return [] def resize(self, xmin, ymin, xmax, ymax): _xmin = xmin if not isinstance(_xmin, float): _xmin = float(xmin) _ymin = ymin if not isinstance(_ymin, float): _ymin = float(ymin) _xmax = xmax if not isinstance(_xmax, float): _xmax = float(xmax) if _xmax < _xmin: raise ValueError, "Illegal values: xmax < xmin" _ymax = ymax if not isinstance(_ymax, float): _ymax = float(ymax) if _ymax < _ymin: raise ValueError, "Illegal values: ymax < ymin" _root = self.__node if not _root.hasSubnodes(): _root.setBoundary(_xmin, _ymin, _xmax, _ymax) else: _objs = self.__objects.values() self.delObjects() _root.setBoundary(_xmin, _ymin, _xmax, _ymax) for _obj in _objs: self.addObject(_obj) def splitTreeNode(self, node, *args): if self.__splitnode is None: self.__splitnode = node def purgeSubnodes(self, node): if not isinstance(node, QTreeNode): raise TypeError, "Invalid node: " + `node` _tmpnode = node _parent = node.getParent() while _parent is not None: _tmpnode = _parent _parent = _tmpnode.getParent() if self.__node is not _tmpnode: raise ValueError, "Node not in tree." if node.hasSubnodes(): _flag = True _count = 0 for _subnode in node.getSubnodes(): if _subnode.hasSubnodes(): _flag = False break _count = _count + len(_subnode) if _flag and _count < node.getThreshold(): _objs = [] for _subnode in node.getSubnodes(): _objs.extend(_subnode.getObjects()) node.delSubnodes() for _obj in _objs: Quadtree.delObject(self, _obj) self.addObject(_obj) def sendsMessage(self, m): if m in Quadtree.messages: return True return super(Quadtree, self).sendsMessage(m)