在golang中实现KDTREE 的 queryBallPoint方法

本文主要是介绍在golang中实现KDTREE 的 queryBallPoint方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近工作中遇到用go重写kdtree的需求，上github上查了下，发现go的算法库是真心烂。star最高的kyroy/kdtree库，没有queryBallPoint方法，没办法，自己加一个

拉取源码

go get github.com/kyroy/kdtree

queryBallPoint 函数

queryBallPoint 函数的目标是查找从目标点到一定距离内的所有点。常见的用法是在圆形（在 2D 中）内搜索半径范围内的点。

talk less show me the code 下面上代码，修改 kdtree.go

// QueryBallPoint returns all points within distance r from a given point x in the KDTree.
func (t *KDTree) QueryBallPoint(x Point, r float64) []Point {var results []Pointif t.root == nil {return results}t.root.queryBallPoint(x, 0, r*r, &results)return results
}func (n *node) queryBallPoint(target Point, axis int, rSquared float64, results *[]Point) {if n == nil {return}// 计算当前节点到目标点的平方距离distSquared := 0.0for i := 0; i < target.Dimensions(); i++ {diff := n.Point.Dimension(i) - target.Dimension(i)distSquared += diff * diff}// 如果距离在半径内，则添加到结果中if distSquared <= rSquared {*results = append(*results, n.Point)}// 确定首先搜索哪个子树diff := target.Dimension(axis) - n.Point.Dimension(axis)nextAxis := (axis + 1) % target.Dimensions()// 优先搜索目标点较近的子树if diff < 0 {n.Left.queryBallPoint(target, nextAxis, rSquared, results)if diff*diff <= rSquared {n.Right.queryBallPoint(target, nextAxis, rSquared, results)}} else {n.Right.queryBallPoint(target, nextAxis, rSquared, results)if diff*diff <= rSquared {n.Left.queryBallPoint(target, nextAxis, rSquared, results)}}
}

收尾

go mod 添加

replace github.com/kyroy/kdtree => /Users/haiya/git_proj/kdtree

这篇关于在golang中实现KDTREE 的 queryBallPoint方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---