QuadTree::getIndex() - Code Metrics - Inspection of "Fixed the precise mask, Resolve: #4" - sixty-nine/php-cloud-lib - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 81b80f...db2b61 )

by Dan

created 2017-04-06 14:59 UTC

QuadTree::getIndex() D

↳ Parent: QuadTree

Complexity

Conditions	9
Paths	28

Size

Total Lines	27
Code Lines	18

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	18
CRAP Score	9

Importance

Changes

Metric	Value
dl	0
loc	27
ccs	18
cts	18
cp	1
rs	4.909
c	0
b	0
f	0
cc	9
eloc	18
nc	28
nop	1
crap	9

<?php

namespace SixtyNine\Cloud\Model;

use Doctrine\Common\Collections\ArrayCollection;

class QuadTree
{
    const MAX_OBJECTS = 10;
    const MAX_LEVELS = 10;

    protected $level;
    protected $objects;
    protected $bounds;
    protected $isSplited = false;
    /** @var array QuadTree[] */
    protected $nodes;

    public function __construct(Box $bounds, $level = 0)
    {
        $this->level = $level;
        $this->objects = new ArrayCollection();
        $this->bounds = $bounds;
    }

    public function split()
    {
        $this->isSplited = true;

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

        $this->nodes = array();
        $this->nodes[0] = new Quadtree(new Box($x, $y, $subWidth, $subHeight), $this->level + 1);
        $this->nodes[1] = new Quadtree(new Box($x + $subWidth, $y, $subWidth, $subHeight), $this->level + 1);
        $this->nodes[2] = new Quadtree(new Box($x, $y + $subHeight, $subWidth, $subHeight), $this->level + 1);
        $this->nodes[3] = new Quadtree(new Box($x + $subWidth, $y + $subHeight, $subWidth, $subHeight), $this->level + 1);
    }

    public function getIndex(Box $box)
    {
        $vMidpoint = $this->bounds->getX() + ($this->bounds->getWidth() / 2);
        $hMidpoint = $this->bounds->getY() + ($this->bounds->getHeight() / 2);

        $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;

        // Object can completely fit within the left quadrants
        if ($leftQuadrant) {
            if ($topQuadrant) {
                return 0;
            } else if ($bottomQuadrant) {
                return 2;
            }
        } else if ($rightQuadrant) {
            if ($topQuadrant) {
                return 1;
            } else if ($bottomQuadrant) {
                return 3;
            }
        }

        return -1;
    }

