一类简单闭域的包含测试算法设计

摘要：

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

关键词：简单闭域、穿越边界、奇偶性

所属期刊栏目：42

分类号：TP391.41(计算技术、计算机技术)

资助基金：中国科学院资助项目20206033;湖南省自然科学基金03JJY3106;湖南省长沙市高新技术项目K03170-62

在线出版日期：2006-05-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：35-37