K-D tree的估价

n+e posted @ 2015年6月30日 21:46 in Interesting with tags kd-tree , 494 阅读

只是自己做个备份

网络上好像没有几篇有介绍这个东西的

首先结构体

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

---By n+e

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter