Commits

Andrew Peterson committed b219106

Add documentation to spatial module.

  • Participants
  • Parent commits 6ba43a1
  • Branches comments

Comments (0)

Files changed (1)

File djlib/spatial.py

+""" Spatial Module
+
+Provides various classes to optimize spatial partitioning.
+
+Overview:
+    QuadTree - A tree structure containing arbitrary data in nodes with four children.
+    RectTree - A QuadTree using Rects to segment space into a four equal partition heirarchy.
+    ExpandingRectTree - Modification of RectTree that allows for dynamic expansion when data added
+                        is outside of current RectTree bounds.
+"""
+
 from primitives import Point, Rect
 
 class QuadTree:
+    """ A tree structure containing arbitrary data in nodes with four children.
+
+    Mainly a base class for handling generic QuadTree operations. Class is left
+    Data agnostic with certain methods needing to be overridden before any real
+    functionality is available.
+
+    Class is designed as a self-containing system. It represents the tree and
+    all nodes in the tree.
+
+    Notes:
+        MAX_DATA is safe to modify and controls how much data can exist in a node before it is forced to
+        child nodes to distribute the data load.
+        Modifying NUM_CHILDREN violates the core principle of a `QuadTree`.
+    """
 
     NUM_CHILDREN = 4
     MAX_DATA = 10
         self.data = None
 
     def insert(self, data):
+        """ Insert new data into the subtree.
+
+        Data is inserted into the highest selected node that is not full.
+        Child nodes are selected using `_childIndex()` to hash the data. If all
+        nodes are full, the selected node will create child nodes to distribute
+        the its contents.
+        """
+
         # Leaf nodes have no children
         if not self.children:
             # no existing data
 
 
     def remove(self, data):
+        """ Remove data from the subtree. """
         # Leaf nodes have no children
         if not self.children:
             if not self.data:
                 self.children = None
 
     def empty(self):
+        """ Return whether node is empty of data or children. """
         return not self.children and not self.data
 
     def count(self):
+        """ Return the amount of data store in this subtree. """
         if self.data:
             return len(self.data)
         
         return c
 
     def _childIndex(self, data):
+        """ Return 0-3 to determine which child node to place data into.
+
+        This is a hashing function that should be overriden to provide data
+        placement specific to the type of QuadTree.
+        """
         return 0
 
     def _createChildren(self):
+        """ Control creation of children in subclasses. """
         return [QuadTree()] * self.NUM_CHILDREN
 
     def __iter__(self):
-            if self.data:
-                for d in self.data:
-                    yield d
+        """ Provide iteration capabilities for entire tree. """
+        if self.data:
+            for d in self.data:
+                yield d
 
-            if self.children:
-                for child in self.children:
-                    for d in child:
-                        yield d
+        if self.children:
+            for child in self.children:
+                for d in child:
+                    yield d
 
 #end QuadTree
 
 class RectTree(QuadTree):
+    """ A QuadTree using Rects to segment space into a four equal partition heirarchy.
 
+    Specialized QuadTree that iterative quarters a geometric space to efficiently
+    manage objects within that space. Provides a means of finding objects within
+    the same (or nearest) partitions for proximity tests.
+
+    Notes:
+        MIN_RECT defines the smallest size a partition can become before it starts
+        overriding MAX_DATA limitations and no longer creating children.
+    """
     MIN_RECT = Rect.fromSides(0, 0, 250, 250)
 
     def __init__(self, rect):
         self.rect = rect
 
     def minNode(self, bounds_rect):
+        """ Return the first node that fully contains the specified bounds.
 
+        Args:
+            bounds_rect(Rect) - Bounding Rect that the node needs to contain
+        """
         if not self.rect.contains(bounds_rect):
             return None
 
         return self
 
     def getData(self, bounds_rect = None):
+        """ Return all data contained in this subtree.
+
+        Args:
+            bounds_rect(Rect, Optional) - Bounding Rect that limits returned data
+                                to nodes that intersect this Rect. Data is not
+                                always guaranteed to be *in* bounds_rect, but
+                                all data in bounds_rect will be available.
+        """
         if bounds_rect and not bounds_rect.intersects(self.rect):
             return []
 
 
         
     def _childIndex(self, entity):
+        """ Override to select child index based on data quadrant. """
         pos = entity.getPosition()
         center = self.rect.center()
         return (0 if pos.x < center.x else 1) + 2*(0 if pos.y < center.y else 1)
 
     def _createChildren(self):
+        """ Define Quadrant Rects when creating children. """
         pos = self.rect.getPosition()
         center = self.rect.center()
         size = center - pos
 # Tree encompassing a normal RectTree to allow for it to be dynamically expanded to
 # any size based on the data inserted into it.
 class ExpandingRectTree:
+    """ Modification of RectTree that allows for dynamic expansion when data added
+        is outside of current RectTree bounds.
+
+    The root of the tree is dynamically recreated whenever inserted data cannot
+    be contained by current tree bounds. This allows for an infinitely expanding 
+    spatial partitioning tree.
+    """
 
     def __init__(self, init_rect):
         self.root = RectTree(init_rect)
     # override the default insert to check for data
     # falling outside of the current tree.
     def insert(self, data):
+        """ Insert new data into the subtree.
+
+        If data cannot be contained by root Rect, the tree will be expanded so
+        it can.
+        """
 
         # expand tree until it can contain new data
         while not self.root.rect.contains(data.getPosition()):
         return self.root.insert(data)
 
     def _expandTree(self, data):
+        """ Create new root with bounding rect large enough to contain data.
+
+        Old root node is retained as a child to the new root. All other child
+        nodes are create to allow for compatibility with existing QuadTree code.
+        """
         
         # double the size of the tree
         newSize = self.root.rect.size * 2