简单多边形内线燃烧动态轨迹算法  

Line Burning Dynamical Trajectory Algorithm in Simple Polygon

作　　者：张云辉[1] 高满屯[2] 吴建军[2] 王淑侠[2] 张燕[3] 

机构地区：[1]西安工业大学机电学院,西安710032 [2]西北工业大学机电学院,西安710072 [3]华为技术有限公司西安研究所,西安710075

出　　处：《计算机辅助设计与图形学学报》2012年第8期1003-1011,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61063030,51105310)

摘　　要：为了模拟草场上线燃烧的动态过程,提出了分别由位于点可视区域的圆弧和方向可视区域的线段组成的多边形线的燃烧轨迹模型.首先利用点可视和方向可视技术实现简单多边形的深度方向可视划分;然后在可视划分的子多边形内,通过计算有向线段与视点或视线的极小?极大距离来实现视线到任意线段或任意可视多边形的极小?极大最短路径的计算;最后分别在点可视区域计算出有向线段与圆的17种位置关系,在方向可视区域计算出有向线段与直线的9种位置关系,再根据这些位置关系确定入点和出点,画出燃烧轨迹的圆弧或线段,并通过VC++编程实现了整个算法.算例结果表明,该算法可以计算不同时刻的火场燃烧轨迹、不同地点的燃烧时间以及火场燃烧的最远距离和最长时间等.In order to simulate the dynamic burning process in a pasture, the burning trajectory model of the Polygon-Curve is created, which composed of arcs in point visible polygon and of line segments in line visible polygon. Firstly, the point visible and the direction visible techniques are used to complete the deep visible division of a simple polygon. Then, in each divided sub-polygon, the mini- max distances of each vector edge to its viewpoint or view line are calculated, which can be used to achieve the calculation of mini-max shortest paths between the initial burning line to any edge or to any visible sub-polygon. Finally, Total 17 kinds of locations for the position relationships of a circle to vector lines and 9 kinds of locations for the position relationships of a line to vector lines are calculated. By used of these position relationships, the into-point and out-point are found and the arcs or line segments of burning trajectory are draw, and the algorithm is programmed by VC＋＋ and several testing examples are examined. Experimental results show that this algorithm can achieve such things that drawing the burning trajectories at different times, computing the burning times in different positions, estimating the longest distance and the longest time of burning etc.

关 键 词：计算几何 方向可视 线燃烧轨迹 最短路径 多边形线 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]