NearestSearch::branchSearch() - Code Metrics - Inspection of "Search nearest alghrothm added" - hexogen/kdtree - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( c60dd0...055fc0 )

by Basarab

created 2016-12-27 12:38 UTC

NearestSearch::branchSearch() B

↳ Parent: NearestSearch

Complexity

Conditions	3
Paths	4

Size

Total Lines	36
Code Lines	24

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	13
CRAP Score	3

Importance

Changes

Metric	Value
dl	0
loc	36
ccs	13
cts	13
cp	1
rs	8.8571
c	0
b	0
f	0
cc	3
eloc	24
nc	4
nop	6
crap	3

<?php

namespace Hexogen\KDTree;

use Hexogen\KDTree\Exception\ValidationException;
use SplPriorityQueue;

class NearestSearch extends SearchAbstract
{
    /**
     * @var SplPriorityQueue
     */
    private $queue;

    /**
     * @var float
     */
    private $maxQueuedDistance;

    /**
     * @var Point
     */
    private $point;

    /**
     * Search items it the tree by given algorithm
     *
     * @param PointInterface $point
     * @param int $resultLength
     * @return ItemInterface[]
     */
    public function search(PointInterface $point, int $resultLength = 1) : array
    {
        $this->validatePoint($point);
        $this->point = $point;
class Alien {}

class Dalek extends Alien {}

class Plot
{
    /** @var  Dalek */
    public $villain;
}

$alien = new Alien();
$plot = new Plot();
if ($alien instanceof Dalek) {
    $plot->villain = $alien;
}

        $upperBound = $this->tree->getMaxBoundary();
        $lowerBound = $this->tree->getMinBoundary();
        $root = $this->tree->getRoot();
        
        /**
         * @var array orthogonal square distances to the point
         */
        $orthogonalDistances = $this->getOrthogonalDistances($point, $upperBound, $lowerBound);

        /**
         * @var float possible Euclidean distance
         */
        $possibleDistance = $this->getPossibleDistance($orthogonalDistances);

        $this->prepareQueue($resultLength);
        $this->searchNearest($root, 0, $upperBound, $lowerBound, $orthogonalDistances, $possibleDistance);

        return $this->getItemsFromQueue();
    }

    /**
     * Check that point has same number of dimensions that all items in the tree
     *
     * @param PointInterface $point
     * @throws ValidationException
     */
    private function validatePoint(PointInterface $point)
    {
        if ($point->getDimensionsCount() !== $this->tree->getDimensionCount()) {
            throw new ValidationException(
                'point dimensions count should be equal to ' . $this->tree->getDimensionCount()
            );
        }
    }

    /**
     * Get orthogonal distances array from the point to multidimensional space that holds all the items in the tree
     *
     * @param PointInterface $point
     * @param array $upperBound
     * @param array $lowerBound
     * @return array
     */
    private function getOrthogonalDistances(PointInterface $point, array $upperBound, array $lowerBound): array
    {
        $orthogonalDistances = [];

        for ($i = 0; $i < $this->dimensions; $i++) {
            $coordinate = $point->getNthDimension($i);
            $orthogonalDistances[$i] = $this->getPossibleOrthogonalDistance(
                $coordinate,
                $upperBound[$i],
                $lowerBound[$i]
            );
        }
        return $orthogonalDistances;
    }

    /**
     * Calculate minimal possible Euclidean distance from the point to an item
     *
     * @param $orthogonalDistances
     * @return int
     */
    private function getPossibleDistance(array $orthogonalDistances) : int
    {
        $possibleDistance = 0.;
        foreach ($orthogonalDistances as $orthogonalDistance) {
            $possibleDistance += $orthogonalDistance;
        }

        return $possibleDistance;
    }

    /**
     * Prepare queue for collecting nearest items.
     * Queue size sets to be equal to result length or to tree size,
     * if request result length is bigger then tree size
     *
     * @param int $resultLength
     * @return SplPriorityQueue
     */
    private function prepareQueue(int $resultLength)
    {
        $this->queue = new SplPriorityQueue();
        $this->queue->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);

