【摘要】 自由曲面的高斯图计算中,需要对由抛物线和直线段组成的闭域进行包含检测来判断该闭域是否为最小闭域,抛物线段由逼近折线多边形表示且单调。基于点与简单闭域的拓扑关系,重新定义了“穿越边界”,设计了点与简单闭域关系判断的算法。该算法通过检测穿越闭域边界次数的奇偶性来判断点与闭域的位置关系;其中对射线与抛物线相交的处理大大减少了判断次数。可以证明算法的时间复杂度仅为o(n);实验表明,该算法简单有效可靠。更多还原

【Abstract】 While computing Gauss map of free-form surface,it is necessary for point-in-closed region test of a closed region composed of line segments and parabola segments to judge whether the closed region is the single-connected region,which parabola segment is approximated by piecewise-linears and is monotone.Based on topologic relation of point and simple closed region,an algorithm is presented to do the inclusion test for simple closed region."Crossing boundary" is given new definition,and pretreatment that all curve segments composed of the closed region boundary become single value or vertical is carried into effect.Through determining parity of number that radial crossing boundary,the algorithm judges the relationship between the point and simple closed region.The experiment results show that the algorithm is simple,efficient and credible,and time-complexity is o(n).更多还原