【作者】 吕琳； 杨承磊； 汪嘉业；

【Author】 Lu Lin~1,Yang Chenglei~1,Wang Jiaye~(1,2) 1(School of Computer Science and Technology, Shandong University,Ji’nan 250101,China) 2(Shandong Economics College,Ji’nan 250014,China)

【机构】 山东大学计算机科学与技术学院； 山东经济学院；

【摘要】 本文提出一种计算任意点可见多边形的新方法。给定一个点数为n,包含h个洞的多边形P和P内的任意点v,计算v在P内的可见多边形VP(P,v).首先,将P分割成O(h)个简单多边形,然后利用文献[4]中的方法将每个简单多边形的内部和外部分割成可见单元,并建立数据结构。我们的方法可以在O(log~2m+hlog(n/h)+h+|VP(P,v)|)时间内报告VP(P,v),其中m表示点v所在简单多边形的点数,m<n,并需要预处理时间O(n~2 logn)和空间O(n~2)。更多还原

【Abstract】 In this paper,we have discussed how to query the visibility polygon VP(P,v) of an arbitrary point v in a polygon P with n vertices and h holes.We first divide P into O(h) simple polygons,and then decompose the inner and exterior of each simple polygon into visibility cells and create data structures using the methods of[4].In the running phase,our algorithm can report VP(P,v) in O(log~2m+hlog(nlh) +h +|VP(P,v)|) time, where m is the size of the simple polygon that v locates in and m<n,with O(n~2) space and O(n~2logn) preprocessing time.更多还原