动态计算圆弧并面积算法的证明及改进

动态计算圆弧并面积算法的证明及改进 V o l. 13, N o. 1 第 13 卷 第 1 期计算机辅助设计与图形学学报 2001 年 1 月J an. , 2001 JOU RN A L O F COM PU T ER 2A ID ED D E S IGN & COM PU T ER GRA PH IC S 动态计算圆弧并面积算法的证明及改进 袁平鹏陈刚董金祥 ( ) 浙江大学 国家重点实验室 杭州 310027CA D & C G ( ) 浙江大学人工智能研究所 杭州 310027 6 摘 要 陈建勋等给出了一个优美的圆弧并面积计算的算法. 文中对该算法的正确性予以证明, 使该算法更完 善. 基于推理所得结论, 对该算法作了改进, 降低了计算复杂度. 关键词 圆弧并面积, 算法正确性, 关联扇形组, 计算几何 中图法分类号 391T P Prove an d Ref in em en t of A lgor ithm f or D ynam ic Com put in g Un ion A rea of C ircula r A rc s 22YU A N P in gP en g CH EN Gan g DON G J in X ian g (), , 310027S ta te K ey L abora tory of CA D & CG Z h ej iang U n iv ersity H ang z h ou ( ), , 310027I nstitu te of A r tif icia l I n tel l ig enceZ h ej iang U n iv ersity H ang z h ou 6 2, C h en J ian X u n e t a lp ropo sed su ch an a lgo r ithm fo r com p u t in g th e u n io n a rea A bstra c t w itho u t g iv in g a t te sta t io n o f it s va lid ity. T h is p ap e r p ro ved th e va lid ity o f th e a lgo r ithm redu ced .th e com p lex ity o f com p u ta t io n , , , Key word s u n io n a rea o f c ircu la r a rc sva lid ity o f a lgo r ithm g ro up o f re levan t sec to r scom p u2 .ta t io n a l geom e t ry 精度无关, 算法适用性和交互性好的特点. 该算法主 要思想是: 将平面上任意方式放置的个圆所覆盖 N 1 引言 区域划分成一系列小区域, 这些小区域不相交, 累计 平面上以任意方式放置的 个圆所覆盖区域 这些小区域的面积便可得到平面上圆域的并面积. N 面积的计算问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 称为圆弧并面积的计算问题. 它不 因此, 这些小区域的存在与否以及小区域间是否存 但是计算几何、ƒ中的基础性算法, 而且在重叠, 对该算法的可靠性是至关重要的. 文献1 CA D CAM 1- 5 该问题具有很强的应用背景. 在军事上, 将此模中对以上两个关键问题没有给出回答, 因此这种计 型应用于机场布置, 如果布置合理, 就可以用最少量 算圆弧并面积的算法是有缺陷的, 圆弧并面积算法 的资源达到最大范围国土防空的目的. 此外, 在商业 的正确性便没有得到保证. 本文对以上两个问题作 区的布置以及城市的经济、文化生活影响范围等都 出了回答, 从而证明了文献1 中计算圆弧并面积算 涉及到圆弧并面积的记算问题, 对经济、文化的评估 法的正确性, 使该算法更完善. 由于该算法中的基本 有着一定的意义. 操作是圆域求交以及区域求并, 在证明的基础上, 本 文献6 给出了一个优美的圆弧并面积计算的 文对该算法中求交运算及归并区域操作进行了改 算法, 该算法具有计算时间复杂度与圆的大小、计算 进, 大大降低了计算复杂度, 提高了计算精度. 原稿收到日期: 1999210208; 修改稿收到日期: 2000202214. 袁平鹏, 男, 1972 年生, 博士研究生, 主要从事 PDM 、计算机图形学等方面的研 究. 陈 刚, 男, 1973 年生, 副教授, 主要研究方向为 、人机交互等. 董金祥, 男, 1945 年生, 教授, 博士生导师, 主要研究方向为 , PDM CA D 、数据库等.C MI S ??Ø , 则可将 , 合并成一个大区域, 这个S 1 S 2 S 1 S 2 大区域称为扇形 与 所形成的扇形组 , 即 S 1 S 2 G 2 概念定义 Α , Α , ?= . 扇形组亦为一扇形, 但其 S 1 G S 2 G S 1 S 2 G 平面上圆之间的关系有 4 种: 相离、相切、相交不一定是两相交圆所形成的扇形. 扇形组关系是一 和包容. 圆的相切有 2 种情况: 内切和外切. 为简化 等价关系. 处理, 在本文中将圆内切情况归之于包容, 将圆外切 一扇形可包含于一系列扇形组, 这一系列扇形 组有大有小. 设包含扇形 的扇形组集合为 , S 1 S G 情况视为相离. 因为在圆弧并面积计算问题中, 相离= {Α }. 如果ϖ?, Π?, Β , |S G G i S 1 G i G i S G G j S G G i G j 的情况可简单地加上同其它圆分离的圆的面积, 而 则扇形组 称为扇形 所在扇形组中的最大扇形 G i S 1 圆包容另一圆的情况则只需抛弃被包含的圆, 在计 组. 如果ϖ?, 且 Α , Π?, ⁄ . 则 G i S G S 1 G i G j S G G i G j 算并面积过程中, 不计入被包含的圆面积. 因此, 在 扇形组 称为扇形 所在扇形组中的最小扇形组. G i S 1 最大扇形组只有一个. 求最大扇形组的算法如下: 本文中主要考虑圆相交的情况. 算法 1. 求最大扇形组定义 1. 圆的方向. 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 沿着圆的周径绕圆一 设圆 O 中扇形的集合为 Α= {S | S Α O , S 是一扇形},周, 圆的内侧在左边时, 此方向为圆的正向. 反之, 为 存储最大扇形组.Gm ax 圆的逆向. 正向也就是逆时针方向, 逆向为顺时针 1. 取任意扇形 ?, = ; = - {}.S tep s0 ΑGm ax s0ΑΑs0 方向. 2. 取扇形 ′?, 如果 ′??Ø , = - {′}, S tep sΑsGm ax ΑΑs定义 2. 扇形. 由一段圆弧和两条半径围成的 = ′?.Gm ax sGm ax 区域称为扇形. 围成扇形的两半径称为扇形的边. 圆 3. 执行 直到Π ?, ?= Ø . 此时 2, S tep S tep sΑsGm ax Gm ax 是 所在扇形组中的最大扇形组.s0 是一种特殊的扇形. 本文仅考虑两圆相交所形成的 4. 如果 ?Ø , 执行 否则, 即为最大扇 1; S tep ΑS tep Gm ax ( 扇形 在下面讨论中, 如不特别注明, 均指此类扇 形组. ) 形, 也即扇形两边与圆弧相交的端点是与另一圆相 该算法是可 终 止 的, 因 为 是 有 限 集; 其 次 Α 交所得的交点. 扇形的顶点是边与边或边与弧的交 中求得的每一个新的 值都包含了与原 2 S tep Gm ax 点, 其中边与弧的交点就是与另一圆的交点. 如图 1 存在非空的交集的扇形区域. 根据最大扇形组 Gm ax 中扇形, 分别是圆与圆、圆相 O 0A D O 0B E O 0 O 1O n 的定义, 算法所得的结果亦是正确的. 交所得的扇形. 扇形组相应的扇形的两边称为扇形组的边. 扇 形组的角度是扇形组两边的夹角. 当一个圆的扇形 组的角度为 2, 该圆域完全被其它圆所包容. 角时Π 度为 0 时, 此圆域同其它圆分离. 依以上所讨论, 这 两种情况分别作为包容和相离处理. 图 1 中 , 和 都 是 扇 形 组,O 1A D O 0A D O 0A E 是所在扇形组中的最大扇形组. O 0A E O 0A D 定义 5. 关联扇形组. 对于扇形 1 , 2 , 圆1 , 2S S O O 以及扇形组 , , 如果 Α , Α , Α , G 1 G 2 S 1 O 1 S 2 O 2 S 1 G 1 S Α , 且 , 关联, 则扇形组 , 相互关联. 扇2 G 2 S 1 S 2 G 1 G 2 形组 是 关联扇形组, 反之扇形组 亦是 G 1 G 2 G 2 G 1 关联扇形组. 定义 3. 关联扇形. 两圆, 相交时, 两圆圆 O 1 O 2 扇形所在的扇形组有多个, 因此关联扇形组可 心与两交点的连线与其所夹的弧构成两扇形 F 1 ,能有多对. 但最大关联扇形组只有一对. 当一个圆的 扇形组的角度为 0 或 2, 它的最大关联扇形组不 时Π , 这两扇形称为相互关联. 是 的关联扇形,F 2 F 1 F 2 存在. 在图 1 中, 是关联扇形组, , O 1A D O 0A D O 0A E 反之, 亦是 的关联扇形. 两相互关联扇形的四 F 2 F 1 , 是最大关联扇形组.O 1A F O n E F 边可围成一四边形, 该四边形称为关联扇形的四边 形. 图 1 中扇形, 是关联扇形. O 0A D O 1A D O 0A D O 1 定义 6. 空区. 不包含任意圆的区域称为空区. 是关联扇形, 的四边形.O 0A D O 1A D 也即未被任意圆覆盖的区域. 定义 4. 扇 形 组. 对 于 圆 中 扇 形 , , 若 S 1 S 2 1 期袁平鹏等: 动态计算圆弧并面积算法的证明及改进69 S tep 2. i= i+ 1. 3. 以与该圆的一最大扇形组的一边相交的圆作为 S tep 3 算法正确性证明下一结点.OL i 4. 反复进行 直到出现重复结点为止.2, 3, S tep S tep 有了以上讨论的基础, 现在可以论证平面上任该算法一定可以终止, 因为圆的数目有限; 其次 意个圆是否可划分为一系列不重叠的区域, 这里先 该算法执行结束时, 一定得到一个环路. 也即遇到起 证明几个结论. 始结点而终止. 假设不是遇到起始结点而终止, 设遇 定 理 1. 最大关联扇形组一定可围成一个多 ( ) 到结点而终止 见图 2, 可知结点 的度数 OL j OL j 边形. 为 3, 因此相应的最大关联扇形组有三条边, 显然矛 证明. 分两步证明. 盾. 因此, 遇到起始结点而终止.() 1最大关联扇形组的边中至少有一对边相交 最后, 算法所得的图一定包含所有关联扇形组 于一点, 这一点就是两扇形组所在的圆的一交点. 所属的圆. 若有圆未在图中出现, 则该圆没有扇形 如图 1, 设为圆 扇形 , 所 O 0A E O 0 O 0A D O 0B E 组与其它圆的扇形组关联. 因为如果该圆有扇形组 形成的扇形组集合中的最大扇形组, , 为扇O 0A O 0 E 与其它圆的扇形组关联, 则该圆的圆心存在两条路 形组 的两边. 与扇形 相关联的扇形O 0A E O 0A D 径与其它圆圆心相连, 根据以上算法该圆一定会出 O 1A D 位于圆 O 1 中, 现在需要证明边 O 1A 是扇形 现在图中. 所在最大扇形组的一边.O 1A D 假设 不是扇形 所在最大扇形组的O 1A O 1A D 一边.那么, 一定存在一扇形 与扇形 重叠 S O 1A D 或相邻, 且该扇形 的一边位于 之外, 另一边 S O 1A 位于 之内. 设扇形 在圆 圆周的两端点为O 1A S O 1 , . 因此, 存在过点 , 的一圆 与圆 相 P 1 P 2P 1 P 2 O O 1 交, 圆与圆的一交点位于点之外, 另一交点O O 0 A 位于点之内. 因此, 圆与圆相交所得的扇形A O 0 O 一定与扇形 重叠或相邻, 该扇形属于扇形组O 0A D . 由它与扇形 的位置关系, 可知边 O 0A EO 0A D O 0A 不是扇形组的一边. 与已知矛盾, 因此边O 0A E O 1A 是扇形所在最大扇形组的一边. O 1A D () 2最大关联扇形组的边一定可围成一多边形. 最大关联扇形组边之间的关系有两种情况, 一 种情况下两最大关联扇形组的边相交于两最大关联 定理 2.最大关联扇形组围成的多边形不包含 扇形组所在圆之间的交点, 此时, 两最大关联扇形组 任何空区.围成的多边形是关联扇形形成的四边形. 另一种情 由定理 1 可知, 多边形包含的区域同最大关联况则是这两条边与另不同的两圆相交于圆周. 扇形组包含的区域相同, 因此只要证明关联扇形组 最大关联扇形组的每一顶点的度为 2, 因为每 不包含空区即可证得结论. 一顶点有且只有两条边同它相连, 边构成一图. 为证 不失一般性, 从平面上 个圆中任意选择一 N 明最大关联扇形组的边可围成一多边形, 只要从某( ) 圆, 设为, 考虑与圆相交的 1Φ Φ - 1个O 0 O 0 n n N 一顶点出发, 沿最大关联扇形组的边周游. 如果能回 圆, , , , 且, , , 与圆相交所得 O 1 O 2 O n O 1 O 2 O n O 0 到初始点, 则找到一条通路, 可围成一多边形. 现构 的扇形 , , , 之间相互重叠或相邻. 扇形 F 1 F 2 F n ( 造如下算法寻找通路 最大扇形组同它所在的圆 G , 可合并成一个扇形组. , , F n F 1 F 2 是对应的, 算法中将最大扇形组视为它所在的圆, 这 假设圆 与圆 , 相交所得的两扇形分别 O 0 O i O j 个为叙述方便而作的简化不会影响算法所得结论的 ( )为 , 0< , < + 1. , 的位置关系有两种 F i F j ij n F i F j ) 正确性: 情况: 相交和相离. 针对这两种情况, 分别讨论之. 算法 2.求最大扇形组通路7 ( )1 若 , 相交, 由圆的凸性 F i F j , 形成两重叠选定任一圆作为起始结点, = 0. 1. S tep O OL 0 i 扇形的 3 个圆之间一定两两相交, 在 3 个圆之间不上个圆所覆盖的区域划分成若干不相交的区域, N 可能存在空区. 因为若存在空区, 一定可作一条直 然后累加这些区域的面积, 便得到个圆所覆盖的 N线, 把其中两圆分开, 因而 3 个圆不两两相交, 从而 区域的并面积. 因此, 在圆域并面积计算算法中基本与圆相交所得的扇形 , 必不重叠或相邻. 与 O 0 F i F j 的操作就是圆的求交以及区域的归并. 如何简化求 假设矛盾. 交运算及归并区域是改进算法的关键. 在圆域并面 () 2若 F i , F j 分离, 由扇形组的定义可知, F i , F j积计算中, 如果知道交点与 轴正向的角度将会使 x 相关运算大大简化. 因为扇形的角度在归并区域过 ( ) 0 < < - , 之间一定存在扇形 , F i jm m n 1, 这F i j 1 程中判断区域是否相交是很简便的, 并且交点的坐 些扇形或者与 相互重叠或相邻, 或者与 相互 F i F j 标值根据圆的参数方程亦很容易求得. 现在推导圆周上任意点与 轴的夹角. 基于圆 x 重叠或相邻, 或者相互之间重叠或相邻, 使 , 可F i F j 的参数方程, 很容易推得交点的参数 的正弦余弦 Η归并到同一扇形组中. 因此一定可从扇形 , , F i j 1 8值. 圆的参数方程如下 () 中找出一扇形 0< < + 1与 相重叠或 F ijm F ij k k m F i x = r co s Η+ x ,0 ( ) 相邻. 由 1所得结论可知, 扇形 及 的关联扇 F ij k F i 形所对应的两圆与圆 之间不存在空区. 同理, 可 O 0 y = r sin Η+ y .0 找出与 重叠或相邻的扇形, 这样继续下去, 直到F i j k ) (其中, 为圆的半径, , 为圆心坐标.r x 0 y 0 与 重叠或相邻. 因而扇形 , , , , 的 F j F i F i j 1 F i jm F j 关联扇形所对应的圆与圆之间无空区. 由于 , O 0 F i 3 所示, 点为圆1′ , 2′ 的交点, 垂直于 如图 C O O C P () () 为任意扇形, 由 1, 2可得与圆 相交的 个F j O 0 n 直线1 ′ 2′. 圆1′ 的半径为 1 , 圆2′ 的半径为 2. 两圆 O O O r O r 圆, , , 之间不存在空区. O 1 O 2 O n 间的距离|′′| 设为 , |′| = 1 2 1 , ?1 ′ ′2 = .由O O d O P tCO O Α 圆是任意的, 因此可得平面上 个圆每个 O 0 N 图 3, 可得下式 圆和与之相交的圆所得的最大关联扇形组围成的多 从而, 平面上 个圆形成的边形不包含任何空区.N 最大关联扇形组围成的多边形不包含任何空区. 定理 3. 平面上任意个圆的并面积可 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为若 干个扇形和多边形面积之和. 证明. 平面上圆之间的位置关系有 4 种: 相离、 相切、相交、包容. 圆的相切有两种情况: 内切和外 切. 内切可归之于包容, 外切可视为相离. 相离时没 有与其它圆发生重叠, 该圆视为一个独立的区域. 在 圆弧并面积计算问题上, 可简单地加上该圆的面积, 而圆包容另一圆的情况则只需抛弃被包含的圆. 如果圆同其它圆相交, 根据定理 1, 该圆可划分 2 2 2 2 成若干个互不相交的最大扇形组和扇形, 这些最大 ) ( - r- rt = d - t , 1 2 2 2 2 2 2 关联扇形组可围成一多边形. 由于最大扇形组同圆 () - r- d + t - 2d t, rt = 1 2 2 2 2 的其它区域不重叠, 因此最大关联扇形组围成的多 r+ d - 1 r2t = . 2d 边形亦不同该圆的其它区域重叠. Α= tƒr, co s 1 所以,综上可得, 平面上任意个圆的并面积可表示为 若干个扇形和多边形面积之和. 由定理 1, 2 可知, 对 2 2sin Α= ? 1 - tr. ƒ1 平面上任意个圆所覆盖区域存在一个划分, 划分N 设圆′, ′两交点分别为 , , 由于两圆的交 O 1O 2C 1 C 2 所得的区域间不重叠. 因此文献1所提出的计算圆点对称地位于直线′′的两侧, 位于直线′′的 O 1O 2C 1 O 1O 2 弧并面积的算法是正确的.上方, 位于直线′′的下方. 于是由对称性, 可得 C 2 O 1O 2 , 两交点的参数值 , 的正弦余弦值分别C 1 C 2 Α1 Α2 4 对算法的改进 如下 co sΑ= co sΑ= tr,ƒ1 2 1 圆弧并面积计算算法的基本思想, 就是将平面 1 期袁平鹏等: 动态计算圆弧并面积算法的证明及改进71 再需要, 这样将大大减少交点的坐标值计算量, 同样2 2 Α= 1 - tr1 ,sin ƒ1 扇形的角度也只需计算最大扇形组的角度. 因此上 2 2 1 - tƒr. sin Α= - 1 2 述方法将大大降低运算复杂度, 并且极大地方便了 依据圆的方向定义, 方向弧为正向弧. C 2C 1 区域的归并. ( )将上面所得的结果推广到一般情况 见图 4. ( ) 平 面 上 圆 O 1 , O 2 圆 心 的 坐 标 分 别 为 x 1 , y 1 和5 结论 () 图 3 的坐标系可, , 矢量 的方向角为 . x 2 y 2 O 1O 2 Β 本文给出了文献1 中动态计算圆弧并面积的看作由图 4 坐标系逆时针旋转 角, 再作平移得到, Β 8 算法的一个正确性证明. 证明了对平面上任意个圆 因此交点角度 = - . 于是可得ΗΑΒ 存在一个划分, 并且划分所得区域之间不存在重叠, co sΗ= co s Αco s Β + sin Αsin Β, sin Η= sin Αco s Β - co s Αsin Β. 从而论证了文献1 中的圆弧并面积计算算法是正 确的. 并且针对文献1 中算法运算复杂这一问题, 对它进行了改进, 降低了算法的计算复杂度, 提高了 算法的计算精度. 参 考 文 献 1 L ee Y T , R equ ich a A A G. A lgo r ithm s fo r com p u t ing th e vo l2 : um e and o th e r in teg ra l p rop e r t ie s o f so lid s IKnow n m e tho d s ( ) . , 1982, 25 9: 635 -and op en issue sComm un ica t io n o f A CM 641 , . 2 L ee Y T R equ ich a A A GA lgo r ithm s fo r com p u t ing th e vo l2 um e and o th e r in teg ra l p rop e r t ie s o f so lid s II: A fam ily o f a lgo 2 r ithm s ba sed o n rep re sen ta t io n co nve r sio n and ce llu la r app ro x i2 根据上式可以容易求得圆的两交点的参数值( ) . , 1982, 25 9: 642- 650m a teComm un ica t io n o f A CM , 的正弦、余弦值.Η1 Η2 , . C a t tan i C P ao luzzi ABo unda ry in teg ra t io n o ve r linea r po lyh e2 3 ( ) 135 d ra l. Com p u te r2A ided D e sign , 1990, 22 2: 130- co sΗ= Αco s Β + Αsin Β, co s sin 1 1 1 4 H iro sh i Sak u ra i. V o lum e decom po sit io n and fea tu re reco gn it io n: sin Η= sin Αco s Β - co s Αsin Β, 1 1 1 22. , 1990, 27 P a r t IPo lyh ed ra l o b jec t sCom p u te rA ided D e sign co sΗ= co s Αco s Β + sin Αsin Β, 2 2 2 ( ) 11: 833- 943 sin Η=sin Αco s Β -co s Αsin Β.2 2 2 5 . :H iro sh i Sak u ra iV o lum e decom po sit io n and fea tu re reco gn it io n 1990, 28 P a r t II2Po lyh ed ra l o b jec t s. Com p u te r2A ided D e sign , () y y 2 -1 ,因为sin Β= ( ) 6ƒ7: 519- 537 d 6 C h en J ian 2X un, M a H eng2T a i. A new a lgo r ithm fo r dynam ic ) (x x -1 2 . co s Β= com p u t ing th e a rea o f un io n o f c ircu la r a rc s. Jo u rna l o f Com p u t2 d ( ) 2, 1998, 10 3: 221 - 226 e rA ided D e sign & Com p u te r G rap h ic s因此 , 的正弦及余弦将只需基本的四则运 Η1 Η2 ( )in C h ine se 算便可求得. 扇形区域相交与否也只需根据扇形两 ( 陈建勋, 马恒太. 动态计算圆弧并面积的一个新算法. 计算机( ) )辅助设计与图形学学报, 1998, 10 3: 221- 226 弧上的顶点的 , 的正弦及余弦值便可很容易判Η1 Η2 , . : P rep a ra ta F P Sh am o s IM Com p u ta t io na l Geom e t ryA In t ro 2 7 ( () )断, 此外可得扇形的角度 = - . 根 Χa rc sin sin Η1 Η2 2. : , 1985duc t io nN ew Yo rkSp r inge rV e r lag 据圆的参数方程亦可很容易求得交点的坐标值. 因 222, , . T ang Ro ngX iW ang J iaYeP eng Q un Sh engCom p u te r 8 此, 根据点的参数 值, 可求得在圆弧归并及区域面 Η( ). : , 1994 G rap h ic s T u to r ia lB e ijingSc ience P re ssin C h ine se ( 唐荣锡, 汪嘉业, 彭群生. 计算机图形学教程. 北京: 科学出版 积计算中需要的数据. 在区域归并时, 大量交点由于 )社, 1994 被区域包含而消失, 从而在圆弧并面积计算中已不