1: <?php
  2: 
  3: namespace Quadtree;
  4: 
  5: use Quadtree\Geometry\Bounds;
  6: 
  7: abstract class QuadtreeAbstract
  8: {
  9:     const CAPACITY = 4;
 10: 
 11:     /** @var ICollisionDetector */
 12:     private $detector;
 13:     
 14:     /** @var Geometry\Boundss */
 15:     private $bounds;
 16:     
 17:     /** @var int */
 18:     private $capacity;
 19:     
 20:     /** @var Insertable[] */
 21:     private $items = array();
 22:     
 23:     /** @var Quadtree */
 24:     private $nw;
 25: 
 26:     /** @var Quadtree */
 27:     private $ne;
 28: 
 29:     /** @var Quadtree */
 30:     private $sw;
 31: 
 32:     /** @var Quadtree */
 33:     private $se;
 34:     
 35:     /**
 36:      * @param \Quadtree\ICollisionDetector $detector
 37:      * @param \Quadtree\Geometry\Bounds $bounds
 38:      * @param int $leafCapacity
 39:      */
 40:     function __construct(ICollisionDetector $detector, Geometry\Bounds $bounds, $leafCapacity = NULL)
 41:     {
 42:         $this->detector = $detector;
 43:         $this->bounds = $bounds;
 44: 
 45:         $capacity = (int)$leafCapacity;
 46:         if ($capacity <= 0) {
 47:             $capacity = static::CAPACITY;
 48:         }
 49:         $this->capacity = $capacity;
 50:     }
 51:     
 52:     /**
 53:      * @param \Quadtree\Insertable $item
 54:      * @return boolean
 55:      */
 56:     public function insert(Insertable $item)
 57:     {
 58:         if (!$this->detector->intersects($this->bounds, $item)) {
 59:             return FALSE;
 60:         }
 61:         if ($this->detector->collide($this->items, $item)) {
 62:             return FALSE;
 63:         }
 64:         
 65:         if ($this->nw === NULL && count($this->items) < $this->capacity) {
 66:             $this->items[] = $item;
 67:             return TRUE;
 68:         } else {
 69:             if (count($this->items) >= $this->capacity) {
 70:                 $this->subdivide();
 71:             }
 72:             $nwIn = $this->nw->insert($item);
 73:             $neIn = $this->ne->insert($item);
 74:             $swIn = $this->sw->insert($item);
 75:             $seIn = $this->se->insert($item);
 76:             return $nwIn || $neIn || $swIn || $seIn;
 77:         }
 78:     }
 79:     
 80:     /**
 81:      * Number of levels in the tree
 82:      * @return int
 83:      */
 84:     public function getDepth()
 85:     {
 86:         if ($this->nw === NULL) {
 87:             return 0;
 88:         } else {
 89:             $max = max($this->nw->getDepth(), $this->ne->getDepth(), $this->sw->getDepth(), $this->se->getDepth());
 90:             return 1 + $max;
 91:         }
 92:     }
 93: 
 94:     /**
 95:      * Number of items in the tree
 96:      * @return int
 97:      */
 98:     public function getSize()
 99:     {
100:         if ($this->nw === NULL) {
101:             return count($this->items);
102:         } else {
103:             return $this->nw->getSize() + $this->ne->getSize() + $this->sw->getSize() + $this->se->getSize();
104:         }
105:     }
106:     
107:     private function subdivide()
108:     {
109:         list($this->nw, $this->ne, $this->sw, $this->se) = $this->getDividedBounds();
110:         foreach ($this->items as $item) {
111:             $this->nw->insert($item);
112:             $this->ne->insert($item);
113:             $this->sw->insert($item);
114:             $this->se->insert($item);
115:         }
116:         $this->items = array();
117:     }
118:     
119:     /**
120:      * @return QuadtreeAbstract[]
121:      */
122:     private function getDividedBounds()
123:     {
124:         $c = $this->bounds->getCenter();
125:         $width = $this->bounds->getWidth() / 2;
126:         $height = $this->bounds->getHeight() / 2;
127:         
128:         $nw = new static(new Bounds($width, $height, $c->getLeft() - $width, $c->getTop() - $height), $this->capacity);
129:         $ne = new static(new Bounds($width, $height, $c->getLeft(), $c->getTop() - $height), $this->capacity);
130:         $sw = new static(new Bounds($width, $height, $c->getLeft() - $width, $c->getTop()), $this->capacity);
131:         $se = new static(new Bounds($width, $height, $c->getLeft(), $c->getTop()), $this->capacity);
132:         return array($nw, $ne, $sw, $se);
133:     }
134: }