hexogen/kdtree

file system KDTree index

K-D Tree

[![Build Status][ico-tests]][link-tests] ![Software License][ico-license] , _(*1)

PHP multidimensional K-D Tree implementation., _(*2)

To receive all benefits from K-D Tree, use file system implementation(FSKDTree). FSKDTree stores tree in binary format and uses lazy loading while traversing through nodes. Current approach provides much higher performance compared to deserialization., _(*3)

Install

Via Composer, _(*4)

``` bash $ composer require hexogen/kdtree, <sub>(*5)</sub>

## Usage

### Tree creation
``` php
//Item container with 2 dimensional points
$itemList = new ItemList(2);

//Adding 2 - dimension items to the list
$itemList->addItem(new Item(1, [1.2, 4.3]));
$itemList->addItem(new Item(2, [1.3, 3.4]));
$itemList->addItem(new Item(3, [4.5, 1.2]));
$itemList->addItem(new Item(4, [5.2, 3.5]));
$itemList->addItem(new Item(5, [2.1, 3.6]));

//Building tree with given item list
$tree = new KDTree($itemList);

Searching nearest items to the given point

``` php //Creating search engine with custom algorithm (currently Nearest Search) $searcher = new NearestSearch($tree);, <sub>(*6)</sub>

//Retrieving a result ItemInterface[] array with given size (currently 2) $result = $searcher->search(new Point([1.25, 3.5]), 2);, <sub>(*7)</sub>

echo $result[0]->getId(); // 2 echo $result[0]->getNthDimension(0); // 1.3 echo $result[0]->getNthDimension(1); // 3.4, <sub>(*8)</sub>

echo $result[1]->getId(); // 1 echo $result[1]->getNthDimension(0); // 1.2 echo $result[1]->getNthDimension(1); // 4.3, <sub>(*9)</sub>

### Persist tree to a binary file

``` php
//Init tree writer
$persister = new FSTreePersister('/path/to/dir');

//Save the tree to /path/to/dir/treeName.bin
$persister->convert($tree, 'treeName.bin');

File system version of the tree

``` php //ItemInterface factory $itemFactory = new ItemFactory();, <sub>(*10)</sub>

//Then init new instance of file system version of the tree $fsTree = new FSKDTree('/path/to/dir/treeName.bin', $itemFactory);, <sub>(*11)</sub>

//Now use fs kdtree to search $fsSearcher = new NearestSearch($fsTree);, <sub>(*12)</sub>

//Retrieving a result ItemInterface[] array with given size (currently 2) $result = $fsSearcher->search(new Point([1.25, 3.5]), 2);, <sub>(*13)</sub>

echo $result[0]->getId(); // 2 echo $result[1]->getId(); // 1, <sub>(*14)</sub>

## Change log

Please see [CHANGELOG](CHANGELOG.md) for more information on what has changed recently.

## Testing

``` bash
$ composer test

Contributing

Please see CONTRIBUTING and CONDUCT for details., <sub>(*15)</sub>

Security

If you discover any security related issues, please email volodymyrbas@gmail.com instead of using the issue tracker., <sub>(*16)</sub>

Credits

• Volodymyr Basarab
• All Contributors

License

The MIT License (MIT). Please see License File for more information., <sub>(*17)</sub>