您好、欢迎来到现金彩票网!
当前位置:ds视讯 > 非均匀有理 >

有理Bze6ir曲线的非均匀细分算法

发布时间:2019-06-04 03:28 来源:未知 编辑:admin

  有理Bze6ir曲线的非均匀细分算法_IT/计算机_专业资料。有理Bze6ir曲线的非均匀细分算法

  第 3 卷 第 9期 4 19 9 7年 9月 计 算 机 研 究 与 发 展 COM P UTE RE ARCH LDE R SE 8 VELOPM ENT V 0 . 4 NO 9 13 , . Se t 1 7 p . 99 有理 B ze 6ir曲线 的非均 匀细分算法 越 摘 要 20 3) 0 4 3 ( 复旦大 学数学系 上 海 弋 1Z ] d at ̄ u算法很 早就 用于 B e eC sa a 商 T曲线 、 曲面 的细分. 对于有理  ̄z r曲线 , 但 i e 当某 些点 出现大权 时, 固定 f 1 =1 2的均 匀细分算法失 效. 本文 分析了失效 的原 因并提 出了一种新 的 非均匀细分方法. 通过分析和 比较 , 证明了新方法非常有 效, 可以很好地应 用于实践. 关键词 dCsl 算 童 生 些 , e aa u 法, 堡 tj a :鐾± 坌 中国法分类号 T 3 14 P 9. 码 { cD A AN UNEVEN ALGo RI TH M F0R THE UBDI S ON S VI I O F RATI ONA L BEZI ER CU RVES Z HU o g LI LiM i Sn N — n ( a h ma is M t e tc “m t Fu n Un v r i da i e st y,Sh gh 2 0 3 an ai 0 4 3) A src T ed at ̄ uag r h h sbe p ldthu dvs no  ̄irc ren btat h eC sa alo i ma ena pi t s b iio f z uvsad t e o e i B e s r c s un r t n l  ̄ i u v s wh n s me c n r lP it h v i ih s h v n u f e .B ti a ia z rc re , e o o to on s a ebg we t,t e e e a o B e g me h do xn = 1 2 r v st e fc v . e meh d o  ̄ e e b ii o n s f t o f iig f 1 o e h i f t e A n w t o f n v ns d v in a di - p oe n ei u s te f c i e e s8 e p e e t d i h s p p r e tv n s r r s n e n t i a e . K y w r s d a tl u ag r h e o d eC saj o i m, ain l  ̄ m  ̄ v , u d i o a l t r t a z rc r e s b i s n o B v i C a S n mT TP3 1 4 I S u  ̄t 9 . 0 引 言 B z r曲 线 的概 念 由来 已久 , 献 F ] 介 绍 了 B z r曲线 的 几 何 作 图 法 , d  ̄i e 文 I中 6i e 即 e C saa atlu算法, 92 j 18 年刘 鼎元教授证明了其细分定理 , 并提出了有理 B z r 6i 曲线 的概 e 念啪. 对于有理 B z r 6i 曲线的细分 , e 现在常使用 F r 于 18 年提 出的细分算法啪, ai n 93 细分 参数一般取定为 / , 一1 2在本文 中称之为均匀细分算法. 在实际应用 中我们发现 , 对于非 有理 B z r 6i 曲线, e 均匀细分算法效果较好, 而对于有理 B z r 6i 曲线 , e 特别是当各控制顶点 收稿 日 : 9 61 1 } 回日期 z9 70- 4 皋 槛, 92年于复 且大 学教学 系获应用 教学专业计 算几何方 向博 期 19 — 6售 1 9 ? ̄2 . 19 士学位, 毕业后留复且大 学教学系工作 , 主要从 事 C G 的理论研究和 C D C M 软件的开发. A D A /A #蔚闺 , 9 5 19 年于复 且大 学教学 系获 应用数学专 业计 算几何方 向博士 学位 , 主要从 事计算复 杂性及算法的研究 , 毕业后 留复旦大学 管理学 院工作. 计 算 机 研 究 与 发 展 19 正 97 权的相对 比值很大时 , 均匀细分法将会失效、 本文分析 了失效 的原因, 并提 出了一种非均 匀细分方法 , 使得细分参数 f 的取值 由各控制顶点的权决定. 这种方法可以快速地画出有 理 Bz r  ̄i 曲线 , e 并且细分次数几乎不受权的影响, 十分有效. 1 问题 的提 出 给 定一组控制顶 点和权 (, ,=0 l …n 其中 为控制顶点, 为权 , 次有理 p, i , , , ) n 户f 一 ( ) 一 ∑ f 研( ) —一 . …E] 研( 一 1 1… 一f ,) t o1 , f ∈ , ) .r 1 ) = ( …, l . … … ‘ . 文献 E ] s 中证 明 了 次 有理 l i  ̄z r曲线 的 细分 定理 , e 现在通常使用的均匀细分算法就是取细分参数 , 显然 f 是与控制顶点的权无关 的常数. 我们甩均匀细分法 来进 行 有理 Bze  ̄i r曲线 的求 交 时 , 现 如果 控制顶 点 的 ]发 权相 对悬殊很大时 , 细分的点几乎都集中在大 权点附近、 如果 甩 b x比较方法进行求交 , o 便有很大的 bx存在, o 并 且 当 细 分次 数 在 一 定 范 围 内 增大 时 ,o b x的大 小 几 乎 不 图 1 三次曲线 变. 用 均匀细分澎I 田 次 分8 如图 1 一条三次有理 B z r ,  ̄i 曲线 , e 它的四个控制顶点 ‘ 的权分别为 (,0,0,)对它甩均 匀细分算法细分 8 1 111 , 次得到一条线. 图中的圆圈点表 示每次细分得到的落在曲线上的点 ( 以下的图中皆用圆圈点表示折线上确实位于 曲线 上的 点 ) 可 以看 出 , 圈点 的分 布 极 不 均匀 , 到 的是 明 、 圆 得 常值 部 分 , 反映 在 向 量曲 线 上 , 是 圆圈 点 都 聚 集在 某 一 图 2 图 曲线的分量凿线 就 个点的附近, 只有当细分次数增大到使得参数值的分布能够越过临界点时, 才可能进行有 效 的 细分 、 9期 朱 拾等 : 有理 l i  ̄z r曲线 的非均匀 细分 算法 e 2 非均匀细分算法 针 对 上 述 情 况 , 文提 出 了一种 非 均 匀 细 分算 法 . 本 在每 次 细分 时 , 数 f 参 的选 取不 再 固定 为 常数 , 而是 由控 制 顶 点 的权 的情 况决 定 . 面从 =2n 下 ,=3和 n 3三 种情 况 来具 > 体讨论 t 值的取法. () 一2的情 形 1 如 图 3 ,P 是控 制 顶 点 , f是 有理 B ze , P ,2 P()  ̄i r曲线 , 口为 pp 的中点, o* P为 Pq与 户 f的交点. l ( ) 在细分 时, 希望 t 值 的选 取 能够 使 得 圆圈 点 一户 f恰 好 与 P重 合 , 者 至 () 或 少在 P点的附近. 从这点出发 , 来求 P点对应的参数值 t . 曲线 P() f方程 为 : 卢z ( 0 01一 f+ 2 11( ) 卢z t 1 图 3 =2 I 0) 一 l Y0)一 — 酉二_ 二 ± 三 ’ Py ( o。 1一 f。 2 Yt 1 t ) + 1( )+ Y2 t 粤 ’ [ 。 ] ∈ ‘ (一f + 2 ( 一} + 1 ) t1 ) 直 户的程 : 线 方 为 考 一 塞 . 联 立化 简得 到一 元二 次方 程 : 一 ) -Z o+P =0 ( f pt o . 当 一 时:z , 轰 . ,-; ≠ 时 , 当 P o JP> > } 油 对 一 鱼 ()一3的情形 2 如 图 4 PPPP , o 。是 控 制 顶 点 , f 是 三 次 有 理 P() e r曲线 , pp 的连 线 的 中点 , 为 户P 的连 线 口 为 os z 的 中点, P为 qq 与 户 f的交 点. l: ( ) 下面求曲线 户 f在 P () 点参数的近似值. P( 的参 数方程与直线 口q 的方 程联立化简得 到 f ) : 方程 : ^卢f 一 ^P + Bt 0 -3 】o = . 图4 3 其中, B= f+32卢+ ) 一3k + ( + ) +3B+k] l o k( f [ :2 (-o z k 一 ( 一 z ) 一 ( - y )c ; 】 3 o y ̄ oa’ k 一 ( 1 赴 ) 一 ( - y )c . 2 z一 yl  ̄ a’ z = z + z 一o z 1 t — ¨ Y 一 Y +2 L 一。 弘 - 一 计 算 机 研 究 与 发 展 B 与 P ,P , , , 及 t oP, zP , 有关 . P ,P , ; 当 oP ,。P 与 , ,z 卢 固定 时 , 因为 t ∈ [ ,]所 以 B是 一个 有 界量 . 时若 一 。 , 01 , 这 。 则有 t 0 既一 0 亦 即 当 卢》 风 时 , 程 可 一 , . 方 3 近 看 :3, √ . 似 成z 风 0一 甓 kt f- t 当 》 时取 如 与 似 小则 1? ,f√ ?果 近 大 ,取 / z ( ) 时 的情形 3次 , ‘ 控 顶 为 o… ,g 户一 中 ,为 l 一 重 ,g 备P 制 点 P 记 。的 点q p"一 心即z P 为 P z " p的 一 t , P为 qq 与 户 t的交 点. tz () 参数 曲线 P t的方程与直线 qq 的方程联立化简得到方程 :. +髓 一0 其 ( ) l 。 9 一 . 中 ,一( -y )一( 一z ) . k oz 。 B 与 P,一0 1 …及 且,一0 1 …一 1 t 关 . P , 0 1 …和 且, 0 1 ,, i ,, 和 有 令 。 ,, ,, …n 1固定 ,∈E ,3 , - t o 1 时 B是 有界 量. 当 一 。 时 , 0故 B 一 0方 程可 近似 看成 :卢, 。 t 一 t , n 一 o 得 瓮 ,t . 解 √ 吖百 当 风时 取t√ . 与 》 , ≈ 铲 当 近 时 则 = / 似 , 取tl . 2 3 两种方 法比较 有理 B z r  ̄ e 曲线可用齐次坐标表示为【 : ( , : 研( , :曰( 》如 i 0 t ) t t . ) ) 面 果把 它看 作三 维空 间的 曲线 , 么它 是 以 ( 那 且,。 , , 0 1 …为控 制顶 点 的空 间整 y且 且) ., Bz r  ̄i 曲线. e 用均 匀细分法细分 曲线 , 生成的圊 圈点在空间曲线上分布得 比较均匀 , 为 作 近似曲线可以很好地逼近原曲线. 但当控制顶点出现相对较大 的权 并且细分次数不够 多 时, 圆圈点在空间曲线上的分布就 比较稀疏 , 再经过一个射影变换得到平面有理 B z r  ̄i e 曲线之后 , 圆圈点在平面曲线上分 布很不均匀 , 会密集 在具有相对较大权点的附近, 从而 逼近 程 度差 . 图 5是二 次有 理 B z r曲线用 均 匀 细分 法 得 到的结 果 , 的相 对 大 权点 取到 了 1  ̄i e 它 0, 细分 次数 为 9次. 明显 , 很 细分 得 到 的 圆 圈点在 大 权 点 附近 相 当 密 集. 由于 非均 匀 细分 法 在每次细分过程都考虑权的影响, 所以细分点分布比较均匀 , 但也非绝对均匀. 曲线 曲 在 率较大的地方 , 点分布要 比曲线平直处稍许密集 , 这也是精确描绘 曲线所必需的 由于参 数选 取 由权决定, 当权增大时, 不用增加细分 次数就可以使细分点 比较均匀分布. 6 图 是 对应于图 5 的曲线 , 同的权 , 相 用非均匀细分法细分 4 次. 由于 用非 均匀 细分方 法可 以 用很 少 的 细分 次 数达 到较 好 的逼 近 效 果 , 因此 在应 用 于 求交运算时 , 可以快速有效地求出交点 , 提高了精度和速度. 文献[ 3 作者讨论 了有理 6 中, 曲线 的三 种求交方 法 , 中前 两种就 是 均 匀 细分 法和 区间 细分 法.均 匀 细分 法 的讨论 中 , 其 引用 了汪国昭【18 年的一个结果 , 94 用来讨论 细分次数与精度的关系. 9 期 一 朱 松等 : 有理 l i  ̄z r曲线的非均 匀细分算 法 e 6l 7 ; .牛 蓄 y为 参 数 曲线) [,] y ,a卢 )一 u iI( 一 Ert + ( 一 y ] } sp ( ntt f ) c( ) 1 ) O) I , 《 。 ≤ 其中 , ,] 口 ≤ . t ∈ 6 , ≤口 ≤6 3 - - iLo 令 r一lg — n( 0 。 4v / n ) 其中,>。 E 为某一4量 , 曲线 的次数 、 为 — — — 一 , 工。一 l  ̄ X (五 l I l ≤一 一 2 而+ I lt 2 『1 五+ + 2 ,y 一 y. + + I It 2 z, 一 +一:) +I 则 当曲线的细分次数超过 r时 , y ,a ) . o (( [ , ≤e证明见 [] ) 6. 实际上 , 汪国昭的结果是针对整 t i 曲线而言的,  ̄z r e 对于有理 曲线则不适用. 当出现 相 对太权 点时 , 均匀和区间细分法要想 比较 好地逼近原 曲线将是较难实现的. 用于求交 时, 这两种方法均会失效 , 而非均匀细分法应用于求交效果则非常好. 图 5 n 2 权 为 ( 0 ,0。) = . 11 ‘1 图 8 一2 权 为 ( ,0 , ) , 1 1 ‘1 用均 匀细分法细分 9 次 用非均匀细分法细分 4 次 参 考 文 献 1 苏步 青, 剂鼎 元. 计算几何 ( 现代教学 丛书 上海 : 上海科学技术出版杜 ,90 18 2 羽鼎 元. 平面敬 B e 曲线 的凸性 定理 . 学年 ,9 2 3 1 : 4 5 I 教 18 。( ) 4 _4 3 羽鼎元 . 有理 B = z曲线e i 浙江大学 学报,9 2 1 ( 9 2 1 8 , 6 1 8 年计算几何讨 论论文寨 )l 3 4 ;3 —1 0 4 F rn G. AI o  ̄h sfrr to a z盯 c a i g rt m oai n lB6i CAD 。1 8 5c ): 3 7 9 3, 2 7 — 7 5 汪国 昭, 沈盒福 . 有理 B 如 曲线曲面的离散和几何性 质 . 6 浙江大学学报 ,9 5 1 ( )l 3 3 1 8 。9 3 ,2 —1 O 6 Tho a otR m s W Stsct C  ̄mp rs n o h e u q mtf e n ag rt a io ft re c r ̄ esc lo ihms CA . D t1 86I1 1) 58 63 9 8( : — 7 汪国昭. e 由线 曲面 的离散 隶变算法 . B r 浙江 大学 学报 , 9 41 (9 4年计算 几何专寨) l 8 1 8 ,8 1 8 t0 一n9 重要更 正 由于我 们对腔 片检查不严 , 成 1 9 造 97年第 7 4 7页与 4 1页重复 , 此向作者和读 者致 期 8 8 在 敷 。47页的主要 内窖 ( 8 其余 同 4 1 ) 8 页 如下 : 基 于一性整台 的知 觉模 式生成与识g 模型 目 ■ 曼 在 [] 3的基础 上 , 本文给 出了基于属性 整食 的模 式生成与 转化机制 的敷学 表达 , 并对跨感觉模 式识射 中 的特征辨识 一 和模式匹配、 补充和惨正问题 , 给出了相应的评爿函数. Ab l . A dm=mt lmo lfrg n r to n 订a强f r o fme W c e a e na t ut e it- mrvt m ̄ ca deo e e a ina d _ 0 ma n 0 m ̄ s h ma b s d a t ̄ i ne v g aln p e e td i sp p r s mec mpe urlo e ain s c sn u ae wo ki tg a na dd t cincf r to r s ne n a e - o o lxne a p rto s?u h a e r l t r n e r  ̄o n e e to n mu t-e _air o 1 s h ma a msc n r  ̄ cna d c mp e m iu li g fp ze t n s h m a o n ]is ̄s t mlc mp 旺 c e s,n o d this, e n o lme ofvs a ma eo e ̄ p i c e sIB o as er p e e td bym h ai l a o  ̄e lo b e r= n e 皿 t a c a . 心理学将 知觉定义为客 观事物各十 部分 的各种 属性 在头脑 中的综合反 映 。 知 心理学 则将知 觉看 n 作是 感觉 信息的组织和解释 , 即是 获得感 觉信 息的 意义的过程日. 模式 被看作是 由若干 元素或 成分按 定关 系形成 的某种刺激结构 。 即模 式被看作是诸刺激的组 一

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