一种改进的点在多边形内外判断算法

doi:10.3969/j.issn.1000-3428.2012.05.007

计算机工程 ›› 2012, Vol. 38 ›› Issue (5): 30-34. doi: 10.3969/j.issn.1000-3428.2012.05.007

一种改进的点在多边形内外判断算法

李楠，肖克炎

(中国地质科学院矿产资源研究所，北京 100037)

收稿日期:2011-09-23 出版日期:2012-03-05 发布日期:2012-03-05
作者简介:李楠(1980－)，男，工程师、博士，主研方向：地理信息工程，地图制图学；肖克炎，研究员、博士生导师
基金资助:
国家自然科学基金资助项目(41002119)；国家“863”计划基金资助项目(2006AA06Z114)；国家科技支撑计划基金资助项目(2006BAB01A01)；中央级公益性科研院所基本科研业务费专项基金资助项目

Improved Judgment Algorithm of Point In-out Polygon

LI Nan, XIAO Ke-yan

(Institute of Mineral Resources, Chinese Academy of Geological Sciences, Beijing 100037, China)

Received:2011-09-23 Online:2012-03-05 Published:2012-03-05

摘要/Abstract

摘要：

为解决多边形内外算法中BSP树退化为链表的问题，提出一种改进的点在多边形内外的判断算法。在构建水平扫描线的BSP树之前，对水平扫描线按照Y值进行排序，将排好序的水平扫描线按照二分法的顺序插入到BSP树中，其查找时间复杂度为O(lbn)。实验结果表明，该算法在不增加BSP构建时间复杂度的前提下，能够保证BSP树的查找效果总是最优的，且简单易行，具有较好的通用性。

关键词: BSP树, 平衡二叉树, 任意简单多边形, 二分查找, 快排序

Abstract:

For settling a problem that Binary Space Partition(BSP) tree of in-out polygon algorithm degenerates into line list, this paper presents an improved judgment algorithm of point in-out polygon. The algorithm sorts Y value per node in polygon. It travels all horizon lines by way of binary. BSP tree is always balance binary tree. The time complexity of the BSP-Tree searching is O(lbn). Experimental results show that the improved algorithm makes sure that time complexity for the query of binary space partition trees is always high efficient while time complexity for the construction of BSP trees does not increase. Meanwhile, it has good versatility.

Key words: Binary Space Partition(BSP) tree, balanced binary tree, arbitrary simple polygon, binary search, quick sort

中图分类号:

TP391

李楠, 肖克炎. 一种改进的点在多边形内外判断算法[J]. 计算机工程, 2012, 38(5): 30-34.

LI Nan, XIAO Ke-Tan. Improved Judgment Algorithm of Point In-out Polygon[J]. Computer Engineering, 2012, 38(5): 30-34.

http://www.ecice06.com/CN/Y2012/V38/I5/30

参考文献

[1] Philip J S, David H E. Geometric Tools for Computer Graphics[M]. Beijing, China: Publishing House of Electronics Industry, 2004.
[2] Manber U. Introduction to Algorithms——A Creative Appro- ach[M]. New York, USA: Addison-Wesley, 1989.
[3] Foley J D, van Dam A, Feiner S K, et al. Computer Graphics——Principles and Practice[M]. 2nd ed. New York, USA: Addison- Wesley, 1990.
[4] Feito F, Torres J C, Urena A. Orientation, Simplicity, and Inclusion Test for Planar Polygons[J]. Computers & Graphics, 1995, 19(4): 595-600.
[5] Feito F, Torres J C. Inclusion Test for General Polyhedra[J]. Computers & Graphics, 1997, 21(1): 23-30.
[6] Preparata F P, Shamos M I. Computational Geometry: An Intro- duction[M]. New York, USA: Springer, 1985.
[7] Taylor G. Point in Polygon Test[J]. Survey Review, 1994, 32(1): 479-484.
[8] Rueda A J, Feito F R, Rivero M. A Triangle-based Representation Forpolygons and Its Applications[J]. Computers & Graphics, 2002, 26(5): 805-814.
[9] Wang Wencheng, Li Jing, Wu Enhua. 2D Point-in-polygon Test by Classifying Edgesinto Layers[J]. Computers & Graphics, 2005, 29(3): 427-439.
[10] Huang Chongwei, Shih T Y. On the Complexity of Point-in- polygonalgorithms[J]. Computers & Geosciences, 1997, 21(1): 109-118.
[11] Zalik B, Kolingerova I. A Cell-based Point-in-polygon Algorithm Suitable for Large Sets of Points[J]. Computers & Geosciences, 2001, 25(10): 1135-1145.
[12] de Berg M, van Kreveld M, Overmars M, et al. Computational Geometry: Algorithms and Applications[M]. 2nd ed. Berlin, Germany: Springer, 2000.
[13] Zalik B, Jezernik A, Rizmanzalik K. Polygon Trapezoidation by Sets of Open Trapezoids[J]. Computers & Graphics, 2003, 27(5): 791-800.
[14] Teillaud M. Union and Split Operations on Dynamic Trapezoidal Maps[J]. Computational Geometry: Theory and Applications, 2000, 17(3/4): 153-163.
[15] Henry F, Kedem Z, Naylor B. On Visible Surface Generation by Priori Tree Structure[C]//Proc. of SIGGRAPH’80. New York, USA: ACM Press, 1980: 124-133.
[16] Sahni S. 数据结构、算法与应用——C++语言描述[M]. 汪诗林,孙晓东, 译. 北京: 机械工业出版社, 2006.
[17] 窦长旭, 王玉玫. 多边形中心点向量的二次插值变形算法[J]. 计算机工程, 2010, 36(16): 189-191.

选择文件类型/文献管理软件名称

选择包含的内容

一种改进的点在多边形内外判断算法

Improved Judgment Algorithm of Point In-out Polygon

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	毛勇华,代兆胜,桂小林. 基于深度信念网络的无线信道二分查找方法[J]. 计算机工程, 2018, 44(7): 86-90.
[2]	林意, 公亚利. 边界切向量长度对B样条曲线的影响及优化[J]. 计算机工程, 2013, 39(8): 295-298.
[3]	杨晟院, 杜亚娟, 舒适. 基于STL文件的曲面网格重建算法[J]. 计算机工程, 2011, 37(4): 10-11.
[4]	陈焱;周莹莹;杨柏林. 适用于移动设备的实时碰撞检测算法[J]. 计算机工程, 2010, 36(06): 273-275.
[5]	崔尚森;冯博琴;张白一. 一种前缀长度二分查找的改进算法[J]. 计算机工程, 2007, 33(15): 70-71,8.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

一种改进的点在多边形内外判断算法

Improved Judgment Algorithm of Point In-out Polygon

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价