A New Algorithm for Detecting Position Relationship between Point and Polygon

Abstract:

A new algorithm for position relationship between detecting point and polygon is proposed based on the research of radial method, and as the first step, transform polygon in convex polygon, then determine the position relationship between detecting point and original polygon by judging the position relationship between detecting point and transformed convex polygon and closed polygon. The new method can accurately determine the position relationship between point and arbitrary shape polygon which fully considers all kinds of position conditions including detecting point inside, on (including vertex) and outside the polygon.

• Periodical: Advanced Materials Research (Volumes 433-440)
• Pages: 4248-4253
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.433-440.4248
• Online since: January 2012
• Authors: Sheng Wu Dong, Dong Wang, Yun Peng Wang
• Keywords: Azimuth, Point, Point of Intersection, Polygon, Radial Method

References

[1] Chen Ruiqing, Zhou Jian, Yu Lie, A fast method to determine spatial relationship between point and polygon , Academic Journal of Xi'an Jiaotong University, Jan. 2007, Vol. 41, No. 1, P. 59-63.

[2] Wu Jian, Jiang Hong, Wang Xiaochun, A method for the determination of a point whether is in or not in self-intersected polygon, Journal of System Simulation, Nov. 2003, Vol. 15, No. 11, P. 1592-1594.

[3] G. Taylor, Test of point inside polygon, Bulletin of Surveying and Mapping, 1996, No. 1, P. 49-51.

[4] Miao Chunbao, Radial method for the relationship between point and polygo, Computer Programming Skills & Maintenance, 2008, No. 3, P. 56-58.

[5] Zhou Peide, An algorithm for determining whether a point lies within the polygon, Transactions of Beijing Institute of Technology, Nov. 1995, Vol. 15, No. 4, P. 437-440.

[6] Liu Xiaojing, Zhao Junsan, An algorithm to determine the spatial relations between the point and polygon and among the simple polygons. Sci-Tech Information Development & Economy, 2008, Vol. 18, No. 28, P. 223-224.

[7] Chen Shuqiang, Chen Xuegong, Wang Liqing, A new method deciding whether a point is in a polygon. Microelectronics & Computer, 2006, Vol. 23, No. 8, P. 194-195.

[8] Dong Xiushan, Liu Runtao, An algorithm for the location relation of simple polygon and point. Computer Engineering and Applications, 2009, Vol. 45, No. 2, P. 185-186.

[9] Wang Hongjuan, Improving algorithm for determining point inside arbitrary and simple polygon . Fujian Computer, 2006, No. 9, P. 155.

[10] Li Weishi, Li Jiangxiong, Ke Yinglin, A new method for determining plate polygon orientation and points inside and outside polygon, Journal of computer-aided design & computer graphics, Jun. 2000, Vol. 12, No. 6, P. 405-407.

[11] Wang Zegen, Improving radial method for determining inclusion relations between point and polygon , Journal of the PLA Institute of Surveying and Mapping, Jun. 1999, Vol. 16, No. 2, P. 130-132.

[12] Yan Haowen, Yang Weifang, Chen Quangong, Liang Tiangang, A fast algorithm of topological polygon auto-construction based on azimuth calculation, Journal of Image and Graphics, Jul. 2000, Vol. 5, No. 7, P. 563-567.