您好、欢迎来到现金彩票网!
当前位置:2019正版免费全年资料 > 凸包逼近 >

一种用圆弧逼近三次平面BEZIER曲线的算法

发布时间:2019-07-25 01:55 来源:未知 编辑:admin

  一种用圆弧逼近三次平面BEZIER曲线的算法_IT/计算机_专业资料。等值线 绘制与光滑 bezier

  维普资讯 第 1 6卷 第 1 0期 19 9 3年 l O月 计 算 机 学 报 CHI ES J N E .COM PtTERS J Vo .1 , I No. 0 6 1 Oc .. 9 3 t 1 9 、] ] 76~ 8 1 . 1 一 种 用 圆 弧 逼 近 三 次 平 面 B z r曲线i e 张林 波 中国科 学院计 算 中心 . 京 I I 北 U ̄ O 中国科学 院 系统科学 母 所 , 京 1 幛O f 甓 北 ∞ \摘 要 本 络 一 用 弧 近 次 面& 曲 的 法. 算 的 文 出种圆逼 三平 线算 该法特 点 是 能 保 特 曲 线 的 整体 光 滑 性 , 用 圆弧 数 量 少 , 可 对 逼近 精 度 进 抒 控 制 .该 所 并 算法稍加变化后也适用于用婴弧逼近其它类型的平面曲线 . ~ √ 关麓词 双 堡兰 , 簦蝼 , 鐾面 墨塾里 堂 AN ALGORI THM FOR APPROXI ATI M NG CUBI C B  ̄ ER IZI CURVES W I H RC T A S Ch n iln a g J n lg l i t S  ̄ m*S i c,Acde aSil .Be ig 1 0 8  ̄gueo y e t f c ̄ e a mi nc a i n 0 0 0 j Z a g Li b hn n o C p t. C n r , a e a S n c , i g 1 0 8  ̄ u 1g e t e Ac d mi i i Be a  ̄n 0 0 0 Ab t a t s r c A t o n t e b a e a p o i to fc b c B∈ ir c r es me h d o h lr p r x ma i n 0 u i ze u v s i — d s rb d I i tman an n h mo h e so h e u n u v n e e c ie ? ta ms a it i i g t e s ot n s ft e r s hi g c r e a d r . d e n h u b rof r sr q ie o g v n p e iin Thi t od c n a s u ig t e n m e c e ur d f r a ie r cso s me h a 1 0 b at poia te t e0aa cre. e dp t a rx t0hry s f J r uvs a e op d m e p p n Ke ywor s d Bir p r x ma i n,  ̄ irc r e , ompu e r p i s a c a p o i to B ze u v s c t rg a h c . 本 文 1 驰 年 9月 船 日敉捌 ?嚣量砖 , 9 时编 . 从事 计算机 编辑捧 颇工 作张 #、 盖 计算 漉体算 法方 面的 研究工 作 . . 副 研 究 员 , 博 士 学 位 , 要 从 事 获 主 维普资讯 1 期 0 常 盎玲 等 :一 用 圆弧逼 近 三次 平面 B z r曲线 的算 法 种  ̄i e 1 引 言 . 计 算 机 图形 处 理 中 经常 用 到 各 种 不 同类 型 的 曲线 , B样 条 、 ̄ir曲线 、 弧等 . 如 Bz e 圆 不 同 的计 算 机 软 件 及 图 眵 设 备 往 往 支持 不 同 的 曲 线 类 型 . 此 我 们 经 常 碰 到 将 一 种 类 型 的 因 曲线 转 换 成 另一 种类 型 , 用 一 种类 型 的 曲 线 逼 近 另 一 种 类 型 的 曲线 的 问题 . 文 考 虑 用 或 本 分 段 圆 弧来 逼 近 光滑 平 面 曲线 的 算 法 . 算 法 可 有 以 下 两 方 面 的 应 用 : ) 乎 所 有 的 图 形 该 1几 软 件 均 将 圆 弧 作 为基 本 线 型 , 用 该 算 法 可通 过 将 任 意 曲 线 用 圆 弧 逼 近 来 实 现 不 同 图 形 应 格 式 间 的转 换 ( 将 P sS r t 言描 述 的 图 形 或 字 符 轮 廓 转 换 为 Auo AD 的 DXF格 如 otci 语 p tC 式 ) 2 许 多 绘 图 仪 有 直 接 画 圆 弧 的 命令 , ;) 当绘 制 一段 光 滑 曲线 时 , 其 用 一 串 圆 弧 逼近 比 将 用折 线 段 逼近 可 大 大 减 少送 往 绘 图 仪 的 数据 量 并 得 到 更 为光 滑 的 结 果 . 们 在 本文 中 虽 我 然 仅 就 三 次 平 面 l ir曲线 来描 述 我 们 的 算 法 , 不 难 将 其推 广 到 其 他 曲 线 的情 形 .  ̄z e 但 有 关 圆弧 样 条 及 圆 弧逼 近 在 国 内 外 已做 过 不少 研 究 . 要结 果 可 参 看 [ ] E 及 其 中 主 3 ,C 列举的有关文献. 本文 从 另 一 角 度 推 导 出双 圆 弧逼 近 的 计 算 公式 , 给 出 了逼 近 误 差 的 一 并 种 估计 方 法. 2 基 本 思 想 . 平 面三次 B z r曲线 由其特 征多边形的四个顶 点 , , :  ̄i e p和 确 定( 中 P ( , 其 “ Y )一0 1 2 3 , 图 1 示 , 参 数 方 程 为 : , . , , )如 所 其 3 p B( D一 ( f , ) ()() 一 ( -t卜 ,t o 1 ( ) 1 ) E[ ,] 1 有关 Bz r  ̄i 曲线的基 本性 质可参看 [ ] [ ] 其有 e 1 ,2 及 关参 考 文 献 . 文 中 需 要 用 到 下 述 性 质 : 本 1 口( ) P。 口( ) P . ) 0 一 , 1 一 2 口() ) f在一 0 的 切 线 方 向 为 P -p , 在一 1 处 。而 处 的 切 线 方 向 为 P -p . 3 曲线 B()t [ ,] 含 于 集 合 { , . 的 ) t ,∈ O 1包 p . P) 凸包 中 - 【 4 任给 t∈( ,) 很容 易导出 另外 两组特征 多边形顶点 . ) o 01 , 使得 第一组特 征多边 形顶 点 所 确 定 的 B z r曲线 等 于 曲线 段 { t ,EE , ] , 第 二 组 特 征 多 边 形 顶 点 所 确 定 的  ̄i e B()t ot )而 o B z r曲线 等 于 曲线 }通 常 将 这 条 性 质 称 为 B z r 线 的 可 分 割 性 .  ̄i e 口()f .] .  ̄i 曲 e 在下面 的推导 中我们用 j I A 表示 向 量 A 的 模 . A. 用 口表 示 向 量 A 和 口 的 内 积 , 用 而 AB表 示 经 过 点 A 和 口 的 直 线. 我 们 要 求 用 圆 弧逼 近 B z r曲线 时 满 足 以 下 四 个 条件 : ei e 条件 1 起 始 圆 弧 的 切 线 方 向与 B ze :  ̄ir的起 始切 线 方 向 一 致 , 止 圆弧 的 切 线 方 向 与 终 B ze  ̄ir曲线 的终 止 切 线 方 向 一 致 . 条 件 2 各段 圆 弧 在连 接 处光 滑相 切 . : 维普资讯 汁 算 机 学 报 条 件 3 总体 逼 近 精 度控 制 在 允 许 的 误 差 范 围之 内? : 条 件 4 所 用 的 圆 弧数 目尽 可 能 少 : 条件 1 条件2 保证 所产生 的逼近 曲线的整体光 滑性 . 和 可 而条件 3 条件 4 和 则可保证 算 法 的有 效 性 及效 率 . 除 非在 一些 特 殊 情 形 下 , 常仅 用 一 段 圆弧 不 可 能 满 足 条 件 l 当 然 更 谈 不 上 对 逼 近 通 , 精 度 的 控 制 . 们 考 虑 用 两 段 圆 弧 对 一 段 三 次 P ir曲 线 进 行 逼 近 , 我  ̄z e 当达 不 到 预 定 逼 近 精 度 时 利 用 P ze 线 的 可分性 将 其 分 成 二 段 . 晤分 别 再 对 每 一段 进 行 逼 近.  ̄ ir曲 然 图 2 设 P ze  ̄i r曲线 的特 征 多边 形 顶 点 为 P ,。P , 为确 定满 足条 件 l 条 件 2 两 段 圆 。P .P. 和 的 弧. 只需 确 定 它 们 的 连 接 点 的位 置 及 连 接 点 处 的 切 线 方 向. 两段 圆 弧 连 接 点 为 P, 接 设 连 点 处 的公 共切 线 与 直 线 P P交 于 点 P . 与 直 线 PP交 于 点 P , 图2 示 . 中 第 一 段 。。 而 za ,如 所 其 圆弧 起 始 于 m , 止 于 p, 点 P 处 与 向 量 PP 相 切 . 点 P处 与 向 量 终 在 o a。 在 下述关 系 : : 相切 ; 二 段 圆 第 弧 起 始 于 P, 止 于 P . 点 P处与 P ,相 切 , 点 P 处 与 PP 终 在 P 在 3 相切 . 然 , , ,满 足 显 P, j 一P l l 一P l … 【 I— P — I P} P a P一 由于 I P —pI I + P —p 一 } , ( ) 可 得 : P 一p I由 2 式 I P 一 I +P 一 I }, = P 一 I () 3 显 然 只要 找 出 P , 满 足 () 。 在线式 则 上存 在唯 一一 点 P使 得 ( ) 成 立 . 2式 因此 我 们的 问 题 转 换 为寻 找 满 足 ( ) 的 点 对 P 3式 …P . 由于 P 位 于 直线 PP 上 , 设 — +M p 一 ) 必 须 满 足 A O 因 为 若 ^ o 则 o 可 . > . < . 圆弧 在 处的 切 线 与 P -p相 差 10, 当 ^ 时 第 一 段 圆弧 退 化 为 一 点 , 时 我 们 无 , 。 8。而 一0 此 法 保 证 第 二段 圆弧 在 P处 与 直 线 PP 相切 . 似 地 , 们 可 设 P = + Y p 一 P) y 0 。 。 类 我 r ( 。 ,, > . 代入 () 得 : 3式 i。 P 一 I y P 一 i I。 + I2 — P 一 +^ p 一 ) ( - p ) (1 一y 3l 两端平方得 : I P 一 I+ I z P 一 I+2 I 胛 P 一 lP 一 i I 。 l — P 一 I+ I , 。 p 一 I 。 - +y ! - !P 一 I+2 ( 。 p ) ( p ) Y p - p ) ( - P ) 2Y p - P ) ( 2 A p - 3 ?p - 一2 ( n a ? 3 一 A ( ? o ’P 一 ) 化筒 后 得 : 维普资讯 1 期 0 常 盒玲 等 :‘ 甩 圆弧逼 近 三次 向 B z r曲线 的算 法 种 ei e { P 一P lP - p 1 ( - p ) ( { l + p - n ? ( . P P. 一 )? P p ( 一 ) ( 4) 令: I6 一 ( 一 P )?( - P ) . u P 一 c Ib一 ( c— P )?( — P ) : p a m 。 显 然 我 们 有≥ 0f 0 注 意 到 6> o 价 于 向 量 P. o P 一 的 夹 角 为锐 角 , 等 ,≥ . 等 一P与 。 6>0 1 价 于 向量 m —m 与 P -p 的 夹 角 为 锐 角 . f 等 价 于 点 p 与 p重 迭 . 们 可 作 下 述 假 。 。 而 —o 我 ● ● 一 m 一 p 设: 一 bl 0, > > 0.c 0 > ( 6) 当 ( ) p 足时我们可将 l z r曲线 不满  ̄ i e 使得 在分割后的 每段 B z r曲线 注 : p难 证 明在 非退 化情 形 下 , 确 切 地 说 当 P ≠ p , ! P并 且 P ,P .s 不 更 n -p C s 。P ,P 不位 于 + 同一直线上时 , 只要将 B z r 6i 曲线足够细分总能使 ( ) e 6 式成立. 如果 P ,P , 。P ,p位于 同一 — 直 线 上 ,P 相 应 的 B ze 则 6ir曲线 亦退 化 为 一 段 或 数 段 直 线 段 . 果 它 们 不 位 于 同 一 直 线 上 如 ) 但 m —p , 时 无 论 如 何 分 割 , 此 在头 一段 曲线 此 时我 们 可选 取 线 段 PP 上 足 , o 一 p 够 接 近 P 但 不 等 于 P 的 一 点 米 代 替 P而 使 得 6≠ 0p p 的 情 况 可 作 类 似 处 理 . 此 经 . . . 因 — 过 适 当 处 理后 总 能 使 ( ) 成 立 . 6式 p 一 p p 将 ( ) 代入 ( ) 5式 4 中得 : Ⅱ 十 6 十 一。 ( 7) p — 一 因此 有 : y 一 ( 或 ^ 一 (j 8 由>, 0知 < , 因 ( )∈。 )  ̄0 r瓦而 0>可 c 此 ∈。 , (麦? a 一 -当 <, , ? 当 . c j " 5 时 — . ,O 这 样 我 们 找 到 了 一 族 满 足 条 件 l 条 件 2 两段 圆弧 构 成 的 曲线 . 面 估 计 它 们 与 原 和 的 下 P ze  ̄ ir曲线 间 的最 大 误 差 . 第 一 段 圆弧 圆 心 为 c, 设 .半径 为 ,, 二段 圆 弧 圆心 为 c. 径 .第 半 为 _ 显 然 c,。 位 于通 过 点 ,并 且 垂 直 于 pp 的 直 线 上 , 此 直 线 与 B ze 线 交 于 c均 r 设 6ir曲 点 B( )∈ ( . ) , 设 B z r曲线 与 这 两段 圆弧 所 构 成 的 曲线 间 的最 大距 离 为 e 则 : t ( 01)并 6i e , £≈ ma x{ xd1 口( ) , a ma ( t ) m xd2 口 ( ) ( t )} | _ 。 —I 1 其 中 d ( 和 d ( 分 别 表 示 点 A 到 第 一段 圆 弧 和 第二 段 圆弧 的 距 离 . 进 一 步 简 化 计 .A) A) 为 算 , 们可 用点到 圆的距离 米代 替点到 圆弧的距 离 , 我 即取 : d ( ≈ lA—c 1 .. :A) lA~ l ! ^) l . 一r d ( ≈ l —r l 则有 : 维普资讯 计 算 机 学 报 E ma In x{B()一 c l r 1tK l t ≈ x la I t — .LKle()一 c l r { I 2 — 2} 0 f 《 ≤ 0 I l ≤ ≤ 令 () f () }(一12 , = B 一 .) 则函数 () 与函数 f口 一 —rf f () f J除在其0 点外具有 同 样的极值点. 设 () O) 的全体零点 的集合 为 Z , t在( 1 1 在( , 上 () . )- 的全体零点 的集 合 为 Z , A =Z U { , }A2 ,)显 然我 们有 : 令 Ot , 一z U 。 1, ma f 1 xf口()一 f r f= r8 I f — 】 n xf口()一 c f r f — L L 0 f ≤ ≤ 0 ^L ma lB()一 c1 rI ma l t x l 2一 = L xlB()一 c 1 2 一 1 “ <t ≤ t ∈ 因 此 蛩{ f ( - —rf [ t I J} B ) ‘’ 。 所 以对逼近误差 e 的估 计可通过计算 函数 ()j ,) £(一1 2 的零 点来完成 ( 实际上 e 给 出 亦 了实 际 误 差 的 一 个 上 界 ) 由于 () t 五 次 实 多 项 式 , 们采 用 Sum 方 法 来 计 算 它 . 是 的 我 tr 的零点. 在所有满足 条件 1 和条 件2 由两段 圆弧连成的 曲线族 中, 们选 取使 e 的 我 达到最 小值 的曲线作 为最佳拟 合曲线 . 经我 们的观察 , 通常 是 ^ £ 或 在相应 区间上 的单峰 函数 , 因此 可采用0 6 8 . 1法来 寻找 最佳拟 合曲线 ( 该方法 的收 敛速度虽 然稍 慢 . 但具有简单 、 安全的特 点 )如 果最佳拟 合曲线所 对应的 e 于预先给定的 误差限度 , . 大 则需 将 B z r曲线从 适 当  ̄i e 处 分 为 两段 再 分 别 进 行 逼 近 . 们 取 B z r曲 线 的拐 点 作 为 分 割 点 . 果 无 拐 点 则 取 它 我  ̄i e 如 相 对 于 其 弦 的 拱 顶 处 作 为分 割 点.  ̄ir曲 线 的 拐 点通 过 求 解 三 次 拐 点 方 程 一 () () Bz e t t= ( () 求得 , ) 而拱顶则可通过求解二次方程 ( 一z ) ( 一( 。 弘一 ) (’ ) 一 £来计 算. 3 计 算 流程 及算例 . 我 们将 第2 中所推导 出的 算法 归纳 为下述计算流程 : 节 () 1 判断 B z r曲线 的四个特征 多边 形顶 点是 否位 于 同一 直线上 . ei e 若是 则可 简单地 用直 线 段 对 其进 行 逼 近 . 则进 行 下 面 步 骤 . 否 ( ) P —p 则 令 P : 2若 o 一 +( : p ) 转 向 4 p - 。, . ( ) P 一p 则 令 P 3若 2 a + p 一 )转 向4 ( , - 其 中 为一 适 当选 取 的 小正 数 . ( ) 据 () 计 算 口 b,2 4根 6式 b. ( ) cb ,2 5若 . b不满足 ( ) 7 则转 向7 . () 6 找出用两段 圆弧的最佳逼近曲线及误差 E若 e 于允许 误差 则转 向9 . 小 . () 7 计算 B z r曲线 的拐点 . 存在 则将 拐点作 为分割 点 , 则将 l i 曲线相对 于  ̄i e 若 否 Mz r e 其 弦 的 拱 顶 处 作 为分 割 点 . ( ) B z r曲线从分割 点处分 为两段 , 8 将  ̄i e 并对每一段分 别重复4 中的步骤 . —8 () 9 若还 有 尚未 处 理 的 B z r曲 线 段 则 对 下 一 段 尚未 处理 的 B z r曲线 中  ̄l e  ̄i e —8 的 步骤 , (0 计 算 结 束 . 1) 维普资讯 l 期 0 常 金玲等 : 种用 圆弧逼 近 三次 平面 B z r曲线的 算法 一 ei e 71 8 图 曲 于 此 述 理 参 考 文 献 [ P vii? ? g rtmsfrGrp i nma eP o e ig Rek ie 1 8 1 a l s T. Alo i 3 d h o a hc a dI g re… . c vl 、 2 s l 9 . [ ] 苏 步 青 . 平 面 B z r曲搜 的 仿 射 不 变 性 . 算 数学 . 9 0 ( . 2 论 6i e 计 1 8 、4) 3 苏 步青 . 鼎元 . j 刘 计算几 何 、 上海科学技 术 出版杜 . 9 1 1 18 .. [] 静 家 昶 , 4 样条 函数与 计算 几何 . 科学 出版社 . 9 8 1 . 1 8 .2

http://exlei.net/tubaobijin/367.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有