| LI Song(李松),SONG Shuang,HAO Xiaohong,ZHANG Liping.[J].高技术通讯(英文),2022,28(2):122~133 |
|
| Directional nearest neighbor query method for specified geographical direction space based on Voronoi diagram |
| |
| DOI：10.3772/j.issn.1006-6748.2022.02.002 |
| 中文关键词: |
| 英文关键词: nearest neighbor query, direction, Voronoi diagram, rectangular plane coordinate system |
| 基金项目: |
| Author Name | Affiliation | | LI Song(李松) | (College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, P.R.China) | | SONG Shuang | (College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, P.R.China) | | HAO Xiaohong | (College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, P.R.China) | | ZHANG Liping | (College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, P.R.China) |
|
| Hits: 677 |
| Download times: 616 |
| 中文摘要: |
| |
| 英文摘要: |
| The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space. In order to compensate the shortcomings of the existing methods, a directional nearest neighbor query method in specific direction space based on Voronoi diagram is put forward. This work studies two cases, i.e. the query point is static and the query point moves with a constant velocity. Under the static condition, the corresponding pruning method and the pruning algorithm of the specified direction nearest neighbor (pruningSDNN algorithm) are proposed by combining the plane right-angle coordinate system with the north-west direction, and then according to the smallest external rectangle of Voronoi polygon, the specific query is made and the direction nearest neighbor query based on Voronoi rectangle (VR-DNN) algorithm is given. In the case of moving with a constant velocity, first of all, the combination of plane right angle coordinate system, geographical direction and circle are used, the query range is determined and pruning methods and the pruning algorithm of the direction nearest neighbor based on decision circle (pruningDDNN algorithm) are put forward. Then, according to the different position of motion trajectory and Voronoi diagram, a specific query through the nature of Voronoi diagram is given. At last, the direction nearest neighbor query based on Voronoi diagram and motion trajectory (VM-DNN) algorithm is put forward. The theoretical research and experiments show that the proposed algorithm can effectively deal with the problem of the nearest neighbor query for a specified geographical direction space. |
|
View Full Text
View/Add Comment Download reader |
| Close |
|
|
|