        $itemsInTree = $this->tree->getItemCount();

        if ($itemsInTree < $resultLength) {
            $resultLength = $itemsInTree;
        }

        for ($i = 0; $i < $resultLength; $i++) {
            $this->queue->insert(null, INF);
        }

        $this->maxQueuedDistance = INF;
    }

    /**
     * Add an item to the queue if distance to the point is less than max queued,
     * after it removes an item with the biggest distance, to keep queue size constant
     *
     * @param ItemInterface $item
     * @param float $distance
     */
    private function addToQueue(ItemInterface $item, float $distance)
    {
        if ($distance >= $this->maxQueuedDistance) {
            return;
        }

        $this->queue->insert($item, $distance);
        $this->queue->extract();

        $this->maxQueuedDistance = $this->queue->current();
    }

    /**
     * Calculate Euclidean distance between point and item
     *
     * @param ItemInterface $item
     * @param PointInterface $point
     * @return float
     */
    private function calculateDistance(ItemInterface $item, PointInterface $point) : float
    {
        $distance = 0.;
        for ($i = 0; $i < $this->dimensions; $i++) {
            $distance += pow($item->getNthDimension($i) - $point->getNthDimension($i), 2);
        }
        return $distance;
    }

    /**
     * Recursive search of N closest item in the tree to the given point
     *
     * @param NodeInterface $node
     * @param int $dimension
     * @param array $upperBound
     * @param array $lowerBound
     * @param array $orthogonalDistances
     * @param float $possibleDistance
     */
    private function searchNearest(
        NodeInterface $node,
        int $dimension,
        array $upperBound,
        array $lowerBound,
        array $orthogonalDistances,
        float $possibleDistance
    ) {
        $item = $node->getItem();
        $distance = $this->calculateDistance($item, $this->point);
        $this->addToQueue($item, $distance);

        $rightLowerBound = $lowerBound;
        $leftUpperBound = $upperBound;
        $rightLowerBound[$dimension] = $item->getNthDimension($dimension);
        $leftUpperBound[$dimension] = $item->getNthDimension($dimension);

        $rightNode = $node->getRight();
        $leftNode = $node->getLeft();

        if ($rightNode && $leftNode) {
            $this->smartBranchesSearch(
                $rightNode,
                $leftNode,
                $dimension,
                $upperBound,
                $rightLowerBound,
                $leftUpperBound,
                $lowerBound,
                $orthogonalDistances,
                $possibleDistance
            );
            return;
        }

        if ($rightNode) {
            $this->branchSearch(
                $rightNode,
                $dimension,
                $upperBound,
                $rightLowerBound,
                $orthogonalDistances,
                $possibleDistance
            );
        }

        if ($leftNode) {
            $this->branchSearch(
                $leftNode,
                $dimension,
                $leftUpperBound,
                $lowerBound,
                $orthogonalDistances,
                $possibleDistance
            );
        }
    }

    /**
     * Get Euclidean distance between point and an item in given dimension
     *
     * @param $pointCoordinate
     * @param $upperBound
     * @param $lowerBound
     * @return float|number
     */
    private function getPossibleOrthogonalDistance($pointCoordinate, $upperBound, $lowerBound)
    {
        if ($pointCoordinate > $upperBound) {
            return pow($pointCoordinate - $upperBound, 2);
        } elseif ($pointCoordinate < $lowerBound) {
            return pow($lowerBound - $pointCoordinate, 2);
        }
        return 0.;
    }

    /**
     * Recursive search in the given branch
     *
     * @param NodeInterface $branchNode
     * @param int $dimension
     * @param array $upperBound
     * @param array $lowerBound
     * @param array $orthogonalDistances
     * @param float $possibleDistance
     */
    private function branchSearch(
        NodeInterface $branchNode,
        int $dimension,
        array $upperBound,
        array  $lowerBound,
        array $orthogonalDistances,
        float $possibleDistance
    ) {
    
        // possible orthogonal distances to the right node
        $branchOrthogonalDistances = $orthogonalDistances;
        $branchPossibleDistance = $possibleDistance;

        $nextDimension = ($dimension + 1) % $this->dimensions;

        $branchOrthogonalDistances[$dimension] = $this->getPossibleOrthogonalDistance(
            $this->point->getNthDimension($dimension),
            $upperBound[$dimension],
            $lowerBound[$dimension]
        );

        if ($orthogonalDistances[$dimension] != $branchOrthogonalDistances[$dimension]) {
            $branchPossibleDistance += $branchOrthogonalDistances[$dimension] - $orthogonalDistances[$dimension];
        }

        if ($branchPossibleDistance <= $this->maxQueuedDistance) {
            $this->searchNearest(
                $branchNode,
                $nextDimension,
                $upperBound,
                $lowerBound,
                $branchOrthogonalDistances,
                $branchPossibleDistance
            );
        }
    }

    /**
     * extract all items from queue
     */
    private function getItemsFromQueue() : array
    {
        $items = [];
        $this->queue->setExtractFlags(SplPriorityQueue::EXTR_DATA);

        while (!$this->queue->isEmpty()) {
            $items[] = $this->queue->extract();
        }

        return array_reverse($items);
    }

    /**
     * Nearest branch first approach
     *
     * @param NodeInterface $rightNode
     * @param NodeInterface $leftNode
     * @param int $dimension
     * @param array $upperBound
     * @param array $rightLowerBound
     * @param array $leftUpperBound
     * @param array $lowerBound
     * @param array $orthogonalDistances
     * @param float $possibleDistance
     */
    private function smartBranchesSearch(
        NodeInterface $rightNode,
        NodeInterface $leftNode,
        int $dimension,
        array $upperBound,
        array $rightLowerBound,
        array $leftUpperBound,
        array $lowerBound,
        array $orthogonalDistances,
        float $possibleDistance
    ) {
    
        // possible orthogonal distances to the right node
        $leftOrthogonalDistances = $rightOrthogonalDistances = $orthogonalDistances;
        $leftPossibleDistance = $rightPossibleDistance = $possibleDistance;

        $nextDimension = ($dimension + 1) % $this->dimensions;

        $leftOrthogonalDistances[$dimension] = $this->getPossibleOrthogonalDistance(
            $this->point->getNthDimension($dimension),
            $leftUpperBound[$dimension],
            $lowerBound[$dimension]
        );
        $rightOrthogonalDistances[$dimension] = $this->getPossibleOrthogonalDistance(
            $this->point->getNthDimension($dimension),
            $upperBound[$dimension],
            $rightLowerBound[$dimension]
        );

        if ($orthogonalDistances[$dimension] != $leftOrthogonalDistances[$dimension]) {
            $leftPossibleDistance += $leftOrthogonalDistances[$dimension] - $orthogonalDistances[$dimension];
        }

        if ($orthogonalDistances[$dimension] != $rightOrthogonalDistances[$dimension]) {
            $rightPossibleDistance += $rightOrthogonalDistances[$dimension] - $orthogonalDistances[$dimension];
        }

        if ($leftPossibleDistance < $rightPossibleDistance) {
            $this->prioritySearch(
                $leftNode,
                $rightNode,
                $leftUpperBound,
                $lowerBound,
                $upperBound,
                $rightLowerBound,
                $leftOrthogonalDistances,
                $rightOrthogonalDistances,
                $leftPossibleDistance,
                $rightPossibleDistance,
                $nextDimension
            );
            return;
        }

        $this->prioritySearch(
            $rightNode,
            $leftNode,
            $upperBound,
            $rightLowerBound,
            $leftUpperBound,
            $lowerBound,
            $rightOrthogonalDistances,
            $leftOrthogonalDistances,
            $rightPossibleDistance,
            $leftPossibleDistance,
            $nextDimension
        );
    }

    public function prioritySearch(
        NodeInterface $firstNode,
        NodeInterface $secondNode,
        array $firstUpperBound,
        array $firstLowerBound,
        array $secondUpperBound,
        array $secondLowerBound,
        array $firstOrthogonalDistances,
        array $secondOrthogonalDistances,
        float $firstPossibleDistance,
        float $secondPossibleDistance,
        int $nextDimension
    ) {
    
        if ($firstPossibleDistance < $this->maxQueuedDistance) {
            $this->searchNearest(
                $firstNode,
                $nextDimension,
                $firstUpperBound,
                $firstLowerBound,
                $firstOrthogonalDistances,
                $firstPossibleDistance
            );
            if ($secondPossibleDistance < $this->maxQueuedDistance) {
                $this->searchNearest(
                    $secondNode,
                    $nextDimension,
                    $secondUpperBound,
                    $secondLowerBound,
                    $secondOrthogonalDistances,
                    $secondPossibleDistance
                );
            }
        }
    }
}


