一种快速的椭圆形窗口的裁剪算法

《一种快速的椭圆形窗口的裁剪算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第22卷第2期计算机应用与软件Vo1．22，No．22005年2月ComputerApplicationsandSoftwareFeb．20D5一种快速的椭圆形窗口的裁剪算法黄新贤吴庆标(浙江大学数学系科学93-程计算研究所浙江杭州310028)摘要本文是实现椭圆形窗口对线段的快速裁剪，利用椭圆的外切长方形与线段的位置关系，对几种简单情形进行快速判断，对剩下的情况，利用预先制备的规范化表，通过映射法查表，实现对所有线段的裁剪，从而大幅度提高了裁剪速度。关键词椭圆形窗口线段裁剪算法规范化交点表AFASTLINECL删

2、GALGo姗肼FoREIJE砌NDoWSHuangXinxianWuQingbiao(ofMathematics，InstituteD，＆&西∞Gompute，Z^咖￡，肚嘎0ⅡZhefiang310028，CⅪ)AbstractThispaperistorealizethelineclippingforellipsewindowsinahighspeed．Makinguseofthelinearrelationbetweenanellipseanditstangentrectangle，thisalgorithm

3、findsoutseveralobvioussituations．Fortheothers，thispaperrealizesanewlineclippingalgorithmviaiI1gandtablechecking，whichisalreadyprepar甜andnormalizedaswel1．Thisalgorithmisgeneralandhasmuchhigherthanthecurrent0fles．KeywordsEllipsewindowLineClippingalgorithmNormali

4、zedintersectiontable1引言+：·口D线段裁剪是计算机图形学研究的一个基本内容，裁剪算法则线段所在直线和椭圆的交点可通过求解如下联立方程而的优劣是影响图形系统效率的主要原因之一。对于矩形窗口的得：线段裁剪已经有许多著名的算法，如经典的Cohen-Sutherland算(—1)(Y2一Y1)一(Y—Y1)(2一1)=0法、中点分割算法和参数方法【8】，以及FIE算法【5】、Nichol-Lee-—+—：lNichol算法【6和ELC算法【7等等。圆形窗口的裁剪由于包含复杂的计算而难以提高裁剪的速度，

5、现有不少文章研究关于圆形由于上述联立方程的求解十分耗时，故我们采取先以简单窗口对线段的裁剪，提出了各种不同的算法，并使裁剪速度得到方法分析线段和椭圆的位置关系，排除那些不可能有交点的情了不同程度的提高。文献[1，2]给出了三种算法，其实质都是把况，以尽可能减少求交运算。直线段的参数方程代入窗口圆的代数方程，通过求解一元二次线段和椭圆的位置关系大致有以下3／方程而实现裁剪。文献[3]试图通过矩形单侧排除和点．线距离种，如图1所示。比较来排除与圆不相交的线段，但在求直线与圆的交点时，也无(1)相离线段在椭圆的外部，彼此

6、＼=二=2／法避免一元二次方程的求解。文献[4]的算法虽然避开了一元不相交。二次方程的求解，但是只讨论关于圆形窗口的裁剪，而关于椭圆(2)包含线段两顶点均在椭圆的内图l线段和椭圆的形窗口对线段的裁剪，由于计算更为复杂，计算量更大而难以找部，线段和椭圆也彼此不相交。三种位置关系到一种快速的裁剪算法，文献[2]给出了椭圆形窗口对于线段的(3)相交线段和椭圆有一个或两个一种裁剪算法，但是其中包含大量的二次运算而难以提高裁剪交点。速度。从理论上讲，判断一条线段和椭圆的位置关系可以用距离本文利用椭圆的外切长方形，试图通过对线

7、段所在的不同法。但是距离法将不可避免地要解一元二次方程，非常耗时。位置进行分析，尽量不通过复杂的计算而通过比较分析直接接为了减少计算量，提高裁剪速度，本文进一步将上述位置关系细受或排除那些比较容易判断的线段，然后对剩余的线段，利用预分，如图2所示。先制备的规范化表，通过映射法查表，实现椭圆形窗口对线段的定义1本文中的“外切长方形”是指四边分别平行于坐标裁剪，从而大幅度提高了裁剪速度，并具有普遍性。轴且与椭圆相切的长方形。定义2本文中的“内接长方形”是指四边分别平行于坐标2线段和椭圆的位置关系分析设线段P，P两端点的

8、坐标为(x。，))和(x，)‘)，椭圆形收稿日期：2O03—10—10。浙江省自然科学基金资助项目(编号：窗口圆心的坐标为(xo，)，椭圆方程为：197047)。黄新贤，硕士生，主研领域：计算机图形学和图像处理。计算机应用与软件2005血轴，并且与该椭圆的“外切长方形”相似3．2直线与外切长方形的关系的，包含在椭圆内部的最大的长方形。上述c，d，／或g类线段