摘要
平面中点对一般多边形的最近邻查询问题是要在一般多边形集合中找到查询点的最近邻以及顺序最近邻。针对查询对象的特殊性,以R树作为索引结构,采用一般多边形的凸包组织空间结构。通过判断可见边计算查询点到凸包的最小距离。采用优先队列的方法给出查询点到每个凸包的最小距离的排序,最终找到查询点的最近邻和顺序最近邻。
The nearest neighbor query of point to general polygons in the plane is to find the nearest neighbor and sequential nearest neighbor in the general polygon set. In view of the particularity of the query object, regards R tree as the index structure, organizes spatial structure with convex hull of the general polygon, computes the minimum distance between the query point and the convex hull by judging the visible edge and gives the sort of the minimum distance between the query point and each convex hull with the , eventually finds nearest neighbor and sequential nearest neighbor of the query point.
出处
《科技通报》
北大核心
2014年第1期138-140,219,共4页
Bulletin of Science and Technology
基金
黑龙江省教育厅科学技术研究项目(12511610)
关键词
一般多边形
最近邻查询
凸包
凸多边形
优先队列
R树
general polygons
nearest neighbor query
convex hull
convex polygon
priority queue
R-tree
