QuadTree::isInLeftQuadrant() - Code Metrics - Inspection of "Update and cleanup" - sixty-nine/php-data-types - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 16c7ba...d9867d )

by Dan

created 2018-10-07 23:03 UTC

QuadTree::isInLeftQuadrant() A

↳ Parent: QuadTree

Complexity

Conditions	2
Paths	2

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	3
CRAP Score	2

Importance

Changes

Metric	Value
dl	0
loc	5
ccs	3
cts	3
cp	1
rs	10
c	0
b	0
f	0
cc	2
nc	2
nop	1
crap	2

<?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 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	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 bool
64		*/
65	17	protected function isInTopQuadrant(Box $box)
66		{
67	17	$hMidpoint = $this->bounds->getCenter()->getY();
68	17	return $box->getY() <= $hMidpoint && $box->getY() + $box->getHeight() <= $hMidpoint;
69		}
70
71		/**
72		* @param Box $box
73		* @return bool
74		*/
75	17	protected function isInBottomQuadrant(Box $box)
76		{
77	17	$hMidpoint = $this->bounds->getCenter()->getY();
78	17	return $box->getY() >= $hMidpoint;
79		}
80
81		/**
82		* @param Box $box
83		* @return bool
84		*/
85	17	protected function isInLeftQuadrant(Box $box)
86		{
87	17	$vMidpoint = $this->bounds->getCenter()->getX();
88	17	return $box->getX() <= $vMidpoint && $box->getX() + $box->getWidth() <= $vMidpoint;
89		}
90
91		/**
92		* @param Box $box
93		* @return bool
94		*/
95	17	protected function isInRightQuadrant(Box $box)
96		{
97	17	$vMidpoint = $this->bounds->getCenter()->getX();
98	17	return $box->getX() >= $vMidpoint;
99		}
100
101		/**
102		* @param Box $box
103		* @return int
104		*/
105	17	public function getIndex(Box $box)
106		{
107	17	$topQuadrant = $this->isInTopQuadrant($box);
108	17	$bottomQuadrant = $this->isInBottomQuadrant($box);
109	17	$leftQuadrant = $this->isInLeftQuadrant($box);
110	17	$rightQuadrant = $this->isInRightQuadrant($box);
111
112		switch (true) {
113	17	case $leftQuadrant && $topQuadrant:
114	8	return self::Q_TOP_LEFT;
115	15	case $rightQuadrant && $topQuadrant:
116	7	return self::Q_TOP_RIGHT;
117	13	case $leftQuadrant && $bottomQuadrant:
118	8	return self::Q_BOTTOM_LEFT;
119	11	case $rightQuadrant && $bottomQuadrant:
120	7	return self::Q_BOTTOM_RIGHT;
121		}
122
123	7	return -1;
124		}
125
126		/**
127		* @param Box $box
128		*/
129	7	public function insert(Box $box)
130		{
131	7	if ($this->isSplit) {
132	5	$index = $this->getIndex($box);
133	5	if ($index !== -1) {
134		/** @var QuadTree $node */
135	5	$node = $this->nodes[$index];
136	5	$node->insert($box);
137	5	return;
138		}
139		}
140
141	7	$this->objects->add($box);
142
143	7	if (count($this->objects) > $this->maxObjects && $this->level < $this->maxLevels) {
144	6	if (!$this->isSplit) {
145	6	$this->split();
146		}
147
148	6	foreach ($this->objects as $object) {
149	6	$index = $this->getIndex($object);
150	6	if ($index !== -1) {
151	6	$this->objects->removeElement($object);
152		/** @var QuadTree $node */
153	6	$node = $this->nodes[$index];
154	6	$node->insert($object);
155		}
156		}
157		}
158	7	}
159
160		/**
161		* @return int
162		*/
163	3	public function count()
164		{
165	3	$count = $this->objects->count();
166
167	3	if ($this->isSplit) {
168		/** @var QuadTree $node */
169	1	foreach ($this->nodes as $node) {
170	1	$count += $node->count();
171		}
172		}
173
174	3	return $count;
175		}
176
177		/**
178		* @param Box $box
179		* @return array
180		*/
181	2	public function retrieve(Box $box)
182		{
183	2	$return = array();
184
185	2	if (!$this->bounds->intersects($box, false)) {
186	1	return array();
187		}
188
189		/** @var Box $object */
190	2	foreach ($this->objects as $object) {
191	2	if ($object->intersects($box, false)) {
192	2	$return[] = $object;
193		}
194		}
195
196	2	if ($this->isSplit) {
197		/** @var QuadTree $node */
198	2	foreach ($this->nodes as $node) {
199	2	$return = array_merge($return, $node->retrieve($box));
200		}
201		}
202
203	2	return $return;
204		}
205
206		/**
207		* @param Box $box
208		* @return bool
209		*/
210	2	public function collides(Box $box)
211		{
212	2	foreach ($this->objects as $object) {
213	2	if ($box->intersects($object)) {
214	2	return true;
215		}
216		}
217
218	2	if ($this->isSplit) {
219
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

Push — master ( 16c7ba...d9867d )

QuadTree::isInLeftQuadrant() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like