f1r3starter/kdtree

另一种 K-d 树实现

维护者

详细信息

github.com/f1r3starter/kdtree

源代码

问题

安装: 42

依赖: 0

建议: 0

安全: 0

星标: 1

关注者: 3

分支: 0

开放问题: 0

v0.4 2019-12-30 18:46 UTC

Requires

  • php: >=7.2.0

Requires (Dev)

MIT fa4bacd1efc376bdd7c4bf4ba2ee89f364355fc8

  • Andrii Filenko <andrey.filenochko.woop@gmail.com>

This package is auto-updated.

Last update: 2024-09-23 05:36:12 UTC

README

CircleCI codecov Scrutinizer Code Quality

这是一个基于普林斯顿大学 K-D 树作业 的 PHP 中 K-D 树的基本实现，同时也是在 Projector 的算法课程中的毕业项目。

安装

composer require f1r3starter/kdtree

使用

树构建

首先，您需要决定树将使用多少维度，然后您可以添加一些点

<?php

use KDTree\Structure\KDTree;  
use KDTree\ValueObject\Point;

$kdTree = new KDTree(2); // 2 for two-dimensional points, eg cities
$kdTree->put(new Point(35.0844, 106.6504)); 
$kdTree->put(new Point(41.2865, 174.7762));

// if you need somehow connect point to your application, you can use setName method
$point = new Point(46.8117, 33.4902);
$point->setName('Kakhovka');
$kdTree->put($point);
//...
$points = $kdTree->points(); // returns list of all points, which can be iterated through

$kdTree->contains(new Point(46.8117, 33.4902)); // will return "true"

最近点搜索

在树构建完成后，我们可以尝试找到最近点

<?php

use KDTree\Search\NearestSearch;
use KDTree\ValueObject\Point;

$search = new NearestSearch($kdTree);
$nearestPoint = $search->nearest((new Point(41.2865, 174.7762)));

范围搜索

同时，也可以找到某些特定范围内的点，这些点应该在 K-D 树的 k 维度中。

<?php

use KDTree\Structure\PointsList;
use KDTree\Search\PartitionSearch;
use KDTree\ValueObject\{Partition, Point};

$pointsList = new PointsList(2);  
$pointsList->addPoint(new Point(46.8117, 33.4902));  
$pointsList->addPoint(new Point(31.3142, 42.5245));  
$pointsList->addPoint(new Point(22.2525, 41.3412));  
$pointsList->addPoint(new Point(55.4245, 52.5134));  

$search = new PartitionSearch($kdTree);  
$foundPoints = $search->find(new Partition($pointsList));

演示

演示可在 此存储库 中找到。

致谢