QuadTree::retrieve() - Code Metrics - sixty-nine/php-data-types - Measure and Improve Code Quality continuously with Scrutinizer

QuadTree::retrieve() B
last analyzed 2018-10-08 09:14 UTC

↳ Parent: QuadTree

Complexity

Conditions	6
Paths	7

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	11
CRAP Score	6

Importance

Changes

Metric	Value
dl	0
loc	24
ccs	11
cts	11
cp	1
rs	8.9137
c	0
b	0
f	0
cc	6
nc	7
nop	1
crap	6

<?php

namespace SixtyNine\DataTypes;

use Doctrine\Common\Collections\ArrayCollection;

class QuadTree
{
    const Q_TOP_LEFT = 0;
    const Q_TOP_RIGHT = 1;
    const Q_BOTTOM_LEFT = 2;
    const Q_BOTTOM_RIGHT = 3;

    /** @var int */
    protected $level;
    /** @var int */
    protected $maxObjects;
    /** @var int */
    protected $maxLevels;
    /** @var ArrayCollection */
    protected $objects;
    /** @var \SixtyNine\DataTypes\Box */
    protected $bounds;
    /** @var bool */
    protected $isSplit = false;
    /** @var array QuadTree[] */
    protected $nodes;

    /**
     * @param Box $bounds
     * @param int $level
     * @param int $maxObjects
     * @param int $maxLevels
     */
    public function __construct(Box $bounds, $level = 0, $maxObjects = 10, $maxLevels = 10)
    {
        $this->level = $level;
        $this->maxObjects = $maxObjects;
        $this->maxLevels = $maxLevels;
        $this->objects = new ArrayCollection();
        $this->bounds = $bounds;
    }

    /** @SuppressWarnings(PHPMD.ShortVariable) */
    public function split()
    {
        $this->isSplit = true;

        $subWidth = (int)($this->bounds->getWidth() / 2);
        $subHeight = (int)($this->bounds->getHeight() / 2);

        $x = $this->bounds->getX();
        $y = $this->bounds->getY();

        $this->nodes = array();
        $this->nodes[self::Q_TOP_LEFT] = new Quadtree(new Box($x, $y, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
        $this->nodes[self::Q_TOP_RIGHT] = new Quadtree(new Box($x + $subWidth, $y, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
        $this->nodes[self::Q_BOTTOM_LEFT] = new Quadtree(new Box($x, $y + $subHeight, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
        $this->nodes[self::Q_BOTTOM_RIGHT] = new Quadtree(new Box($x + $subWidth, $y + $subHeight, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
    }

    /**
     * @param Box $box
     * @return bool
     */
    protected function isInTopQuadrant(Box $box)
    {
        $hMidpoint = $this->bounds->getCenter()->getY();
        return $box->getY() <= $hMidpoint && $box->getY() + $box->getHeight() <= $hMidpoint;
    }

    /**
     * @param Box $box
     * @return bool
     */
    protected function isInBottomQuadrant(Box $box)
    {
        $hMidpoint = $this->bounds->getCenter()->getY();
        return $box->getY() >= $hMidpoint;
    }

    /**
     * @param Box $box
     * @return bool
     */
    protected function isInLeftQuadrant(Box $box)
    {
        $vMidpoint = $this->bounds->getCenter()->getX();
        return $box->getX() <= $vMidpoint && $box->getX() + $box->getWidth() <= $vMidpoint;
    }

    /**
     * @param Box $box
     * @return bool
     */
    protected function isInRightQuadrant(Box $box)
    {
        $vMidpoint = $this->bounds->getCenter()->getX();
        return $box->getX() >= $vMidpoint;
    }

    /**
     * @param Box $box
     * @return int
     */
    public function getIndex(Box $box)
    {
        $topQuadrant = $this->isInTopQuadrant($box);
        $bottomQuadrant = $this->isInBottomQuadrant($box);
        $leftQuadrant = $this->isInLeftQuadrant($box);
        $rightQuadrant = $this->isInRightQuadrant($box);

        switch (true) {
            case $leftQuadrant && $topQuadrant:
                return self::Q_TOP_LEFT;
            case $rightQuadrant && $topQuadrant:
                return self::Q_TOP_RIGHT;
            case $leftQuadrant && $bottomQuadrant:
                return self::Q_BOTTOM_LEFT;
            case $rightQuadrant && $bottomQuadrant:
                return self::Q_BOTTOM_RIGHT;
        }

        return -1;
    }

    /**
     * @param Box $box
     */
    public function insert(Box $box)
    {
        if ($this->isSplit) {
            $index = $this->getIndex($box);
            if ($index !== -1) {
                /** @var QuadTree $node */
                $node = $this->nodes[$index];
                $node->insert($box);
                return;
            }
        }

        $this->objects->add($box);

        if (count($this->objects) > $this->maxObjects && $this->level < $this->maxLevels) {
            if (!$this->isSplit) {
                $this->split();
            }

            foreach ($this->objects as $object) {
                $index = $this->getIndex($object);
                if ($index !== -1) {
                    $this->objects->removeElement($object);
                    /** @var QuadTree $node */
                    $node = $this->nodes[$index];
                    $node->insert($object);
                }
            }
        }
    }

    /**
     * @return int
     */
    public function count()
    {
        $count = $this->objects->count();

        if ($this->isSplit) {
            /** @var QuadTree $node */
            foreach ($this->nodes as $node) {
                $count += $node->count();
            }
        }

        return $count;
    }

    /**
     * @param Box $box
     * @return array
     */
    public function retrieve(Box $box)
    {
        $return = array();

        if (!$this->bounds->intersects($box, false)) {
            return array();
        }

        /** @var Box $object */
        foreach ($this->objects as $object) {
            if ($object->intersects($box, false)) {
                $return[] = $object;
            }
        }

        if ($this->isSplit) {
            /** @var QuadTree $node */
            foreach ($this->nodes as $node) {
                $return = array_merge($return, $node->retrieve($box));
            }
        }

        return $return;
    }

    /**
     * @param Box $box
     * @return bool
     */
    public function collides(Box $box)
    {
        foreach ($this->objects as $object) {
            if ($box->intersects($object)) {
                return true;
            }
        }

        if ($this->isSplit) {
            $index = $this->getIndex($box);
            $nodes = (-1 === $index) ? $this->nodes : array($this->nodes[$index]);
            /** @var QuadTree $node */
            foreach ($nodes as $node) {
                if ($node->collides($box)) {
                    return true;
                }
            }
        }

        return false;
    }

    /**
     * @return string
     * @codeCoverageIgnore
     */
    public function __toString()
    {
        $padding = str_repeat('> ', $this->level);
        $res = sprintf(
            '%sBounds: %s, objects: %s',
            $padding,
            $this->bounds,
            $this->objects->count()
        );

        foreach ($this->objects as $box) {
            $res .= PHP_EOL . $padding . '  - ' . (string)$box;
        }

        if (null !== $this->nodes) {
            foreach ($this->nodes as $node) {
                $res .= PHP_EOL . (string)$node;
            }
        }

        return $res;
    }

    /**
     * @return array
     */
    public function getAllObjects()
    {
        $return = array();

        $return = array_merge($return, $this->objects->toArray());

        if ($this->isSplit) {
            /** @var QuadTree $node */
            foreach ($this->nodes as $node) {
                $return = array_merge($return, $node->getAllObjects());
            }
        }

        return $return;
    }

    /**
     * @return Box
     */
    public function getBounds()
    {
        return $this->bounds;
    }
}


1		<?php
2
3		namespace SixtyNine\DataTypes;
4
5		use Doctrine\Common\Collections\ArrayCollection;
6
7		class QuadTree
8		{
9		const Q_TOP_LEFT = 0;
10		const Q_TOP_RIGHT = 1;
11		const Q_BOTTOM_LEFT = 2;
12		const Q_BOTTOM_RIGHT = 3;
13
14		/** @var int */
15		protected $level;
16		/** @var int */
17		protected $maxObjects;
18		/** @var int */
19		protected $maxLevels;
20		/** @var ArrayCollection */
21		protected $objects;
22		/** @var \SixtyNine\DataTypes\Box */
23		protected $bounds;
24		/** @var bool */
25		protected $isSplit = false;
26		/** @var array QuadTree[] */
27		protected $nodes;
28
29		/**
30		* @param Box $bounds
31		* @param int $level
32		* @param int $maxObjects
33		* @param int $maxLevels
34		*/
35	20	public function __construct(Box $bounds, $level = 0, $maxObjects = 10, $maxLevels = 10)
36		{
37	20	$this->level = $level;
38	20	$this->maxObjects = $maxObjects;
39	20	$this->maxLevels = $maxLevels;
40	20	$this->objects = new ArrayCollection();
41	20	$this->bounds = $bounds;
42	20	}
43
44		/** @SuppressWarnings(PHPMD.ShortVariable) */
45	7	public function split()
46		{
47	7	$this->isSplit = true;
48
49	7	$subWidth = (int)($this->bounds->getWidth() / 2);
50	7	$subHeight = (int)($this->bounds->getHeight() / 2);
51
52	7	$x = $this->bounds->getX();
53	7	$y = $this->bounds->getY();
54
55	7	$this->nodes = array();
56	7	$this->nodes[self::Q_TOP_LEFT] = new Quadtree(new Box($x, $y, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
57	7	$this->nodes[self::Q_TOP_RIGHT] = new Quadtree(new Box($x + $subWidth, $y, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
58	7	$this->nodes[self::Q_BOTTOM_LEFT] = new Quadtree(new Box($x, $y + $subHeight, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
59	7	$this->nodes[self::Q_BOTTOM_RIGHT] = new Quadtree(new Box($x + $subWidth, $y + $subHeight, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
60	7	}
61
62		/**
63		* @param Box $box
64		* @return bool
65		*/
66	17	protected function isInTopQuadrant(Box $box)
67		{
68	17	$hMidpoint = $this->bounds->getCenter()->getY();
69	17	return $box->getY() <= $hMidpoint && $box->getY() + $box->getHeight() <= $hMidpoint;
70		}
71
72		/**
73		* @param Box $box
74		* @return bool
75		*/
76	17	protected function isInBottomQuadrant(Box $box)
77		{
78	17	$hMidpoint = $this->bounds->getCenter()->getY();
79	17	return $box->getY() >= $hMidpoint;
80		}
81
82		/**
83		* @param Box $box
84		* @return bool
85		*/
86	17	protected function isInLeftQuadrant(Box $box)
87		{
88	17	$vMidpoint = $this->bounds->getCenter()->getX();
89	17	return $box->getX() <= $vMidpoint && $box->getX() + $box->getWidth() <= $vMidpoint;
90		}
91
92		/**
93		* @param Box $box
94		* @return bool
95		*/
96	17	protected function isInRightQuadrant(Box $box)
97		{
98	17	$vMidpoint = $this->bounds->getCenter()->getX();
99	17	return $box->getX() >= $vMidpoint;
100		}
101
102		/**
103		* @param Box $box
104		* @return int
105		*/
106	17	public function getIndex(Box $box)
107		{
108	17	$topQuadrant = $this->isInTopQuadrant($box);
109	17	$bottomQuadrant = $this->isInBottomQuadrant($box);
110	17	$leftQuadrant = $this->isInLeftQuadrant($box);
111	17	$rightQuadrant = $this->isInRightQuadrant($box);
112
113		switch (true) {
114	17	case $leftQuadrant && $topQuadrant:
115	8	return self::Q_TOP_LEFT;
116	15	case $rightQuadrant && $topQuadrant:
117	7	return self::Q_TOP_RIGHT;
118	13	case $leftQuadrant && $bottomQuadrant:
119	8	return self::Q_BOTTOM_LEFT;
120	11	case $rightQuadrant && $bottomQuadrant:
121	7	return self::Q_BOTTOM_RIGHT;
122		}
123
124	7	return -1;
125		}
126
127		/**
128		* @param Box $box
129		*/
130	7	public function insert(Box $box)
131		{
132	7	if ($this->isSplit) {
133	5	$index = $this->getIndex($box);
134	5	if ($index !== -1) {
135		/** @var QuadTree $node */
136	5	$node = $this->nodes[$index];
137	5	$node->insert($box);
138	5	return;
139		}
140		}
141
142	7	$this->objects->add($box);
143
144	7	if (count($this->objects) > $this->maxObjects && $this->level < $this->maxLevels) {
145	6	if (!$this->isSplit) {
146	6	$this->split();
147		}
148
149	6	foreach ($this->objects as $object) {
150	6	$index = $this->getIndex($object);
151	6	if ($index !== -1) {
152	6	$this->objects->removeElement($object);
153		/** @var QuadTree $node */
154	6	$node = $this->nodes[$index];
155	6	$node->insert($object);
156		}
157		}
158		}
159	7	}
160
161		/**
162		* @return int
163		*/
164	3	public function count()
165		{
166	3	$count = $this->objects->count();
167
168	3	if ($this->isSplit) {
169		/** @var QuadTree $node */
170	1	foreach ($this->nodes as $node) {
171	1	$count += $node->count();
172		}
173		}
174
175	3	return $count;
176		}
177
178		/**
179		* @param Box $box
180		* @return array
181		*/
182	2	public function retrieve(Box $box)
183		{
184	2	$return = array();
185
186	2	if (!$this->bounds->intersects($box, false)) {
187	1	return array();
188		}
189
190		/** @var Box $object */
191	2	foreach ($this->objects as $object) {
192	2	if ($object->intersects($box, false)) {
193	2	$return[] = $object;
194		}
195		}
196
197	2	if ($this->isSplit) {
198		/** @var QuadTree $node */
199	2	foreach ($this->nodes as $node) {
200	2	$return = array_merge($return, $node->retrieve($box));
201		}
202		}
203
204	2	return $return;
205		}
206
207		/**
208		* @param Box $box
209		* @return bool
210		*/
211	2	public function collides(Box $box)
212		{
213	2	foreach ($this->objects as $object) {
214	2	if ($box->intersects($object)) {
215	2	return true;
216		}
217		}
218
219	2	if ($this->isSplit) {
220	1	$index = $this->getIndex($box);
221	1	$nodes = (-1 === $index) ? $this->nodes : array($this->nodes[$index]);
222		/** @var QuadTree $node */
223	1	foreach ($nodes as $node) {
224	1	if ($node->collides($box)) {
225	1	return true;
226		}
227		}
228		}
229
230	2	return false;
231		}
232
233		/**
234		* @return string
235		* @codeCoverageIgnore
236		*/
237		public function __toString()
238		{
239		$padding = str_repeat('> ', $this->level);
240		$res = sprintf(
241		'%sBounds: %s, objects: %s',
242		$padding,
243		$this->bounds,
244		$this->objects->count()
245		);
246
247		foreach ($this->objects as $box) {
248		$res .= PHP_EOL . $padding . ' - ' . (string)$box;
249		}
250
251		if (null !== $this->nodes) {
252		foreach ($this->nodes as $node) {
253		$res .= PHP_EOL . (string)$node;
254		}
255		}
256
257		return $res;
258		}
259
260		/**
261		* @return array
262		*/
263	2	public function getAllObjects()
264		{
265	2	$return = array();
266
267	2	$return = array_merge($return, $this->objects->toArray());
268
269	2	if ($this->isSplit) {
270		/** @var QuadTree $node */
271	2	foreach ($this->nodes as $node) {
272	2	$return = array_merge($return, $node->getAllObjects());
273		}
274		}
275
276	2	return $return;
277		}
278
279		/**
280		* @return Box
281		*/
282	3	public function getBounds()
283		{
284	3	return $this->bounds;
285		}
286		}
287

sixty-nine / php-data-types

QuadTree::retrieve() B last analyzed 2018-10-08 09:14 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

QuadTree::retrieve() B
last analyzed 2018-10-08 09:14 UTC