QuadTree::insert() - Code Metrics - Inspection of "Introduce the class Drawer" - sixty-nine/php-cloud-lib - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Pull Request — master (#5)

by Dan

created 2017-04-05 13:03 UTC

QuadTree::insert() C

↳ Parent: QuadTree

Complexity

Conditions	8
Paths	15

Size

Total Lines	26
Code Lines	15

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	16
CRAP Score	8

Importance

Changes

Metric	Value
dl	0
loc	26
ccs	16
cts	16
cp	1
rs	5.3846
c	0
b	0
f	0
cc	8
eloc	15
nc	15
nop	1
crap	8

<?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	22	public function __construct(Box $bounds, $level = 0)
20		{
21	22	$this->level = $level;
22	22	$this->objects = new ArrayCollection();
23	22	$this->bounds = $bounds;
24	22	}
25
26	5	public function split()
27		{
28	5	$this->isSplited = true;
29
30	5	$subWidth = (int)($this->bounds->getWidth() / 2);
31	5	$subHeight = (int)($this->bounds->getHeight() / 2);
32	5	$x = (int)$this->bounds->getX();
33	5	$y = (int)$this->bounds->getY();
34
35	5	$this->nodes = array();
36	5	$this->nodes[0] = new Quadtree(new Box($x, $y, $subWidth, $subHeight), $this->level + 1);
37	5	$this->nodes[1] = new Quadtree(new Box($x + $subWidth, $y, $subWidth, $subHeight), $this->level + 1);
38	5	$this->nodes[2] = new Quadtree(new Box($x, $y + $subHeight, $subWidth, $subHeight), $this->level + 1);
39	5	$this->nodes[3] = new Quadtree(new Box($x + $subWidth, $y + $subHeight, $subWidth, $subHeight), $this->level + 1);
40	5	}
41
42	15	public function getIndex(Box $box)
43		{
44	15	$vMidpoint = $this->bounds->getX() + ($this->bounds->getWidth() / 2);
45	15	$hMidpoint = $this->bounds->getY() + ($this->bounds->getHeight() / 2);
46
47	15	$topQuadrant = ($box->getY() <= $hMidpoint && $box->getY() + $box->getHeight() <= $hMidpoint);
48	15	$bottomQuadrant = ($box->getY() >= $hMidpoint);
49	15	$leftQuadrant = $box->getX() <= $vMidpoint && $box->getX() + $box->getWidth() <= $vMidpoint;
50	15	$rightQuadrant = $box->getX() >= $vMidpoint;
51
52		// Object can completely fit within the left quadrants
53	15	if ($leftQuadrant) {
54	8	if ($topQuadrant) {
55	6	return 0;
56	6	} else if ($bottomQuadrant) {
57	6	return 2;
58		}
59	10	} else if ($rightQuadrant) {
60	7	if ($topQuadrant) {
61	5	return 1;
62	5	} else if ($bottomQuadrant) {
63	5	return 3;
64		}
65		}
66
67	6	return -1;
68		}
69
70	9	public function insert(Box $box)
71		{
72	9	if ($this->isSplited) {
73	3	$index = $this->getIndex($box);
74	3	if ($index !== -1) {
75	3	$this->nodes[$index]->insert($box);
76	3	return;
77		}
78		}
79
80	9	$this->objects->add($box);
81
82	9	if (count($this->objects) > self::MAX_OBJECTS && $this->level < self::MAX_LEVELS) {
83	4	if (!$this->isSplited) {
84	4	$this->split();
85		}
86
87	4	foreach ($this->objects as $object) {
88	4	$index = $this->getIndex($object);
89	4	if ($index !== -1) {
90	4	$this->objects->removeElement($object);
91	4	$this->nodes[$index]->insert($object);
92		}
93		}
94		}
95	9	}
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	7	public function collides(Box $box)
124		{
125	7	foreach ($this->objects as $object) {
126	7	if ($box->intersects($object)) {
127	7	return true;
128		}
129		}
130
131	7	if ($this->isSplited) {
132
133	2	$index = $this->getIndex($box);
134	2	$nodes = (-1 === $index) ? $this->nodes : array($this->nodes[$index]);
135	2	foreach ($nodes as $node) {
136	2	if ($node->collides($box)) {
137	2	return true;
138		}
139		}
140		}
141
142	7	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	1	public function getAllObjects()
173		{
174	1	$return = array();
175
176	1	$return = array_merge($return, $this->objects->toArray());
177
178	1	if ($this->isSplited) {
179		foreach ($this->nodes as $node) {
180		$return = array_merge($return, $node->getAllObjects());
181		}
182		}
183
184	1	return $return;
185		}
186		}
187

sixty-nine / php-cloud-lib

Pull Request — master (#5)

QuadTree::insert() C

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like