QuadTree::getAllObjects() - Code Metrics - Inspection of "Simplify code of QuadTree" - sixty-nine/php-data-types - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 260677...732299 )

by Dan

created 2017-04-16 08:28 UTC

QuadTree::getAllObjects() A

↳ Parent: QuadTree

Complexity

Conditions	3
Paths	2

Size

Total Lines	15
Code Lines	7

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	7
CRAP Score	3

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
c	1
b	0
f	0
dl	0
loc	15
ccs	7
cts	7
cp	1
rs	9.4285
cc	3
eloc	7
nc	2
nop	0
crap	3

<?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;
    }

    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 int
     */
    public function getIndex(Box $box)
    {
        $center = $this->bounds->getCenter();
        $vMidpoint = $center->getX();
        $hMidpoint = $center->getY();

        $topQuadrant = ($box->getY() <= $hMidpoint && $box->getY() + $box->getHeight() <= $hMidpoint);
        $bottomQuadrant = ($box->getY() >= $hMidpoint);
        $leftQuadrant = $box->getX() <= $vMidpoint && $box->getX() + $box->getWidth() <= $vMidpoint;
        $rightQuadrant = $box->getX() >= $vMidpoint;

        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	7	public function split()
45		{
46	7	$this->isSplit = true;
47
48	7	$subWidth = (int)($this->bounds->getWidth() / 2);
49	7	$subHeight = (int)($this->bounds->getHeight() / 2);
50
51	7	$x = $this->bounds->getX();
52	7	$y = $this->bounds->getY();
53
54	7	$this->nodes = array();
55	7	$this->nodes[self::Q_TOP_LEFT] = new Quadtree(new Box($x, $y, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
56	7	$this->nodes[self::Q_TOP_RIGHT] = new Quadtree(new Box($x + $subWidth, $y, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
57	7	$this->nodes[self::Q_BOTTOM_LEFT] = new Quadtree(new Box($x, $y + $subHeight, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
58	7	$this->nodes[self::Q_BOTTOM_RIGHT] = new Quadtree(new Box($x + $subWidth, $y + $subHeight, $subWidth, $subHeight), $this->level + 1, $this->maxObjects, $this->maxLevels);
59	7	}
60
61		/**
62		* @param Box $box
63		* @return int
64		*/
65	17	public function getIndex(Box $box)
66		{
67	17	$center = $this->bounds->getCenter();
68	17	$vMidpoint = $center->getX();
69	17	$hMidpoint = $center->getY();
70
71	17	$topQuadrant = ($box->getY() <= $hMidpoint && $box->getY() + $box->getHeight() <= $hMidpoint);
72	17	$bottomQuadrant = ($box->getY() >= $hMidpoint);
73	17	$leftQuadrant = $box->getX() <= $vMidpoint && $box->getX() + $box->getWidth() <= $vMidpoint;
74	17	$rightQuadrant = $box->getX() >= $vMidpoint;
75
76		switch (true) {
77	17	case $leftQuadrant && $topQuadrant:
78	8	return self::Q_TOP_LEFT;
79	15	case $rightQuadrant && $topQuadrant:
80	7	return self::Q_TOP_RIGHT;
81	13	case $leftQuadrant && $bottomQuadrant:
82	8	return self::Q_BOTTOM_LEFT;
83	11	case $rightQuadrant && $bottomQuadrant:
84	7	return self::Q_BOTTOM_RIGHT;
85		}
86
87	7	return -1;
88		}
89
90		/**
91		* @param Box $box
92		*/
93	7	public function insert(Box $box)
94		{
95	7	if ($this->isSplit) {
96	5	$index = $this->getIndex($box);
97	5	if ($index !== -1) {
98		/** @var QuadTree $node */
99	5	$node = $this->nodes[$index];
100	5	$node->insert($box);
101	5	return;
102		}
103		}
104
105	7	$this->objects->add($box);
106
107	7	if (count($this->objects) > $this->maxObjects && $this->level < $this->maxLevels) {
108	6	if (!$this->isSplit) {
109	6	$this->split();
110		}
111
112	6	foreach ($this->objects as $object) {
113	6	$index = $this->getIndex($object);
114	6	if ($index !== -1) {
115	6	$this->objects->removeElement($object);
116		/** @var QuadTree $node */
117	6	$node = $this->nodes[$index];
118	6	$node->insert($object);
119		}
120		}
121		}
122	7	}
123
124		/**
125		* @return int
126		*/
127	3	public function count()
128		{
129	3	$count = $this->objects->count();
130
131	3	if ($this->isSplit) {
132		/** @var QuadTree $node */
133	1	foreach ($this->nodes as $node) {
134	1	$count += $node->count();
135		}
136		}
137
138	3	return $count;
139		}
140
141		/**
142		* @param Box $box
143		* @return array
144		*/
145	2	public function retrieve(Box $box)
146		{
147	2	$return = array();
148
149	2	if (!$this->bounds->intersects($box, false)) {
150	1	return array();
151		}
152
153		/** @var Box $object */
154	2	foreach ($this->objects as $object) {
155	2	if ($object->intersects($box, false)) {
156	2	$return[] = $object;
157		}
158		}
159
160	2	if ($this->isSplit) {
161		/** @var QuadTree $node */
162	2	foreach ($this->nodes as $node) {
163	2	$return = array_merge($return, $node->retrieve($box));
164		}
165		}
166
167	2	return $return;
168		}
169
170		/**
171		* @param Box $box
172		* @return bool
173		*/
174	2	public function collides(Box $box)
175		{
176	2	foreach ($this->objects as $object) {
177	2	if ($box->intersects($object)) {
178	2	return true;
179		}
180		}
181
182	2	if ($this->isSplit) {
183
184	1	$index = $this->getIndex($box);
185	1	$nodes = (-1 === $index) ? $this->nodes : array($this->nodes[$index]);
186		/** @var QuadTree $node */
187	1	foreach ($nodes as $node) {
188	1	if ($node->collides($box)) {
189	1	return true;
190		}
191		}
192		}
193
194	2	return false;
195		}
196
197		/**
198		* @return string
199		* @codeCoverageIgnore
200		*/
201		public function __toString()
202		{
203		$padding = str_repeat('> ', $this->level);
204		$res = sprintf(
205		'%sBounds: %s, objects: %s',
206		$padding,
207		$this->bounds,
208		$this->objects->count()
209		);
210
211		foreach ($this->objects as $box) {
212		$res .= PHP_EOL . $padding . ' - ' . (string)$box;
213		}
214
215		if (null !== $this->nodes) {
216		foreach ($this->nodes as $node) {
217		$res .= PHP_EOL . (string)$node;
218		}
219		}
220
221		return $res;
222		}
223
224		/**
225		* @return array
226		*/
227	2	public function getAllObjects()
228		{
229	2	$return = array();
230
231	2	$return = array_merge($return, $this->objects->toArray());
232
233	2	if ($this->isSplit) {
234		/** @var QuadTree $node */
235	2	foreach ($this->nodes as $node) {
236	2	$return = array_merge($return, $node->getAllObjects());
237		}
238		}
239
240	2	return $return;
241		}
242
243		/**
244		* @return Box
245		*/
246	3	public function getBounds()
247		{
248	3	return $this->bounds;
249		}
250		}
251

sixty-nine / php-data-types

Push — master ( 260677...732299 )

QuadTree::getAllObjects() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like