Gabriel 图 (gabriel gragh)"/>
Gabriel 图 (gabriel gragh)
(欢迎录载到百科中)
参考=timeline
按Grabriel三角划分法 划分 出来的结果叫Grabriel 图。
Grabriel 划分 是 Delaunany 三角剖分的一种
定义:GG(grabriel gragh 缩写)
存在点集E ,u、v、w 属于E,如果节点u和节点v之间,直径为uv的圆内,不存在其它顶点w,则节点u和节点v为GG边(u,v)。用方程式表示如下:
∀w∈E,w!=[u,v] : d²(u,v) ≤ max( d²(u , w) , d²(v , w)
下图形象地说明了Grabriel 图的定义,节点u和节点v之间形成一个直径为d(u,v)的圆形,节点u和节点v都在圆上,即是圆形阴影区域。若(u,v)是GG中的边,则在节点u和v之间的圆形阴影区域,不能包含有任何证明节点w。所以下图的uv不是GG边。
GG平面图的算法
直径为uv的圆形阴影的圆心也是uv的中点。对于每个节点u,有完整的邻节点列表N,用以下伪代码去除非GG连接:
对于这样的计算有一种加速方式就是 先对数据做kd树划分,使可以快速判断临近值,再在此基础上进行广度优先或者深度优先扩张(可以对kd树多添加一个变量达到这个目的)。
从如下图所示,左图是无线网络的完整拓扑图;200个节点被随机部署在2000*2000米的区域,无线电范围为250米;中间表示整个拓扑图的GG子图;右图表示整个拓扑图的RNG子图。
更多推荐
Gabriel 图 (gabriel gragh)
发布评论