自由曲面高斯图闭域包含测试算法设计

《自由曲面高斯图闭域包含测试算法设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2006年第23卷第7期微电子学与计算机157自由曲面高斯图闭域包含测试算法设计欧新良-，2陈松乔1方逵2肖健宇3(1中南大学信息科学与工程学院，湖南长沙410083)(2长沙学院计算机科学与技术系，湖南长沙410003)(3西安交通大学电子与信息工程学院，陕西西安710049)摘要：提出了一种闭域包含点检测算法，对曲线边先进行包含测试，再找到相交线段。其中对抛物曲线段用二分查找法找到相交线段。由于曲边数远小于逼近多边形的边数n·m，该算法时间复杂度仅为o(n．Inm)，加快了检测速度。关键词：高斯图，闭域包含点检测，二分法，连接数中图法分类号：TP391．41文献标识码

2、：A文章编号：1000-7180(2006)07-003．AnAlgorithmforPointInclusioninFree-formsurface’SClosedGaussMapQueryOUXin-liang，CHENSong-qiao，FANGKui2,XIAOJian-yu(1ConegeoffIrmati。nScience&EngineeringSentralSouthUniversity，Changsha410083China)(2DepartmentofComputerScienceandTechnology，ChangshaCoiloge，Changsh

3、a410003China)(3SchoolofElectronicsandInformationEngineering，Xi’anJiaotongUniversity，Xi’an710049China)Abstract：Analgebraicalgorithmreformedpaperispresented．Whenrunningit,point—in—segmentinclusionquerydid．befo~findingintersectsegmentorusingdichotomytofindtoparabolasegment．Thealgorithmcomple

4、xityisO(，l·lIlm)，andacceleratesthetestfor，l<<，l·m．Keywords：Gaussmap，Point-in-closedregiontest，Dichotomy，Link-number1引言对曲线边先进行相交检测．再用快速查找法找到相平面上点与简单闭域的关系问题是计算机图关边。由于曲边数远小于逼近多边形的边数。该算形学中的基本问题．在区域填充、连通域判断、碰撞法可大大减少运算量，加快检测速度。检测等方面都有着重要的理论和应用价值。由于闭域曲线边界一般是用直线段逼近表示．闭域由逼近2算法基本思想多边形表示．因此平面上点与闭域的关

5、系问题在计自由曲面高斯图闭域由直线段和单值抛物线算机图形学中总是转化为判断点与简单多边形的段组成，属于本文所定义的特殊闭域；而抛物线段关系。但是。用简单多边形去逼近闭域，会使多边形由多边形直线段逼近形成．因此整个闭域又可以认顶点数和边数巨大．运算量非常大。如果某特殊闭为是简单多边形，如图1所示圆。对于每条曲线段，域的曲线边已经求得其多边形逼近．并用单值函数其逼近多边形线段已经不需预处理就具备实现快表示．可否设计这样一个算法：能使点与闭域关系速查找的数据结构。因此充分利用这类特殊闭域的检测算法大大减少运算量。加快检测速度。目前已经有很多方法检测点与简单多边形的关系．但研究点

6、与任意闭域的关系的很少．检测其关系的算法尚未发现，本文研究了这类特殊闭域的特点和文献f1～31的算法，提出了一种基于笛卡尔坐标的检测算法，收稿日期：2005—10-08乏／／＼基金项目：国家自然科学基金项目(20206033)湖南省自然科学基金项目(03JJY3106)图1自由曲面参数域高斯图158微电子学与计算机2006年第23卷第7期特点，吸收文献『1～31的算法思想来设计自由曲面高斯图闭域包含测试算法：让一条垂直直线去与多边形相交遇到直线段，则判断其相交性，遇到曲线段时，则使用快速二分查找法。找到相交直线段，再判断其相交性。利用算法【l】的代数特征判断其关系。(a)

7、全交(b)半交定义数据结构如下：按逆时针方向建立有向曲线段Is的循环链表。结点信息包括有向曲线段是否直线段(是，为0；否则为1)、始端点(，yi)、指向下一结点指针。指针P点与线段的连接数(1inkingnumber)：任意点Q指向第一个结点，尾结点就是头结点，对于曲线段，由于它是单值抛物线段。由四叉树分解(quadtreef2，全交decomposition)算法得到。其多边形逼近折线是横坐IJ(q，s)I={1，半交标方向的单值增(或减)，每条抛物线段均按横坐标JOr不交单值方向建立单独的结点链，以曲线段始点为子链如果是有