    public function insert(Box $box)
    {
        if ($this->isSplited) {
            $index = $this->getIndex($box);
            if ($index !== -1) {
                $this->nodes[$index]->insert($box);
                return;
            }
        }

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

        if (count($this->objects) > self::MAX_OBJECTS && $this->level < self::MAX_LEVELS) {
            if (!$this->isSplited) {
                $this->split();
            }

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

    public function count()
    {
        $count = $this->objects->count();

        if ($this->isSplited) {
            foreach ($this->nodes as $node) {
                $count += $node->count();
            }
        }

        return $count;
    }

    public function retrieve(Box $box)
    {
        $return = array();
        $index = $this->getIndex($box);

        if ($index !== -1 && $this->isSplited) {
            $return = array_merge($return, $this->nodes[$index]->retrieve($box));
        }

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

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

        if ($this->isSplited) {

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

        return false;
    }

    public function __toString()
    {
        $padding = str_repeat('  ', $this->level);
        $res = sprintf(
            '%sQuadTree, level: %s, bounds: %s, objects: %s',
            $padding,
            $this->level,
            $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 . PHP_EOL;
    }

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

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

        if ($this->isSplited) {
            foreach ($this->nodes as $node) {
                $return = array_merge($return, $node->getAllObjects());
            }
        }

        return $return;
    }
}


1		<?php
2
3		namespace SixtyNine\Cloud\Model;
4
5		use Doctrine\Common\Collections\ArrayCollection;
6
7		class QuadTree
8		{
9		const MAX_OBJECTS = 10;
10		const MAX_LEVELS = 10;
11
12		protected $level;
13		protected $objects;
14		protected $bounds;
15		protected $isSplited = false;
16		/** @var array QuadTree[] */
17		protected $nodes;
18
19	23	public function __construct(Box $bounds, $level = 0)
20		{
21	23	$this->level = $level;
22	23	$this->objects = new ArrayCollection();
23	23	$this->bounds = $bounds;
24	23	}
25
26	6	public function split()
27		{
28	6	$this->isSplited = true;
29
30	6	$subWidth = (int)($this->bounds->getWidth() / 2);
31	6	$subHeight = (int)($this->bounds->getHeight() / 2);
32	6	$x = (int)$this->bounds->getX();
33	6	$y = (int)$this->bounds->getY();
34
35	6	$this->nodes = array();
36	6	$this->nodes[0] = new Quadtree(new Box($x, $y, $subWidth, $subHeight), $this->level + 1);
37	6	$this->nodes[1] = new Quadtree(new Box($x + $subWidth, $y, $subWidth, $subHeight), $this->level + 1);
38	6	$this->nodes[2] = new Quadtree(new Box($x, $y + $subHeight, $subWidth, $subHeight), $this->level + 1);
39	6	$this->nodes[3] = new Quadtree(new Box($x + $subWidth, $y + $subHeight, $subWidth, $subHeight), $this->level + 1);
40	6	}
41
42	16	public function getIndex(Box $box)
43		{
44	16	$vMidpoint = $this->bounds->getX() + ($this->bounds->getWidth() / 2);
45	16	$hMidpoint = $this->bounds->getY() + ($this->bounds->getHeight() / 2);
46
47	16	$topQuadrant = ($box->getY() <= $hMidpoint && $box->getY() + $box->getHeight() <= $hMidpoint);
48	16	$bottomQuadrant = ($box->getY() >= $hMidpoint);
49	16	$leftQuadrant = $box->getX() <= $vMidpoint && $box->getX() + $box->getWidth() <= $vMidpoint;
50	16	$rightQuadrant = $box->getX() >= $vMidpoint;
51
52		// Object can completely fit within the left quadrants
53	16	if ($leftQuadrant) {
54	9	if ($topQuadrant) {
55	7	return 0;
56	7	} else if ($bottomQuadrant) {
57	7	return 2;
58		}
59	11	} else if ($rightQuadrant) {
60	8	if ($topQuadrant) {
61	6	return 1;
62	6	} else if ($bottomQuadrant) {
63	6	return 3;
64		}
65		}
66
67	7	return -1;
68		}
69
70	10	public function insert(Box $box)
71		{
72	10	if ($this->isSplited) {
73	4	$index = $this->getIndex($box);
74	4	if ($index !== -1) {
75	4	$this->nodes[$index]->insert($box);
76	4	return;
77		}
78		}
79
80	10	$this->objects->add($box);
81
82	10	if (count($this->objects) > self::MAX_OBJECTS && $this->level < self::MAX_LEVELS) {
83	5	if (!$this->isSplited) {
84	5	$this->split();
85		}
86
87	5	foreach ($this->objects as $object) {
88	5	$index = $this->getIndex($object);
89	5	if ($index !== -1) {
90	5	$this->objects->removeElement($object);
91	5	$this->nodes[$index]->insert($object);
92		}
93		}
94		}
95	10	}
96
97	2	public function count()
98		{
99	2	$count = $this->objects->count();
100
101	2	if ($this->isSplited) {
102		foreach ($this->nodes as $node) {
103		$count += $node->count();
104		}
105		}
106
107	2	return $count;
108		}
109
110	1	public function retrieve(Box $box)
111		{
112	1	$return = array();
113	1	$index = $this->getIndex($box);
114
115	1	if ($index !== -1 && $this->isSplited) {
116	1	$return = array_merge($return, $this->nodes[$index]->retrieve($box));
117		}
118
119	1	$return = array_merge($return, $this->objects->toArray());
120	1	return $return;
121		}
122
123	8	public function collides(Box $box)
124		{
125	8	foreach ($this->objects as $object) {
126	8	if ($box->intersects($object)) {
127	8	return true;
128		}
129		}
130
131	8	if ($this->isSplited) {
132
133	3	$index = $this->getIndex($box);
134	3	$nodes = (-1 === $index) ? $this->nodes : array($this->nodes[$index]);
135	3	foreach ($nodes as $node) {
136	3	if ($node->collides($box)) {
137	3	return true;
138		}
139		}
140		}
141
142	8	return false;
143		}
144
145		public function __toString()
146		{
147		$padding = str_repeat(' ', $this->level);
148		$res = sprintf(
149		'%sQuadTree, level: %s, bounds: %s, objects: %s',
150		$padding,
151		$this->level,
152		$this->bounds,
153		$this->objects->count()
154		);
155
156		foreach ($this->objects as $box) {
157		$res .= PHP_EOL . $padding . ' - ' . (string)$box;
158		}
159
160		if (null !== $this->nodes) {
161		foreach ($this->nodes as $node) {
162		$res .= PHP_EOL . (string)$node;
163		}
164		}
165
166		return $res . PHP_EOL;
167		}
168
169		/**
170		* @return array
171		*/
172	2	public function getAllObjects()
173		{
174	2	$return = array();
175
176	2	$return = array_merge($return, $this->objects->toArray());
177
178	2	if ($this->isSplited) {
179	1	foreach ($this->nodes as $node) {
180	1	$return = array_merge($return, $node->getAllObjects());
181		}
182		}
183
184	2	return $return;
185		}
186		}
187

sixty-nine / php-cloud-lib

Push — master ( 81b80f...db2b61 )

QuadTree::getIndex() D

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like