维普资讯 http://www.cqvip.com 第１９卷第４期 计算机辅助设计与图形学学报 ＪＯＵＲＮＡＬ ＯＦ ＣＯＭＰＵＴＥＲ—ＡＩＤＥＤ ＤＥＳＩＧＮ＆ＣＯＭＰＵＴＥＲ ＧＲＡＰＨＩＣＳ Ｖｏ１．１９．Ｎｏ．４ Ａｐｒ．，２００７ ２００７年４月 基于凸剖分的多边形窗口线裁剪算法 李 静 ’ 王文成 吴恩华 ’ ”（中国科学院软件研究所计算机科学国家重点实验室（中国科学院研究生院北京１０００４９） ） 北京 １０００８０） （大学科学技术学院电脑与资讯科学系（１ｉｊ＠ｉｏｓ．ａｃ．ｃｎ） 摘要 以不增加新点的方式将多边形剖分为一些凸多边形，并基于这些多边形的边建立二叉树进行管理．裁剪计 算时，根据二叉树快速地找到与被裁剪线有相交的凸多边形，然后运用高效的凸多边形裁剪算法进行线裁剪．该方 法能自适应地降低裁剪计算的复杂度，使其在Ｏ（１ｏｇｎ）和Ｏ（ ）之间变化，并在大多数情况下小于Ｏ（ ），其中 是 多边形边数．虽然该方法需要进行预处理，但在许多应用（如多边形窗口对多边形的裁剪）中，其总执行时间（包括预 处理时间和裁剪时间）比已有的不需要预处理的裁剪算法少很多． 关键词 多边形窗口；线裁剪；凸剖分；二叉树；加速 中图法分类号ＴＰ３９１ Ｌｉｎｅ Ｃｌｉｐｐｉｎｇ Ａｇａｉｎｓｔ ａ Ｐｏｌｙｇｏｎ Ｂａｓｅｄ ｏｎ Ｃｏｎｖｅｘ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ Ｌｉ Ｊｉｎｇ１，２）Ｗａｎｇ Ｗｅｎｃｈｅｎｇ ）Ｗｕ Ｅｎｈｕａ ， ） （ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ＩｎｓｔｉｔｕｔｅｏｆＳｏｆｔｗａｒｅ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １０００８０） （Ｇｒａｄｕａｔｅ ＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １０００４９） （Ｄｅｐａｒｔｍｅｎｔ ｏｆＣｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ，ＦａｃｕｌｔｙｏｆＳｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，ＵｎｉｅｒｓｉｖｔｙｏｆＭａｃａｕ，Ｍａｃａｏ） Ａｂｓｔｒａｃｔ Ａ ｎｏｖｅｌ ｌｉｎｅ ｃｌｉｐｐｉｎｇ ａｌｇｏｒｉｔｈｍ ａｇａｉｎｓｔ ａ ｇｅｎｅｒａｌ ｐｏｌｙｇｏｎ ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｅ ｐａｐｅｒ．Ｂｙ ｔｈｅ ａｐｐｒｏａｃｈ，ｔｈｅ ｐｏｌｙｇｏｎ ｉｓ ｆｉｒｓｔ ｄｅｃｏｍｐｏｓｅｄ ｉｎｔｏ ａ ｓｅｔ ｏｆ ｃｏｎｖｅｘ ｐｏｌｙｇｏｎｓ ｗｉｔｈｏｕｔ ａｄｄｉｎｇ ｎｅｗ ｐｏｉｎｔｓ ａｎｄ ｔｈｅｎ ｔｈｅｓｅ ｃｏｎｖｅｘ ｐｏｌｙｇｏｎｓ ａｒｅ ｏｒｇａｎｉｚｅｄ ｉｎ ａ ｂｉｎａｒｙ ｓｐａｃｅ ｐａｒｔｉｔｉｏｎ ｔｒｅｅ，ａｓ ａ ｓｅａｒｃｈ ｔｒｅｅ．Ｉｎ ｔｈｅ ｃｌｉｐｐｉｎｇ ｐｒｏｃｅｄｕｒｅ，ｔｈｅ ｓｅａｒｃｈ ｔｒｅｅ ｉｓ ｕｓｅｄ ｔｏ ｆｉｎｄ ｔｈｅ ｃａｎｄｉｄａｔｅ ｃｏｎｖｅｘ ｐｏｌｙｇｏｎｓ ｔｈａｔ ｉｎｔｅｒｓｅｃｔ ｔｈｅ ｃｌｉｐｐｅｄ ｌｉｎｅ ｓｅｇｍｅｎｔ ａｎｄ ｔｈｅｎ ａｎ ｅｆｆｉｃｉｅｎｔ ｌｉｎｅ ｃｌｉｐｐｉｎｇ ａｌｇｏｒｉｔｈｍ ａｇａｉｎｓｔ ａ ｃｏｎｖｅｘ ｐｏｌｙｇｏｎ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｅａｃｈ ｓｕｃｈ ｃａｎｄｉｄａｔｅ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ａｄａｐｔｉｖｅｌｙ ｄｅｃｒｅａｓｅ ｔｈｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｆｏｒ ｌｉｎｅ ｃｌｉｐｐｉｎｇ，ｒａｎｇｉｎｇ ｆｒｏｍ Ｏ（１ｏｇｎ）ｔｏ ０（ ），ｂｕｔ ｌｅｓｓ ｔｈａｎ Ｏ（ ）ｉｎ ｍｏｓｔ ｃａｓｅｓ，ｗｈｅｒｅ ｉｓ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｔｈｅ ｅｄｇｅｓ ｏｆ ｔｈｅ ｐｏｌｙｇｏｎ． Ａｌｔｈｏｕｇｈ ａ ｐｒｅｐｒｏｃｅｓｓ ｉｓ ｒｅｑｕｉｒｅｄ。ｉｎ ｍａｎｙ ａｐｐｌｉｃａｔｉｏｎｓ（ｅ．ｇ．ｃｌｉｐｐｉｎｇ ａ ｐｏｌｙｇｏｎ ａｇａｉｎｓｔ ａｎｏｔｈｅｒ ｐｏｌｙｇｏｎ）， ｔｈｅ ｔｏｔａｌ ｔｉｍｅ ｃｏｎｓｕｍｅｄ ｂｙ ｔｈｅ ｎｅｗ ｍｅｔｈｏｄ，ｉｎｃｌｕｄｉｎｇ ｔｈｅ ｔｉｍｅ ｆｏｒ ｐｒｅｐｒｏｃｅｓｓ ａｎｄ ｃｌｉｐｐｉｎｇ ｃａｌｃｕｌａｔｉｏｎ，ｉｓ ｍｕｃｈ ｌｅｓｓ ｔｈａｎ ｔｈａｔ ｂｙ ｔｈｅ ｅｘｉｓｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｗｉｔｈｏｕｔ ｐｒｅｐｒｏｃｅｓｓ． Ｋｅｙ ｗｏｒｄｓ ａｃｃｅｌｅｒａｔｉｏｎ ｏｌｐｙｇｏｎａｌ ｗｉｎｄｏｗ； ｌｉｎｅ ｃｌｉｐｐｉｎｇ；ｃｏｎｖｅｘ ｄｅｃｏｍｐｏｓｉｔｉｏｎ；ｂｉｎａｒｙ ｓｐａｃｅ ｐａｒｔｉｔｉｏｎ ｔｒｅｅ； 关于凸多边形窗口的线裁剪问题，有比较深入 的研究 一。 ；而对于一般多边形窗口的线裁剪问题 理的效率并不高 ．所以，已有方法大多不１进行预 处理而直接检测多边形的每条边，以找到与被裁剪 线所在直线（简称裁剪直线）相交的边，再进行裁剪 的研究还不多．虽然文献［１］提出将一般多边形进 行凸剖分，再基于凸多边形进行线裁剪；但该方法处 计算．为快速地找到这些相交的边，文献［４－６］用 修回日期：２００６—０９—０１．基金项目：国家自然科学基金（６Ｏ３７３Ｏ５１）；国家“九七三”重点基础研究发展规划项目（２００２ＣＢ３１２１０２）；国家“八六 三”高技术研究发展计划（２００６ＡＡ０１Ｚ３０６）；国家“／ｋ￣￣－－”高技术研究发展计划（２００６ＡＡ０１Ｚ３０６）；大学科研基金．李静，女，１９７２年生， 博士研究生，主要研究方向为计算机图形学．王文成，男，１９６７年生，博士，研究员，博士生导师，主要研究方向为科学计算可视化、虚拟现实． 吴恩华，男，１９４７年生，博士，研究员，博士生导师，主要研究方向为计算机图形学、真实感成像、虚拟现实、科学计算可视化． 维普资讯 http://www.cqvip.com ４２６ 计算机辅助设计与图形学学报 ２００７正 简单的运算来尽量排除那些不相交的边．其中文献 ［６］的方法是最快的，它通过对被裁剪线进行变换， １基于凸剖分的裁剪算法 １．１ 凸剖分及二叉树组织 使其平行ｘ轴，然后用同样的变换处理多边形的顶 点；由此只需进行ｙ坐标的检测就能得到相交的 边．这些方法要处理每条边，计算复杂度为０（ ）． 被裁剪线一般只与多边形的少数边相交．为 此，我们提出一种新的裁剪算法，避免处理许多不相 我们使用文献［７］的算法将多边形剖分成相对 于ｙ轴的单调多边形，并仿照其单调多边形三角化 的方法将各个单调多边形凸剖分，即可完成多边形 的凸剖分． 对于剖分的凸多边形，我们建立二叉树来管理， 即用与多边形边共线的直线（称为分割直线）进行空 间划分，使得凸多边形迭代地被分到分割直线的两 边（与分割直线相交的凸多边形要在左右２个子结 点中都存在）．这样选择分割直线是为了减少分割 直线与凸多边形相交的情况，以利于裁剪计算．二 叉树的中间结点存储分割直线，而叶子结点存储各 个凸多边形．如图１所示，图１ ａ所示为剖分的凸多 边形；图１ ｂ，１ Ｃ所示为生成的２个二叉树，其中，中 间结点存放分割直线所在边，叶子结点存放凸多边 形，以编号表示． 交的边，可自适应地降低计算复杂度．它先将多边 形进行凸剖分，然后建立二叉树来管理这些凸多边 形．与已有的基于凸剖分的算法…不同，本文算法 对凸多边形进行了高效的管理．这样，在进行裁剪 计算时，先根据二叉树找到与被裁剪线相交的凸多 边形，再利用凸多边形线裁剪方法进行裁剪计算． 这样可以避免处理许多不相关边，因为没有被处理 的凸多边形有许多原多边形的边，而利用高效的凸 多边形线裁剪方法也可避免处理一些边． 虽然本文算法需要预处理，但因为许多应用中 要相对于一个多边形进行很多的线裁剪计算，所以 该算法还是能发挥积极作用的，如３Ｄ动态场景中 的阴影线裁剪． ａ被凸剖分的多边形 ｂ较差的二叉树组织 ｃ较好的二叉树组织 图１ 凸多边形的二叉树组织示意图 由于２个子结点中都包含与分割直线相交的凸 多边形，所以会增加树结构的冗余．为去掉冗余并 使树结构尽可能平衡，以降低树的高度，提高裁剪时 剔除不相交凸多边形的效率，我们采用了下面２个 措施： 为提高选择速度，我们用一定的计算来定量地衡量 每个候选者，并设定一个阈值；然后，逐个考核候选 者，一旦得到满足阈值要求的，就以它为实际的分割 直线，不再考查其余候选者．这样虽然会略微降低 树的质量，但对裁剪效率的影响不大，且可将建树的 复杂度大幅度降低． １）建立三叉树来替代二叉树，即每个结点分成 ３个子结点，分别包含在其分割直线左边、右边及与 分割直线相交的凸多边形．显然，它是支持二分查 找检索的． ２）考查每条候选分割直线，衡量哪条能更好地 平衡左右子结点并减少中间子结点中的凸多边形个 数，由此来选择其中最好者为该结点的真正分割直 线．如图１ Ｃ中选择了好的分割直线，使得其树的高 度比图１ ｂ少一层． 衡量计算是根据位于一条候选直线左边、右边 及与它相交的凸多边形个数来进行的．设 Ｌ， 和 分别表示左侧集合Ｓ Ｌ、右侧集合Ｓ 和相交集合 Ｓ 中所包含的凸多边形个数，下面计算３个参数， 并以“选择度”的值最大者为分割直线． 纯净度（ｐｕｒｅ ｄｅｇｒｅｅ，ＰＤ）．ＰＤ＝（ Ｌ＋ Ｒ）／ （ Ｉ＋ Ｒ＋ Ｉ），用于考查一个分叉方案中ＳＩ的容 量，该值越大，则Ｓ。所带来的树的冗余部分就越少． 平衡度（ｂａｌａｎｃｅ ｄｅｇｒｅｅ，ＢＤ）．ＢＤ＝１一｝ Ｌ一 显然，以遍历的方式来选择分割直线是费时的． 维普资讯 http://www.cqvip.com ４期 李 静等：基于凸剖分的多边形窗口线裁剪算法 ４２７ Ｒ Ｊ／（ Ｌ＋ Ｒ），用于考查左、右子树是否平衡，该值 Ｏ（ ｌｏｇｎ）．后者的分析如下：设一个包含 个顶点 越大，则树越平衡． 的多边形被剖分成ｍ个凸多边形，且每个凸多边形 选择度（ｓｅｌｅｃｔｉｏｎ ｄｅｇｒｅｅ，ＳＤ）．ＳＤ＝ｍｉｎ（ＰＤ， 的边数平均为“．由欧拉公式可知Ｏ（ｍｕ）＝Ｏ（ ）． ＢＥ）），协调参数ＰＤ与ＢＥ）． 它对应的二叉树共有ｋ层，找出每一层所有结点的最 １．２裁剪计算 佳分割直线所需要的总时间分别为 （１≤ｉ≤ｋ）． 本文算法先根据二叉树找到很可能与被裁剪线 从根结点Ｒ包含的ｍ个凸多边形中找出最佳分割 段相交的凸多边形，然后根据这些找到的凸多边形 直线Ｓ需要的时间Ｔ ：Ｌ（ｍｕ） ，其中Ｌ是测试一 对被裁剪线段进行裁剪． 个点位于一条边哪一侧的计算开销，为常量． 在寻找很可能相交的凸多边形时，我们考查被 在找到Ｓ后，设位于Ｓ左侧、右侧和与其相交 裁剪线段的２个端点是否位于中间结点所对应分割 的多边形分别有ａ×ｍ，ｂ×ｍ和ｃ×ｍ个，其中， 直线的两边．如果是，则该结点的２个子结点都要 ａ，ｂ，Ｃ均为［０，１］间的实数，且ａ＋ｂ＋Ｃ：１．故 进一步的检测；否则，只需要进一步检测包含被趁剪 Ｔ２＝Ｌ（（ａ＋Ｃ）ｍｕ）２＋Ｌ（（ｂ＋ｃ）ｍｕ）２＝Ｌ（（口＋ 线段的那个子结点，而另一个子结点中的凸多边形 Ｃ） ＋（ｂ＋Ｃ） ）（ｍｕ） ．由于在选择分割直线时进行 则不需要参加后续的裁剪计算．如此迭代进行，直 了质量控制，因此一般有Ｃ ＜２ａｂ．所以，Ｔ，＜ 至达到树的叶子结点，就找到了很可能与被裁剪线 Ｌ（ａ＋ｂ＋ｃ） （ｍｕ） ＝Ｌ（ｍｕ） Ｔ１＝ｇ２ Ｔ１，Ｏ＜ 段相交的凸多边形． ｇ２＜１．类似地，Ｔ ＝ｇ （ —１）…ｇ２ Ｔｌ，ｉ＝３，４，…； 根据找到的凸多边形对被裁剪线段进行裁剪 设ｇ２，ｇ３，ｇ４，…ｇ …中最大者为ｇ，则建立二叉树 时，可选用各种高效的裁剪算法，如复杂度为０（１） ∞ 的凸多边形裁剪算法［引，但这种算法需要大量的空 的时间为∑ ≤Ｔ。∑ｇ 一 ＜Ｔ。∑ｇ 一 ＝ ＝１ ｉ＝１ ｆ＝１ 间存储预计算结果．为节约存储开销，我们将选用 Ｔ 没有额外空间需求且复杂度为０（１ｏｇｎ）的凸多边 ，其时间复杂度为０（（ｍｕ） ），即０（ ）． １一ｇ 形裁剪算法【２Ｊ．最后，综合被裁剪线段相对于所有 如果不以遍历的方式选择分割直线，则建树的 这些凸多边形的裁剪结果，得到该被裁剪线段相对 复杂度可降低很多．其分析如下： 于此多边形的裁剪结果． 首先，从一个结点所有的Ｃ条候选边中选择分 为进一步提高计算速度，我们采用了如下优化 割直线所需处理的直线数量将小于Ｃ，姑且记之为 技术： ．对于任意一条边Ｅ，其选择度的取值范围为［Ｏ， １）细分被裁剪线段．当被裁剪线段与一分割直 １］，故设ｆ（ｓ）为边Ｅ所对应的选择度的概率密度 线相交时，根据交点剖分被裁剪线段，然后再对各个 函数．由概率密度的定义可知，边Ｅ的选择度优于 剖分的部分在各自相关的子结点中分别进行后续的 ｒ１ 处理．这样能减少考查很多无关的结点，提高检索 阈值 的概率Ｐ（｛ｓ（Ｅ）≥ ｝）＝Ｉ ｆ（ｓ）ｄｓ，记之 Ｊｔｕ 速度． 为Ｐ１．由于 ，１皆为常数，因此Ｐ１亦为常数．由Ｐ１ ２）包围盒检测．相对于凸多边形裁剪时，先对 定义可知 ＝１的概率为Ｐ１， ＝２的概率为Ｐ１（１一 其包围盒进行检测，可以以较少的代价排除许多不 Ｐ１）， ＝３的概率为Ｐ１（１一Ｐ１） …．由概率论相关 相交的凸多边形． 定理易知， 的期望值为１／Ｐ．，为・常数．因此，从 ３）省略与新边的求交计算．对凸多边形进行裁 总边数为Ｃ的候选者中寻找分割直线所需的期望时 剪时，如果被裁剪线段与一个新边（为凸剖分而新加 间为Ｄ（Ｏｃ）＝０（Ｃ）． 的边）相交，则不计算该交点，因为该交点肯定属于 其次，由于树的形式由二叉变为三叉，任一多边 多边形内部． 形都不会在同一层次的不同结点中重复出现，因此 每一层次所有结点相关的凸多边形的边总数都相 ２算法分析 同，为ｍｕ＝０（ ），故计算每一层次所有结点的分 割直线需要的时间皆为０（ ）．又由于树的总层次 ２．１预处理的时间复杂度 数为Ｋ＝０（１ｏｇｍ），因此建立树结构总时间的期望 预处理时间包括２个部分：多边形的凸剖分和 值为ＫＯ（ ）＝０（ ｌｏｇｍ）．由于多边形凸剖分的 树结构的建立．根据文献［７］，前者的时间复杂度为 凸多边形数量与多边形凹点数ｒ呈线性关系，即 维普资讯 http://www.cqvip.com 计算机辅助设计与图形学学报 ２００７正 ０（ｍ）＝０（ｒ），因此该时间复杂度可改写为 ０（ ｌｏｇｒ），当凹点数很多，达到０（ ）级别时，时间 边形进行裁剪计算，此时的复杂度为０（ｍｌｏｇｕ）． 当ｍ为０（ ）时，０（ｍｌｏｇｕ）＝０（ ）．由于本文算 法的裁剪复杂度是与被裁剪线段关联的凸多边形个 复杂度即为０（ｎｌｏｇｎ）． 综上可知，预处理的时间复杂度最坏情况下为 Ｏ（ ），期望值为０（ ｌｏｇｒ）． ２．２预处理的空间复杂度 数相关的，而大多数情况下被裁剪线段不会与所有 的凸多边形相交．因此，本文算法在大多数情况下 的复杂度小于０（ ）． 在凸剖分过程中，剖分得到的凸多边形的个数 的复杂度是０（ ），空间复杂度也是０（ ）．树结构 的空间需求包括在树的中间结点存储的分割直线的 线方程（即线方程 ＝口 ＋ｂｆ中的参数ａ 和ｂｆ）和在 叶子结点存储的各个凸多边形的顶点序列．由于凸 多边形的个数的复杂度是０（ ），而树结构中所有 结点的数目与其叶子结点的数目呈线性关系，所以 树结构的空间复杂度是０（ ）．因此，本文算法的空 间复杂度为０（ｎ）． ２．３裁剪时间分析 ３对比实验 我们用Ｖｉｓｕａｌ Ｃ＋＋６．０实现了本文算法，并与 文献［６２算法进行对比．实验环境为ＡＭＤ Ａｔｈｌｏｎ６４＋ ２．４ＧＨｚ ＣＰＵ，１ ＧＢ内存的ＰＣ机．在实验中，我们 基于椭圆来随机生成多边形，即根据多边形的顶点 数目在椭圆上随机取点，并在这些点中选定一些点， 使它们沿着与椭圆中心的连线进行一定幅度的随机 位移来形成凹点．被裁剪线段在比多边形包围盒稍 大的矩形区域内中随机生成．本文设计了３组实验． 实验１．本文算法预处理时间、空间以及裁剪时 间随窗口多边形规模变化的情况．共有１０个随机多 边形参与实验，其边数由３００均匀地增长到３０００． 图２ａ～２ ｃ所示分别为预处理时间、辅助结构占用 本文算法的裁剪计算复杂度与具体的裁剪计算 密切相关，因为该算法是通过选取被裁剪线段附近 的凸多边形来进行裁剪计算．当被裁剪线段与绝大 部分凸多边形相交时，该算法要处理原多边形的大 部分边，此时的复杂度较高；反之则低． 最好情况时，本文算法通过树结构找到只有一 个凸多边形是与被裁剪线段相交的，其计算包括基 于树结构找到此凸多边形的计算和关于此凸多边形 的空间以及裁剪时间随多边形的边数变化的曲线， 其中裁剪时间是１ ０００条随机线段的平均裁剪时 间，随机线段的长度与裁剪窗口多边形的边长度相 近．作为对比，图２ ｃ中也绘制了文献［６］算法的裁 的线裁剪计算．容易推出，此时的复杂度为Ｏ（１ｏｇｍ＋ ｌｏｇｕ）＝０（１ｏｇ（ “））＝０（１ｏｇｎ）． 剪时间曲线．实验结果表明，本文算法比文献［６］算 法降低了计算复杂度． １５ ＼ 最坏情况时，被裁剪线段需要相对于所有凸多 ５ｏ０ ∞５０ ４００ ３００ 兰４０ 厘９ 厘３０ 詈： 多边形边数 ａ预处理时间随窗口 多边形边数的变化 ：亲￣制２。。。００ 蓉ｅ 箍３ ０ 蓉２０ 箍１０ ０ ０ 多边形边数 ｂ空间随窗口多边形 边数的变化 多边形边数 ｃ裁剪时间随窗口多边形 边数的变化 被裁剪边长度／％ ｄ裁剪时间随被裁剪线 长度的变化 图２本文算法性能实验结果 实验２．被裁剪线段长度对于裁剪时间的影响． 实验中以一个边数为２４００的随机多边形作为窗口． 被裁边分为１１组，每组１０００条边，每组的边长与窗 口包围盒对角线的长度之比从０．０１变化到０．９９． 图２ ｄ所示为各组的平均裁剪时间随被裁边长度变 实验３．本文算法在具体应用之一——多边形 窗口的多边形裁剪中的性能．实验中所用模型如图 ３所示，表１所示为本文算法和文献［６］算法完成这 些操作需要的总时间（即将被裁剪多边形的每条边 相对于裁剪多边形窗口进行裁剪计算的总时间）． 实验结果显示，即使加上预处理时间，本文算法的性 能也比文献［６］算法分别提高了１．４２倍和９．３６倍． 化的曲线．实验结果表明，本文算法可自适应地降 低计算复杂度，且被裁剪线越短，＇速度越快． 维普资讯 http://www.cqvip.com ４期 李静等：基于凸剖分的多边形窗口线裁剪算法４２９ ａ多边形窗口 ｂ被裁剪多边形 ｃ被裁剪多边形位于 裁剪窗口内的边 图３多边形窗口对多边形裁剪的实验结果 ４ 结 语 本文提出针对一般多边形的线裁剪算法，能根 据裁剪计算的具体情况自适应地降低复杂度．该算 法将多边形进行凸剖分，并建立二叉树来管理剖分 的凸多边形，以便裁剪计算时可根据二叉树快速找 到与被裁剪线段很可能相交的凸多边形，再使用高 效的凸多边形裁剪算法进行裁剪计算．对于一个有 条边、ｒ个凹点的多边形，本文算法的预处理时间 复杂度的期望值为０（ ｌｏｇｒ），线裁剪计算的复杂 度在０（１ｏｇｎ）与ｏ（ ）之间自适应地变化，且大部 分情况下是小于０（ ）、甚至接近０（１ｏｇｎ）的．实验 结果表明，本文算法能很好地提高裁剪速度，并在一 些应用（如多边形窗１２１对多边形的裁剪）中即使包括 预处理的执行速度，依然要比不需要预处理的同类 裁剪算法快很多． 参 考 文 献 ［１］Ｒｏｇｅｒｓ Ｄａｖｉｄ Ｆ．Ｐｒｏｃｅｄｕｒａｌ ｄｅｍｅｎｔｓ ｆｏｒ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ ［Ｍ］．２ｎｄ ｅｄ．Ｂｅｉｊｉｎｇ：Ｃｈｉｎａ Ｍａｃｈｉｎｅ Ｐｒｅｓｓ．２００２ ［２３ Ｓｋａｌａ Ｖ．Ｏ（１ｇＮ）ｌｉｎｅ ｃｌｉｐｐｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｎ Ｅ ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ ＆Ｇｒａｐｈｉｃｓ，１９９４，１８（４）：５１７—５２４ ［３］Ｓｋａｌａ Ｖ．Ｌｉｎｅ ｃｌｉｐｐｉｎｇ ｉｎ Ｅ ｗｉｔｈ ｏ（１）ｐｒｏｃｅｓｓｉｇｎ ｃｏｍｐｌｅｘｉｔｙ ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆Ｇｒａｐｈｉｃｓ，１９９６，２０（４）：５２３—５３０ 【４］Ｌｉｕ Ｙｏｎｇｋｕｌ，Ｙａｎ Ｙｅ，Ｓｈｉ Ｊｉａｏｙｉｎｇ．Ａｎ ｅｆｆｉｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｌｉｎｅ ｃｌｉｐｐｉｎｇ ａｇａｉｎｓｔ ａ ｐｏｌｙｇｏｎ［Ｊ］．Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ，１９９９，２２（１１）：１２０９—１２１４（ｉｎ Ｃｈｉｎｅｓｅ） （刘勇奎，颜叶，石教英．一个有效的多边形窗ＩＺｌ的线裁剪 算法［Ｊ］．计算机学报，１９９９，２２（１１）：１２０９—１２１４） ［５］Ｌｕ Ｇｕｏｄｏｎｇ，Ｘｉｎｇ Ｓｈｉｈａｉ，Ｐｅｎｇ Ｑｕｎｓｈｅｎｇ． Ａｎ ｅｆｆｉｃｉｅｎｔ ｌａｇｏｒｉｔｈｍ ｏｆ ｌｉｎｅ ｃｌｉｐｐｉｎｇ ａｇａｉｎｓｔ ｐｏｌｙｇｏｎａｌ ｗｉｎｄｏｗ ｂａｓｅｄ ｏｎ ｔｈｅ ｖｅｒｔｅｘ ｅｎｃｏｄｉｎｇ［Ｊ］．Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ，２００２，２５ （９）：９８７—９９３（ｉｎ Ｃｈｉｎｅｓｅ） （陆国栋，邢世海，彭群生．基于顶点编码的多边形窗口线裁 剪高效算法［Ｊ］．计算机学报，２００２，２５（９）：９８７—９９３） ［６］Ｈｕａｎｇ Ｙ Ｑ，Ｌｉｕ Ｙ Ｋ．Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｃｌｉｐｐｉｇｎ ａｇａｉｎｓｔ ａ ｏｐｌｙｇｏｎ ｂａｓｅｄ ｏｎ ｓｈｅａｒｉｎｇ ｔｒａｎｓｆｏｒｍａｔｉｏｎ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｆｏｒｕｍ，２００２，２１（４）：６８３—６８８ ［７］ｄｅ Ｂｅｒｇ Ｍａｒｋ，Ｏｖｅｒｍａｒｓ Ｍａｒｋ．Ｃｏｍｐｕｔａｔｉｏｎａｌ ｇｅｏｍｅｔｒｙ： ｌａｇｏｒｉｔｈｍｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．２ｎｄ ｅｄ．Ｂｅｄｉｎ：Ｓｐｒｉｇｎｅｒ． ２０００