1		<?php
2
3		namespace Hexogen\KDTree;
4
5		use Hexogen\KDTree\Exception\ValidationException;
6		use SplPriorityQueue;
7
8		class NearestSearch extends SearchAbstract
9		{
10		/**
11		* @var SplPriorityQueue
12		*/
13		private $queue;
14
15		/**
16		* @var float
17		*/
18		private $maxQueuedDistance;
19
20		/**
21		* @var Point
22		*/
23		private $point;
24
25		/**
26		* Search items it the tree by given algorithm
27		*
28		* @param PointInterface $point
29		* @param int $resultLength
30		* @return ItemInterface[]
31		*/
32	39	public function search(PointInterface $point, int $resultLength = 1) : array
33		{
34	39	$this->validatePoint($point);
35	36	$this->point = $point;
		0 ignored issues – show Documentation Bug introduced 2016-12-27 12:42 UTC by Report Bug Copy Issue Report `$point` is of type `object<Hexogen\KDTree\PointInterface>`, but the property `$point` was declared to be of type `object<Hexogen\KDTree\Point>`. Are you sure that you always receive this specific sub-class here, or does it make sense to add an `instanceof` check? Our type inference engine has found a suspicous assignment of a value to a property. This check raises an issue when a value that can be of a given class or a super-class is assigned to a property that is type hinted more strictly. Either this assignment is in error or an instanceof check should be added for that assignment. class Alien {} class Dalek extends Alien {} class Plot { /** @var Dalek */ public $villain; } $alien = new Alien(); $plot = new Plot(); if ($alien instanceof Dalek) { $plot->villain = $alien; } Loading history...
36
37	36	$upperBound = $this->tree->getMaxBoundary();
38	36	$lowerBound = $this->tree->getMinBoundary();
39	36	$root = $this->tree->getRoot();
40
41		/**
42		* @var array orthogonal square distances to the point
43		*/
44	36	$orthogonalDistances = $this->getOrthogonalDistances($point, $upperBound, $lowerBound);
45
46		/**
47		* @var float possible Euclidean distance
48		*/
49	36	$possibleDistance = $this->getPossibleDistance($orthogonalDistances);
50
51	36	$this->prepareQueue($resultLength);
52	36	$this->searchNearest($root, 0, $upperBound, $lowerBound, $orthogonalDistances, $possibleDistance);
53
54	36	return $this->getItemsFromQueue();
55		}
56
57		/**
58		* Check that point has same number of dimensions that all items in the tree
59		*
60		* @param PointInterface $point
61		* @throws ValidationException
62		*/
63	39	private function validatePoint(PointInterface $point)
64		{
65	39	if ($point->getDimensionsCount() !== $this->tree->getDimensionCount()) {
66	3	throw new ValidationException(
67	3	'point dimensions count should be equal to ' . $this->tree->getDimensionCount()
68		);
69		}
70	36	}
71
72		/**
73		* Get orthogonal distances array from the point to multidimensional space that holds all the items in the tree
74		*
75		* @param PointInterface $point
76		* @param array $upperBound
77		* @param array $lowerBound
78		* @return array
79		*/
80	36	private function getOrthogonalDistances(PointInterface $point, array $upperBound, array $lowerBound): array
81		{
82	36	$orthogonalDistances = [];
83
84	36	for ($i = 0; $i < $this->dimensions; $i++) {
85	36	$coordinate = $point->getNthDimension($i);
86	36	$orthogonalDistances[$i] = $this->getPossibleOrthogonalDistance(
87		$coordinate,
88	36	$upperBound[$i],
89	36	$lowerBound[$i]
90		);
91		}
92	36	return $orthogonalDistances;
93		}
94
95		/**
96		* Calculate minimal possible Euclidean distance from the point to an item
97		*
98		* @param $orthogonalDistances
99		* @return int
100		*/
101	36	private function getPossibleDistance(array $orthogonalDistances) : int
102		{
103	36	$possibleDistance = 0.;
104	36	foreach ($orthogonalDistances as $orthogonalDistance) {
105	36	$possibleDistance += $orthogonalDistance;
106		}
107
108	36	return $possibleDistance;
109		}
110
111		/**
112		* Prepare queue for collecting nearest items.
113		* Queue size sets to be equal to result length or to tree size,
114		* if request result length is bigger then tree size
115		*
116		* @param int $resultLength
117		* @return SplPriorityQueue
118		*/
119	36	private function prepareQueue(int $resultLength)
120		{
121	36	$this->queue = new SplPriorityQueue();
122	36	$this->queue->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);
123
124	36	$itemsInTree = $this->tree->getItemCount();
125
126	36	if ($itemsInTree < $resultLength) {
127	18	$resultLength = $itemsInTree;
128		}
129
130	36	for ($i = 0; $i < $resultLength; $i++) {
131	36	$this->queue->insert(null, INF);
132		}
133
134	36	$this->maxQueuedDistance = INF;
135	36	}
136
137		/**
138		* Add an item to the queue if distance to the point is less than max queued,
139		* after it removes an item with the biggest distance, to keep queue size constant
140		*
141		* @param ItemInterface $item
142		* @param float $distance
143		*/
144	36	private function addToQueue(ItemInterface $item, float $distance)
145		{
146	36	if ($distance >= $this->maxQueuedDistance) {
147	30	return;
148		}
149
150	36	$this->queue->insert($item, $distance);
151	36	$this->queue->extract();
152
153	36	$this->maxQueuedDistance = $this->queue->current();
154	36	}
155
156		/**
157		* Calculate Euclidean distance between point and item
158		*
159		* @param ItemInterface $item
160		* @param PointInterface $point
161		* @return float
162		*/
163	36	private function calculateDistance(ItemInterface $item, PointInterface $point) : float
164		{
165	36	$distance = 0.;
166	36	for ($i = 0; $i < $this->dimensions; $i++) {
167	36	$distance += pow($item->getNthDimension($i) - $point->getNthDimension($i), 2);
168		}
169	36	return $distance;
170		}
171
172		/**
173		* Recursive search of N closest item in the tree to the given point
174		*
175		* @param NodeInterface $node
176		* @param int $dimension
177		* @param array $upperBound
178		* @param array $lowerBound
179		* @param array $orthogonalDistances
180		* @param float $possibleDistance
181		*/
182	36	private function searchNearest(
183		NodeInterface $node,
184		int $dimension,
185		array $upperBound,
186		array $lowerBound,
187		array $orthogonalDistances,
188		float $possibleDistance
189		) {
190	36	$item = $node->getItem();
191	36	$distance = $this->calculateDistance($item, $this->point);
192	36	$this->addToQueue($item, $distance);
193
194	36	$rightLowerBound = $lowerBound;
195	36	$leftUpperBound = $upperBound;
196	36	$rightLowerBound[$dimension] = $item->getNthDimension($dimension);
197	36	$leftUpperBound[$dimension] = $item->getNthDimension($dimension);
198
199	36	$rightNode = $node->getRight();
200	36	$leftNode = $node->getLeft();
201
202	36	if ($rightNode && $leftNode) {
203	30	$this->smartBranchesSearch(
204		$rightNode,
205		$leftNode,
206		$dimension,
207		$upperBound,
208		$rightLowerBound,
209		$leftUpperBound,
210		$lowerBound,
211		$orthogonalDistances,
212		$possibleDistance
213		);
214	30	return;
215		}
216
217	36	if ($rightNode) {
218	27	$this->branchSearch(
219		$rightNode,
220		$dimension,
221		$upperBound,
222		$rightLowerBound,
223		$orthogonalDistances,
224		$possibleDistance
225		);
226		}
227
228	36	if ($leftNode) {
229	3	$this->branchSearch(
230		$leftNode,
231		$dimension,
232		$leftUpperBound,
233		$lowerBound,
234		$orthogonalDistances,
235		$possibleDistance
236		);
237		}
238	36	}
239
240		/**
241		* Get Euclidean distance between point and an item in given dimension
242		*
243		* @param $pointCoordinate
244		* @param $upperBound
245		* @param $lowerBound
246		* @return float\|number
247		*/
248	36	private function getPossibleOrthogonalDistance($pointCoordinate, $upperBound, $lowerBound)
249		{
250	36	if ($pointCoordinate > $upperBound) {
251	33	return pow($pointCoordinate - $upperBound, 2);
252	36	} elseif ($pointCoordinate < $lowerBound) {
253	36	return pow($lowerBound - $pointCoordinate, 2);
254		}
255	30	return 0.;
256		}
257
258		/**
259		* Recursive search in the given branch
260		*
261		* @param NodeInterface $branchNode
262		* @param int $dimension
263		* @param array $upperBound
264		* @param array $lowerBound
265		* @param array $orthogonalDistances
266		* @param float $possibleDistance
267		*/
268	30	private function branchSearch(
269		NodeInterface $branchNode,
270		int $dimension,
271		array $upperBound,
272		array $lowerBound,
273		array $orthogonalDistances,
274		float $possibleDistance
275		) {
276
277		// possible orthogonal distances to the right node
278	30	$branchOrthogonalDistances = $orthogonalDistances;
279	30	$branchPossibleDistance = $possibleDistance;
280
281	30	$nextDimension = ($dimension + 1) % $this->dimensions;
282
283	30	$branchOrthogonalDistances[$dimension] = $this->getPossibleOrthogonalDistance(
284	30	$this->point->getNthDimension($dimension),
285	30	$upperBound[$dimension],
286	30	$lowerBound[$dimension]
287		);
288
289	30	if ($orthogonalDistances[$dimension] != $branchOrthogonalDistances[$dimension]) {
290	27	$branchPossibleDistance += $branchOrthogonalDistances[$dimension] - $orthogonalDistances[$dimension];
291		}
292
293	30	if ($branchPossibleDistance <= $this->maxQueuedDistance) {
294	30	$this->searchNearest(
295		$branchNode,
296		$nextDimension,
297		$upperBound,
298		$lowerBound,
299		$branchOrthogonalDistances,
300		$branchPossibleDistance
301		);
302		}
303	30	}
304
305		/**
306		* extract all items from queue
307		*/
308	36	private function getItemsFromQueue() : array
309		{
310	36	$items = [];
311	36	$this->queue->setExtractFlags(SplPriorityQueue::EXTR_DATA);
312
313	36	while (!$this->queue->isEmpty()) {
314	36	$items[] = $this->queue->extract();
315		}
316
317	36	return array_reverse($items);
318		}
319
320		/**
321		* Nearest branch first approach
322		*
323		* @param NodeInterface $rightNode
324		* @param NodeInterface $leftNode
325		* @param int $dimension
326		* @param array $upperBound
327		* @param array $rightLowerBound
328		* @param array $leftUpperBound
329		* @param array $lowerBound
330		* @param array $orthogonalDistances
331		* @param float $possibleDistance
332		*/
333	30	private function smartBranchesSearch(
334		NodeInterface $rightNode,
335		NodeInterface $leftNode,
336		int $dimension,
337		array $upperBound,
338		array $rightLowerBound,
339		array $leftUpperBound,
340		array $lowerBound,
341		array $orthogonalDistances,
342		float $possibleDistance
343		) {
344
345		// possible orthogonal distances to the right node
346	30	$leftOrthogonalDistances = $rightOrthogonalDistances = $orthogonalDistances;
347	30	$leftPossibleDistance = $rightPossibleDistance = $possibleDistance;
348
349	30	$nextDimension = ($dimension + 1) % $this->dimensions;
350
351	30	$leftOrthogonalDistances[$dimension] = $this->getPossibleOrthogonalDistance(
352	30	$this->point->getNthDimension($dimension),
353	30	$leftUpperBound[$dimension],
354	30	$lowerBound[$dimension]
355		);
356	30	$rightOrthogonalDistances[$dimension] = $this->getPossibleOrthogonalDistance(
357	30	$this->point->getNthDimension($dimension),
358	30	$upperBound[$dimension],
359	30	$rightLowerBound[$dimension]
360		);
361
362	30	if ($orthogonalDistances[$dimension] != $leftOrthogonalDistances[$dimension]) {
363	30	$leftPossibleDistance += $leftOrthogonalDistances[$dimension] - $orthogonalDistances[$dimension];
364		}
365
366	30	if ($orthogonalDistances[$dimension] != $rightOrthogonalDistances[$dimension]) {
367	30	$rightPossibleDistance += $rightOrthogonalDistances[$dimension] - $orthogonalDistances[$dimension];
368		}
369
370	30	if ($leftPossibleDistance < $rightPossibleDistance) {
371	30	$this->prioritySearch(
372		$leftNode,
373		$rightNode,
374		$leftUpperBound,
375		$lowerBound,
376		$upperBound,
377		$rightLowerBound,
378		$leftOrthogonalDistances,
379		$rightOrthogonalDistances,
380		$leftPossibleDistance,
381		$rightPossibleDistance,
382		$nextDimension
383		);
384	30	return;
385		}
386
387	30	$this->prioritySearch(
388		$rightNode,
389		$leftNode,
390		$upperBound,
391		$rightLowerBound,
392		$leftUpperBound,
393		$lowerBound,
394		$rightOrthogonalDistances,
395		$leftOrthogonalDistances,
396		$rightPossibleDistance,
397		$leftPossibleDistance,
398		$nextDimension
399		);
400	30	}
401
402	30	public function prioritySearch(
403		NodeInterface $firstNode,
404		NodeInterface $secondNode,
405		array $firstUpperBound,
406		array $firstLowerBound,
407		array $secondUpperBound,
408		array $secondLowerBound,
409		array $firstOrthogonalDistances,
410		array $secondOrthogonalDistances,
411		float $firstPossibleDistance,
412		float $secondPossibleDistance,
413		int $nextDimension
414		) {
415
416	30	if ($firstPossibleDistance < $this->maxQueuedDistance) {
417	30	$this->searchNearest(
418		$firstNode,
419		$nextDimension,
420		$firstUpperBound,
421		$firstLowerBound,
422		$firstOrthogonalDistances,
423		$firstPossibleDistance
424		);
425	30	if ($secondPossibleDistance < $this->maxQueuedDistance) {
426	30	$this->searchNearest(
427		$secondNode,
428		$nextDimension,
429		$secondUpperBound,
430		$secondLowerBound,
431		$secondOrthogonalDistances,
432		$secondPossibleDistance
433		);
434		}
435		}
436	30	}
437		}
438

hexogen / kdtree

Push — master ( c60dd0...055fc0 )

NearestSearch::branchSearch() B

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like