|
|
|
| Direction Visible Division in a Polygon |
| ZHANG Yun-Hui, GAO Man-Tun, WU Jian-Jun, WANG Shu-Xia |
| School of Mechanical Engineering,Northwestern Polytechnical University,Xi’an 710072 |
|
|
|
|
Abstract To achieve line burning trajectory calculations within a simple polygon, the concept of direction visible is proposed under the condition of line view, eight types of visible lines are found firstly, and seven kinds of bridge structure models are summarized to achieve direction visible division for a simple polygon. Polygonal interior is divided into two point visible areas and two line visible areas under direction projection and the bridges are constructed to complete boundary direction division by using the block relationship between main line and secondary line. Then, combined with point visible division algorithm, the polygon is divided into deep direction visible sub-polygons. Using these sub-polygons, the shortest path from any point to any line is derived within original polygon. Finally, the proposed algorithm is applied to line burning trajectory calculation in a polygon and obtains a good performance.
|
|
Received: 05 May 2011
|
|
|
|
|
|
[1] Ghosh S K.Visibility Algorithms in the Plane.Cambridge,USA:Cambridge University Press,2007
[2] Davis L,Benedikt M.Computational Models of Space: Isovists and Isovist Fields.Computer Graphics and Image Processing,1979,11(1): 49-72
[3] Chazelle B,Guibas L J.Visibility and Intersection Problems in Plane Geometry.Discrete Computational Geometry,1989,4(1): 551-581
[4] El Gindy H,Avis D.A Linear Algorithm for Computing the Visibility Polygon from a Point.Journal of Algorithms,1981,2(2): 186-197
[5] Lee D T.Visibility of a Simple Polygon.Computer Vision,Graphics,and Image Processing,1983,22(2): 207-221
[6] Joe B,Simpson R B.Corrections to Lees Visibility Polygon Algorithm.BIT Numerical Mathematics,1987,27(4): 458-473
[7] Bhattacharya B K,Ghosh S K,Shermer T.A Linear Time Algorithm to Remove Winding of a Simple Polygon.Computational Geometry: Theory and Applications,2006,33(3): 165-173
[8] Avis D,Toussaint G T.An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge.IEEE Trans on Computers,1981,100(12): 910-914
[9] Qu Jilin,Yang Hongwan.Visibility of a Set of Arbitrary Simple Polygons.Journal of Shandong Normal University: Natural Science,2000,15(2): 133-137 (in Chinese)
(曲吉林,杨洪万.平面内任意一组简单多边形的可见性.山东师范大学学报:自然科学版,2000,15(2): 133-137)
[10] Liu Rongzhen,Zhao Jun,Cheng Yaodong.Efficient Point Visibility Algorithm for Simple Polygons.Journal of Engineering Graphics,2009,30(2): 109-113 (in Chinese)
(刘荣珍,赵 军,程耀东.求简单多边形可见点的一种新算法.工程图学学报,2009,30(2): 109-113)
[11] Ou Xinliang.Visibility for a Set of Segments Based on Linear Light Source in the Plane.Journal of National University of Defense Technology,2001,23(1): 102-104 (in Chinese)
(欧新良.平面内一组线段相对于线光源的可见性.国防科技大学学报,2001,23(1): 102-104)
[12] Ou Xinliang,Fang Kui.Visibility for a Set of Segments Based on Parallel Light in the Plane.Journal of Changsha University,2005,19(5): 73-74 (in Chinese)
(欧新良,方 逵.平行光照射下平面内一组线段的可见性.长沙大学学报,2005,19(5): 73-74)
[13] Tarjan R E,van Wyk C J.A Linear-Time Algorithm for Triangulating Simple Polygons // Proc of the 8th Annual ACM Symposium on Theory of Computing.Berkeley,USA,1986: 380-388
[14] Chazelle B.Triangulating a Simple Polygon in Linear Time.Discrete Computational Geometry,1991,6(1): 485-524
[15] Guibas L J,Hershberger J,Leven D,et al.Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons.Algorithmica,1987,2(1): 209-233
[16] Toussaint G T.Shortest Path Solves Edge-to-Edge Visibility in a Polygon.Pattern Recognition Letters,1986,4(3): 165-170
[17] Ghosh S K,Maheshwari A,Pal S P,et al.Characterizing and Recognizing Weak Visibility Polygons.Computational Geometry: Theory and Applications,1993,3(4): 213-233
[18] Guibas L J,Hershberger J.Optimal Shortest Path Queries in a Simple Polygon.Journal of Computer and System Sciences,1989,39(2): 126-152
[19] Bose P,Lubiw A,Munro J.Efficient Visibility Queries in Simple Polygons.Computational Geometry: Theory and Applications,2002,23(3): 313-335
[20] Lien J M,Amato N M.Approximate Convex Decomposition of Polygons.Computational Geometry: Theory and Applications,2006,35(1): 100-123
[21] Gerdjikov S,Wolff A.Decomposing a Simple Polygon into Pseudo-Triangles and Convex Polygons.Computational Geometry: Theory and Applications,2008,41(1): 21-30 |
|
|
|
2012, Vol. 25 
