NearestSearch::searchNearest() - Code Metrics - hexogen/kdtree - Measure and Improve Code Quality continuously with Scrutinizer

NearestSearch::searchNearest() A
last analyzed 2024-09-15 21:17 UTC

↳ Parent: NearestSearch

Complexity

Conditions	5
Paths	5

Size

Total Lines	54
Code Lines	37

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	20
CRAP Score	5

Importance

Changes	1
Bugs	0	Features	1

Metric	Value
eloc	37
c	1
b	0
f	1
dl	0
loc	54
ccs	20
cts	20
cp	1
rs	9.0168
cc	5
nc	5
nop	6
crap	5

How to fix Long Method

<?php

namespace Hexogen\KDTree;

use Hexogen\KDTree\Exception\ValidationException;
use Hexogen\KDTree\Interfaces\ItemInterface;
use Hexogen\KDTree\Interfaces\NodeInterface;
use Hexogen\KDTree\Interfaces\PointInterface;
use Hexogen\KDTree\Interfaces\SearchAbstract;
use SplPriorityQueue;

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

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

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

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

        $upperBound = $this->tree->getMaxBoundary();
        $lowerBound = $this->tree->getMinBoundary();
        $root = $this->tree->getRoot();

        if ($root == null) {
            return [];
        }

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

hexogen / kdtree

NearestSearch::searchNearest() A last analyzed 2024-09-15 21:17 UTC

Complexity

Size

Duplication

Code Coverage

Importance

How to fix Long Method

Long Method

Duplication Side-by-Side

Filter issues like

NearestSearch::searchNearest() A
last analyzed 2024-09-15 21:17 UTC