生成圆弧的多边形逼近法 ?圆的正内接多边形迫近法 圆的等面积正多边形迫近法 用正多边形近似代替圆,显示多边形的边可用 扫描转换直线段的中点算法来实现。 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 26 用正多边形近似代替圆, 显示多边形的边可用 扫描转换直线段的中点算法来实现。 生成圆弧的多边形逼近法 ? 圆的正内接多边形迫近法 ? 圆的等面积正多边形迫近法
生成圆弧的多边形逼近法 圆的正内接多边形迫近法 P 原理 im(m边正内接多边形)=圆 n→)0 计算多边形各顶点的递推公式 X计+1 r coS a -sin a( Xi sin a cosa Yi 因为:a是常数,sina,cosa只在开始时计算一次 所以,一个顶点只需4次乘法,共4n次乘法,外 加直线段的中点算法的计算量 北大计算机系多媒体与人机交互 27
北大计算机系多媒体与人机交互 27 生成圆弧的多边形逼近法 – 圆的正内接多边形迫近法 • 原理 • 计算多边形各顶点的递推公式 Xi+1 cos a - sin a Xi = Yi +1 sin a cosa Yi 因为: a是常数， sin a， cosa只在开始时计算一次 所以，一个顶点只需4次乘法，共4n次乘法，外 加直线段的中点算法的计算量。 边正内接多边形）=圆 → n n lim (
可题 B 给定最大逼近误 2丌 差(最大距离)n= DELTA,如何确 C 定多边形的边数 R 或a? d=r-rcos(a/2)<= delta DcoS(a/2)>=(R-Delta/R Lya<=2 arc cos(r-DELta/R amax=2 arc cos(R-DELTAR n=360/a 另外,用矢量运算可以简化计算,推出求顶点的逆推公式(p60) 北大计算机系多媒体与人机交互 28
北大计算机系多媒体与人机交互 28 •问题： 给定最大逼近误 差（最大 距离） DELTA ，如何确 定多边形的边数 n或a？ 2 n = 另外，用矢量运算可以简化计算，推出求顶点的逆推公式(p60) d = R – Rcos(a/2) <= DELTA cos(a/2) >= (R – DELTA)/R a <= 2 arc cos (R – DELTA)/R amax =2 arc cos (R – DELTA)/R n = 360 /a
生成圆弧的多边形逼近法 圆的等面积正多边形迫近法 步骤: ●求多边形径 B 长,从而求 所有顶点生 标值 ●由逼近误差 值,确定边 所对应的圆 B 角a E D 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 29 生成圆弧的多边形逼近法 - 圆的等面积正多边形迫近法 步骤： ⚫求多边形径 长，从而求 所有顶点生 标值 ⚫由逼近误差 值，确定边 所对应的圆 心角α
扇形ODCE的面积=三角形OPP+的面积(P60页) B E 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 30 扇形ODCE的面积 = 三角形OPiPi+1的面积(P60页)