见原文，转自http://longriver.me/?p=355
图1，将一个地域划分为网格，并给每个网格唯一id
图2，AOI:圆明园，天安门，森林公园
假设一种空间检索的应用场景，现在有一堆面状的区域，我们知道这些面状区域（AOI area of interest）的轮廓如图2，我们有一些坐标点，那么如何判断这些坐标点是否落在aoi里，落到了哪个区域里呢？
完成这项工作，需要三步：
|
1
2
3
4
5
6
7
8
9
10
11 |
intaoi_util::build_gridindex()
{
// build index for each aoi
for(size_tj=0;j<aois.size();++j){
aoi_index idx;
idx=j;
AOI*aoi_ptr=&aois[j];
build_gridindex(aoi_ptr,idx);
}
return0;
} |
Mesh_size 可以根据一共检索区域的大小来进行设定，在我们的应用场景下设为1000，指每个网格的大小为1000m。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 |
intaoi_util::build_gridindex(AOI *aoi_ptr,aoi_index idx)
{
ll_t min_x,min_y,max_x,max_y;
//get every aoi‘s leftmost rightmost
,ceiling,bottom
min_x=aoi_ptr->min_boundx();
min_y=aoi_ptr->min_boundy();
max_x=aoi_ptr->max_boundx();
max_y=aoi_ptr->max_boundy();
// get every grid id
typedefgrid_index::iterator grid_map_it;
for(size_ta=size_t(min_x/mesh_size);a<=size_t(max_x/mesh_size);a++){
for(size_tb=size_t(min_y/mesh_size);b<=size_t(max_y/mesh_size);b++){
uint32_t id=get_id_by_grid(a,b);
grid_map_it it=grid2index.find(id);
if(it==grid2index.end()){
index_value idx_vl;
idx_vl.push_back(idx);
// each grid may have more than one aoi
grid2index.insert(std::pair<uint32_t,index_value>(id,idx_vl));
}else{
it->second.push_back(idx);
}
}
}
return0;
} |
2,为每个检索点找到所在的mesh 和每个mesh中的aoi
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 |
AOI*aoi_util::get_aoi_for_point(ll_tx,ll_ty)
{
uint32_t mesh_id=get_id_by_xy(x,y);
typedefgrid_index::const_iterator grid_map_it;
typedefindex_value::iterator index_value_it;
index_value idx_list;
grid_map_it it=grid2index.find(mesh_id);
if(it!=grid2index.end()){
idx_list =it->second;
for(index_value_it
iv_it=idx_list.begin();iv_it!=idx_list.end();++iv_it){
aoi_index idx= *iv_it;
AOI *aoi_i=&(aois[idx]);
// determine if poinxy in this aoi
if(aoi_i->is_point_inside(x,y)){
returnaoi_i;
}
}
}
returnNULL;
} |
3,判断一个point 是否在aoi里面，一个aoi其本质上是一个多边形，由顶点描述，因此现在有很多现成的算法讲如何判断一个点是否落在多边形中，参照这边博文http://alienryderflex.com/polygon/讲的非常详细，代码实现如下，具体原理，请阅读博文。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 |
boolAOI::is_point_inside(ll_tx,ll_ty)
{
typedefvertexes_t::iterator v_iterator;
v_iterator it,pre_it;
booloddNodes=0;
// vertexes are polygon’s vertexes vector
it=pre_it=vertexes.begin();
for(;it!=vertexes.end();++it)
{
if((it->second<y&&pre_it->second>=y)
||(pre_it->second<y&&it->second>=y)
&&(it->first<=x||it->second<=x)){
oddNodes^=(it->first+(y-it->second)/(pre_it->second-it->second)\
*(pre_it->first-it->first)<x);
}
pre_it=it;
}
returnoddNodes;
} |
4,剩余的一些代码，如如何对grid去hash值，可以自己去实现，贴上我们的实现，仅作参考：
|
1
2
3
4 |
uint32_t
aoi_util::get_id_by_grid(uint32_ta,uint32_tb)
{
return((a&0xffff)<<16)|(b&0xffff);
} |
原文：http://www.cnblogs.com/harveyaot/p/3627056.html