README

PHP 多维 K-D 树实现。

要获得 K-D 树的所有好处，请使用文件系统实现（FSKDTree）。FSKDTree 以二进制格式存储树，并在遍历节点时使用延迟加载。当前方法与反序列化相比提供了更高的性能。

安装

通过 Composer

$ composer require hexogen/kdtree

用法

创建树

//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);

搜索给定点的最近项

//Creating search engine with custom algorithm (currently Nearest Search)
$searcher = new NearestSearch($tree);

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

echo $result[0]->getId(); // 2
echo $result[0]->getNthDimension(0); // 1.3
echo $result[0]->getNthDimension(1); // 3.4

echo $result[1]->getId(); // 1
echo $result[1]->getNthDimension(0); // 1.2
echo $result[1]->getNthDimension(1); // 4.3

将树持久化到二进制文件

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

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

树的文件系统版本

//ItemInterface factory
$itemFactory = new ItemFactory();

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

//Now use fs kdtree to search
$fsSearcher = new NearestSearch($fsTree);

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

echo $result[0]->getId(); // 2
echo $result[1]->getId(); // 1

变更日志

有关最近变更的更多信息，请参阅 CHANGELOG。

测试

$ composer test

贡献

有关详细信息，请参阅 CONTRIBUTING 和 CONDUCT。

安全

如果您发现任何与安全相关的问题，请通过电子邮件 volodymyrbas@gmail.com 联系，而不是使用问题跟踪器。

鸣谢

• Volodymyr Basarab
• 所有贡献者

许可证

MIT 许可证（MIT）。有关更多信息，请参阅 许可证文件。