K-D tree的估价
n+e
posted @ 2015年6月30日 21:46
in Interesting
with tags
kd-tree
, 1055 阅读
只是自己做个备份
网络上好像没有几篇有介绍这个东西的
首先结构体
struct KDTree{
int d[2],s[2],x[2],y[2];
}t[N];
d-维度，s-儿子，x-x坐标范围，y-y坐标范围
然后估价，这里的估价是算出下界或上界
距离最小：一个点离当前域的最短距离（内部为0）
距离最大：一个点离当前域端点的最长距离
以平面为例，(x,y)为查询的坐标
曼哈顿最小：
max(t[p].x[0]-x,0)+max(x-t[p].x[1],0)+max(t[p].y[0]-y,0)+max(y-t[p].y[1],0);
曼哈顿最大
max(abs(x-t[p].x[1]),abs(t[p].x[0]-x))+max(abs(y-t[p].y[1]),abs(t[p].y[0]-y));
欧几里德最小
sqr(max(max(x-t[p].x[1],t[p].x[0]-x),0))+sqr(max(max(y-t[p].y[1],t[p].y[0]-y),0))
欧几里德最大
max(sqr(x-t[p].x[0]),sqr(x-t[p].x[1]))+max(sqr(y-t[p].y[0]),sqr(y-t[p].y[1]))
切比雪夫距离？把坐标转45°就是曼哈顿距离了233
评论 (0)