椭圆生成算法的研究
椭圆生成算法的研究
本文由天空乐园校园二手网整理分享
摘要
作为计算机图形学中基本几何元素之一的椭圆，其生成算法在几乎所有计算机图形学相关领域都要用到，尤其在计算机辅助设计中经常涉及。因此，研究椭圆生成对计算机图形系统十分重要。目前，已有大量的文献讨论了如何高效生成误差小的椭圆。文献一中方法之一在扫描转换的同时复制椭圆宽度数个像素，这种方法比较简单，但造成椭圆切线斜率接近-1处显得很细。文献一中方法之二扫描转换两个同心的椭圆，内椭圆的两个半径分别为a-w/2，b-w/2 ；外椭圆的两个半径为a +w/2 ,b + w/2；然后填充它们间的间隙，在微分几何中有一个结论：沿着垂直椭圆弧的方向，将此椭圆上的点移动w/2的距离所形成的曲线与原椭圆同心的椭圆，而是由一个8次方程所描述的曲线，因此这种算法也有较大误差，特别是a 的值接近于w时。然而，对这样8次函数进行扫描转换，计算量非常大。圆弧绘制生成宽椭圆算法与椭圆中点扫描转换算法复杂度相当，且生成的椭圆效果较好，视觉感受不到明显缺陷。
本文主要对计算机图形学、椭圆的生成算法的具体实现及其应用进行综述，并简要讨论。
关键词：计算机图形学椭圆生成算法并行生成算法宽椭圆
1 一种宽椭圆生成算法
计算机辅助设计领域常涉及宽椭圆生成，宽椭圆生成算法的优劣直接影响 设计效果。为了生成一个圆心在原点的标准宽椭圆，每次用单像素宽的椭圆中点扫描转换算法，得到一个单像素宽椭圆上的一个点，填充一个以该点为中心，椭圆宽为直径的圆弧，扫描转换结束后，生成一个无明显视觉缺陷的第一象限12宽椭圆。
作为计算机图形学中基本几何元素之一的椭圆，其生成算法在几乎所有计算机图形学相关领域都要用到，尤其在计算机辅助设计中经常涉及。因此，研究椭圆生成对计算机图形系统十分重要。目前，已有大量的文献讨论了如何高效生 成误差小的椭圆。椭圆的扫描转换法[1]就是其中之一，该算法基于Da Silva 的算法[2]，运用二阶偏差分Pitteway[3]，Van Aken[4]、KAppel[5]等所用的一些技术，该算法生成的椭圆都是单像素宽的，而现实中更多时候要生成宽椭圆，宽椭圆一般定义为沿着垂直两半径为a 、b 的椭圆弧的两方向，将此椭圆上的点移动2w 的距离所形成的两条曲线中间部分，为了生成宽椭圆，文献一中方法之一在扫描转换的同时复制椭圆宽度数个像素，这种方法比较简单，但造成椭圆切线斜率接近-1 处显得很细。文献一中方法之二扫描转换两个同心的椭圆，内椭圆的两个半径分别为2a ? w ，2b ? w ；外椭圆的两个半径为2a + w ，2b + w ；然后填充它们间的间隙，在微分何中有一个结论：沿着垂直椭圆弧的方向，将此椭圆上的点移动2w 的距离所形成的曲线与原椭圆同心的椭圆，而是由一个8 次方程所描述的曲线[6]，因此这种算法也有较大误差，特别是a 的值接近于w 时。然而，对这样8 次函数进行扫描转换，计算量非常大。圆弧绘制生成宽椭圆算法与椭圆中点扫描转换算法复杂度相当，且生成的椭圆效果较好，视觉感受不到明显缺陷。
1.1 算法基本思想 主要考虑中心在原点的标准椭圆12222=+b y a x ，宽度w ，(a >b >w ，a ，b ，w
∈z )；对于中心不在坐标原点的椭圆，可先作相应的平移变换，变换为中心在原点的椭圆，把所得的像素坐标加上一个位移即可得到所求的像素坐标。此外，只讨论椭圆在第一象限内的生成算法，其他象限内的点利用椭圆的四分对称性即可得到。在第一象限内的四分之一椭圆分为两个区域来处理．两个区域之间以斜率为-1 的点(即法向量两个分量相等的点)作为分界。对于区域I ，以点(0，b )为始点，x 方向单位长作为步长。向右生成曲线。假设当前扫描计算得到的点为批p 0（x ，y ），扫描转换的下一个点p 1 可能为s 1=（x+1，y ）或s 2=（x +1，y -1），
判断s 1、s 2 的中间点)2
1,21(--y x m 在椭圆的内还是外，选择下一个扫描点。 如果中点m 在内(m 点代入椭圆方程值小于1)，则下一个点p 1 为（x +1, y ），否则为（x +1, y -1）；当斜率变为小于-l 时，转向区域Ⅱ，此时以(a ，0)为始点。y 方向作为单位步长，向左生成曲线。假设当前扫描计算得到的点为p 0′(x ，y )，扫描转换的下一个点可能为s 1′(x ，y +1)或s 2′(x -1，y +1)，判断s 1、s 2的
中间点m （x ?21 ，y+2
1 ）在椭圆的内还是外，选择下一个扫描点。如果中点在内，则下一个点p 1′为（x ，y +1）否则为（x -1，y +1）。以上简单介绍了椭圆中点扫描生成算法，接下来基于中点扫描算法来生成宽椭圆。宽椭圆生成算法思路：先以中点圆算法[1]生一个圆心在原点直径为w 的圆，填充该圆，然后以椭圆扫描转换算法[1]求得椭圆
12222=+b y a x 上的点，将填充的圆平移到扫描转换得到的
各点处（如图1
）。
图1 生成椭圆第一象限
1.2 算法实现过程
如图2，椭圆扫描转化得到的相邻点P 0(x 0，y 0)、P 1(x 1，y 1)，它们对应的圆形填充区为U 1、U 0，填充圆于造成中间大量的像素U 1 U 2重复绘制，算
法复杂性较高，实际上只须绘制U 1-U 2，即图中黑色的部分，这些点全在圆边
上，为“半圆弧”，这个半圆弧相对扫描点P 1 的位置以及它的形状取决于扫描推进的方向，也就是P 1 与P 0的位置关系。图1 所示，根据椭圆扫描转换分4种来考虑它们的位置（θ为圆心角）：
（1） 扫描第一区间(切线斜率r >-1)，p 1 取S 1，X 1=X 0+1，y 1=y 0 时，
如图2 所示。U 1-U 2 为图中黑色右半圆弧，绘制右半圆弧的算法：
1） 从最左的一个点开始， 取1/8 圆?? ?≤≤24
θ上的一个点q ； 2） 由对称性，计算q 对应在1/2 圆??? ??≤≤-22
πθπ的3 个对称点q 0, q 1, q 2； 3） 将q q q q ,,,210平移(j i y x 11,) , ()y x 1
1,为p 1 的坐标； 4） 判断是不是最后一个点，不是的话，取下一个点；回到2）；是则圆弧绘完。
图2 中点扫描向右推进时相邻两次填充区的关系
（2） 扫描第一区间（切线斜率r >-1），p 1取s 2，X 1=X 0+1
，101-=y y ，如图3 所示。
图3 中点扫描斜下推进时相邻两次填充区的关系
U U 01-为图中黑色半圆弧??? ??≤≤-44
3πθπ，图中类似p 点的凹点要绘制，绘制右下半圆弧的算法：
1） 从最左的一个点开始， 取1/8 圆??? ??≤≤24
πθπ 上的一个点q ；
2） 由对称性，计算q 对应在1/2 圆?? ?≤≤-44
θ的3 个对称点q q q q ,,,210； 3） 将q q q q ,,,210平移(j i y x 11,) , ()y x 11,为p 1
的坐标; 4） 判断q 边有没有凹点，有则取凹点执行2)、3）；
5） 判断是不是最后一个点，不是的话，取q 下一个点；回到2）；是则圆弧绘完。用同样的方法可以填充第二区间的椭圆。
（3） 扫描第二区间（切线斜率r <=-1），
当p 1 取s 1，x 1=x 0，y 1=y 0-1 时，如图4 所示。
图4 中点扫描向下推进时相邻两次填充区的关系
U U 01-为图中黑色半圆弧(?π≤θ ≤ 0)，绘制下半圆弧的算法：
1） 从最左的一个点开始，取1/8 圆??? ??≤≤24
πθπ上的一个点q ； 2） 由对称性，计算q 对应在1/2 圆(?π≤θ ≤ 0)的3 个对称点q q q
q ,,,210； 3） 将q q q q ,,,210平移(j i y x 11,) , ()y x 1
1,为p 1 的坐标； 4） 判断是不是最后一个点，不是的话，取下一个点；回到2)；是则圆弧绘完。
（4） 扫描第二区间（切线斜率r <=-1），当p 1 取s 2，x 1=x 0+1，y 1=y 0-1，此时p 0 与p 1 位置与(2)同，见图2，必须绘制右下半圆弧，其算法见绘制右下半圆弧的算法。
1.3 宽椭圆具体的生成过程
（1） 生成直径为椭圆宽度w 的1/8 圆，以数组y [n ]记下1/8 圆的纵坐标值；
（2） 填充圆心在（0，b ）处直径为w 的圆，p 0 为（0，b ）；
（3） 判断p 0 是否为分界点, 是转(7)，不是
转入(4)；
（4） 由椭圆的扫描转换法求得p 1；
（5） 判断p 1 与p 0 是对角关系还是水平相邻，如果是水平相邻，绘制右半圆，如果斜对角，绘制右下半圆；
（6） p 0=p 1，转(3)；
（7） 填充圆心在（0，b ）处直径为w 的圆，p 0 为（a ，0）；
（8） 判断p 0 是否为分界点，不是分界点转入(9)，是则结束；
（9） 由椭圆的扫描转换法求得p 1；
（10） 判断p 1 与p 0 是对角关系还是垂直相邻，如果是垂直相邻，绘制上半圆，如果斜对角，绘制左上半圆；
（11） P 0= P 1, 转(8)。
2 一个椭圆的并行生成算法
随着计算机图形学的发展, 对基本几何元素生成算法的研究也不断深入, 人们从不同角度对椭圆的生成提出了许多算法. 文献[ 1] 从已知点入手, 根据递推公式逐点选择最靠近椭圆的像素点, 文献[ 2] 和[ 3] 也从已知点入手根据递推公式每次确定两个最靠近椭圆的像素点来生成椭圆, 文献[ 4] 从椭圆与其外接和内切圆之间的相互位置关系入手, 通过这两个圆来生成椭圆, 文献[ 5] 从椭圆的参数方程入手, 利用正弦和余弦的泰勒展开式以等分角度为增量生成椭圆.本文从另一角度入手, 利用多处理器( 或线程) 并行生成椭圆, 即以Bresenham 椭圆生成算法为基础引入并行特征, 并利用C # 的多线程机制模拟实现。也就是先把第一象限的椭圆分割成无关联的两段, 然后针对每一段利用一个处理器( 或线程) 并结合椭圆的四分对称性进行椭圆的Bresenham 扫描转换, 从而提高椭圆的生成效率.
2.1 椭圆弧的划分 设椭圆的方程为12222=+b y a x ，即F( x , y )=0222222=-+b a y a x b a, b 为x 轴方向和y 轴方向的两个半轴, 且a, b 均为正整数, 任意位置的椭圆可通过图形的复合变换得到。由于椭圆的四分对称性, 只需考虑第一象限1/4 椭圆的生成, 其它象限的像素点可由图形的对称变换得到。对隐函数F( x , y ) 求导可得dX
dY = y x a b 22/-, 由于dy /dx ≤0 可知椭圆在第一象限内单调递减, 在区间[ 0, a ] 内切线的斜率从0 递减到- ∞ .为了使生成的椭圆具有封闭性, 以弧
上斜率为- 1 的点作为分界, 把椭圆弧分成上下两部分. 上半部分满足| dX
dY | < 1 即y x a b 22≤ , x 的变化量大于y 的变化量, 由x 从点( 0, b) 开始递增
步长来确定y 的值, 下半部分满足| dX
dY | ≥1 即y x a b 22≥, y 的变化量大于x 的变化量, 由y 从点( a, 0) 开始递增步长来确定x 的值.由于这两部分是
相互独立的, 可用两个处理器( 或线程) 并行处理, 而不用考虑同步问题, 从而能最大化的提高并行效率.
2.2 两部分的算法描述
对划分后的两个独立弧段, 可以借用Bresenham 算法思想从一个已知点开始根据构造的判别递推公式逐
点生成, 这个过程可利用两个处理器( 或线程) 并行执行.对于上半部分, 假设
已知点为()y x i i , 则下一点()y x i i 11,++ 在其右方()y x i i ,1+ 点或右下方
()1,1-+y x i i 点中选择离椭圆弧最近的点, 而| F ()y x i i ,1+ | 为右方点到椭圆弧的距离, | F ()1,1-+y x i i | 为右下方点到椭圆弧的距离, 通过做差:
d i = | F ()y x i i ,1+ | - | F ()1,1-+y x i i | =| F ()y x i i ,1+ | + | F
()1,1-+y x i
i | 可判断出所要选择的点, 即: d i < 0 选择右方的点, d i ≥0 选择右下方的点.
根据所得到的
()y x
i i 11,++ 利用上述思想推下一点即可得到di+ 1 与di 的递推关系式: d i 1+=d i +4,2212a y a
i ++d i < 0且d i 1+=d i +4x b a y a i i 12212
42++-+，d i ≥0
该算法在VS . NET2005 平台下编译通过, 根据笔者的思路该算法可以利用任何并行编程环境如PVM 或MPI 在并行机或集群网络上实现.
3 一个椭圆生成算法
计算机图形学中, 关于椭圆的生成算法较多, 如中点椭圆生成算法[1], 高效的整数型椭圆生成算法[2], 基于Bresenham 算法的画椭圆算法[3], 椭圆的高质量、快速生成算法[4]等, 这些算法的主体思想均是以递推方式每次生成椭圆上一个点的坐标, 再调用画点函数在显示器上点亮一个像素。文献[3]中介绍的是一种高效的算法, 该算法引用了虚拟空间中椭圆的内切或外接圆, 使虚拟空间中所画的圆较小, 减少了参与运算的数据位数,但该算法生成的椭圆并不精确, 当椭圆的长短轴之比较大时,靠近长轴顶端部分的图像退化严重, 呈锯齿状, 这种算法可称为“内切或外接圆算法”, 它只适合于长短轴之比小于3 的情况。文献[4]给出的算法是“等分角度的绘椭圆算法”, 它要用到浮点运算, 且无法确定不同椭圆应该多少等分方可使生成的椭圆达到最佳。
作为计算机图形学中基本几何元素之一的椭圆，其生成算法在几乎所有计算机图形学相关领域都要用到，尤其在计算机辅助设计中经常涉及。因此，研究椭圆生成对计算机图形系统十分重要。目前，已有大量的文献讨论了如何高效生 成误差小的椭圆。椭圆的扫描转换法就是其中之一，该算法基于 Dasilva 的算法，运用二阶偏差分 Pitteway ，Van Aken 、KAppel 等所用的一些技术，该算法生成的椭圆都是单像素宽的，而现实中更多时候要生成宽椭圆，宽椭圆一般定义为沿着垂直两半径为 a 、b 的椭圆弧的两方向，将此椭圆上的点移动w/2的距离所形成的两条曲线中间部分，为了生成宽椭圆，文献一中方法之一在扫描转换的同时复制椭圆宽度数个像素，这种方法比较简单，但造成椭圆切线斜率接近-1处显得很细。文献一中方法之二扫描转换两个同心的椭圆，内椭圆的两个半径分别为a-w/2，b-w/2 ；外椭圆的两个半径为 a +w/2 ,b + w/2；然后填充它们间的间隙，在微分几何中有一个结论：沿着垂直椭圆弧的方向，将此椭圆上的点移动w/2的距离所形成的曲线与原椭圆同心的椭圆，而是由一个8次方程所描述的曲线，因此这种算法也有较大误差，特别是 a 的值接近于w 时。然而，对这样8次函数进行扫描转换，计算量非常大。圆弧绘制生成宽椭圆算法与椭圆中点扫描转换算法复杂度相当，且生成的椭圆效果较好，视觉感受不到明显缺陷。
3.1 算法思想及算法描述
设椭圆方程为F( x, y) =0222222=-+b a y a x b =0, 其中a 、b 为x 轴方向和y 轴方向的两个半轴, 且a 、b 均为正整数, 任意位置的椭圆可通过它的平移和旋转得到。由椭圆的对称性, 可只考虑一个象限内的1 /4 椭圆弧的生成。如图1 所示, 是一个a=19, b=10 的椭圆。在第一象限内, 椭圆弧是由一组水平直线段、斜率为- 1 的对角直线段和垂直直线段首尾相连而成的。在处理这段椭圆弧时, 仍然依文献[2]中所述, 把它分为两个部分: 上半部分( 弧1) 和下半部分( 弧2) , 以弧上斜率为- 1 的点( 即法向量的两个分量相等的点) 作为分界, 如图2 所示。
图2 一象限弧分两个部分
图1 a=19，b=10的椭圆
由微分知识, 椭圆上一点P( x, y) 处切线的斜率方程为: y a x b 2222+=0,
则有y ′=y a x b 22- 。在第一象限中, y ′∈[- ∞, 0]。由图可知, 在上半部分
( 弧1) , y ′∈[- 1, 0]; 下半部分( 弧2) , y ′∈[- ∞, - 1]。即上半部分满足y ′>- 1, 即y x a b 22≤, 而在下半部分则有y x a b 22≥。
2.1 上半部分( 弧1)
在上半部分, 设P i 11- ()1,1-+y x i
i 是已确定的一个像素, 则下一个像素H i (x i ,y i
) 要么是H i (x i ,y i ) , 要么是L i (x i ,y i ), 如图3 所示。由于x 坐标从0 开始, 每次递增1, y 坐标从b 开始, 每次不变或递减1, 所以有:
x i =H i =L i =x i - 1, H i =y i - 1, L i =y i
- 1- 1。
图3 p i 1-和p i
的位置关系
由( 1) 、( 2) 、( 3) 可以用画点函数依次画出弧1 上的各个像素, 这实际上就是Bresenham 画椭圆的改进算法的思想, 这样做并没有充分利用到弧1 上的水平直线段和对角直线段。弧的切线反映了弧的走向, 当弧的切线斜率在- 1 /2≤y ′≤0 时, x 增加2 时, y 最多减少1。如图4 所示, 这一段椭圆弧是 由水平位移至少为2 的线段组成( L1, L2, L3) 。当弧的切线斜率在- 1≤y ′≤- 1 /2 时, 是长度不超过2 个像素的一组水平直线段, 当然可看成一组斜率为-
1 的对角线( L4, L5) 。在图4 中, 当x 从0 加到6 时, y 值始终为b, 这条直线段( L1) 可通过( 1) 的d i<0 得到; 当x 再加1, 则有( 2) 的d i≥0, 此时, y 应减1, 进入第二条直线段, 当x 再加1 时, 又进入了(1)的d i<0 状态, 此后x 继续加1 至x 加到10, 生成L2; 当x 再加1, 又有d i≥0, 此时, y 应减1, 如此循环直到y′<- 1 /2。在这个过程中, 可以得到长度大于等于
2 个像素的一组水平直线段, 这组水平直线段可用画线函数line(x0, y, x, y) 画出, 其中x0和y表示d i≥0 时所记录的水平坐标和垂直坐标, x 表示退出d i<0时的水平坐标。
图4 弧段由线段组成
3.2 算法的整数化
以上程序中使用了关于x、y 的乘法运算和一些常量a、b的乘法运算, 由于x、y 的变化都是增量变化的, 所以可使用增量运算来避免乘法, 常量的乘法运算也可以使用中间变量使其在循环之前完成。若设incx=b*b*x, incy=a*a*y。则: 在循环开始时, x=0, y=b。所以有: incx=0, incy=a*a*b。在循环体内, 当x 增1 时, incx 增b*b, y 减1 时, incy 减a*a。此时, while( 2*b*b*x<=a*a*y) 可改写成while( ( incx<<1) <=incy) ; while( b*b*x<=a*a*y) 可改写成
while( incx<=incy) 。对弧2 结束条件的处理形式: 在弧1 结束时, 使用一对变量( stopx, stopy) 记住该点, 作为弧2 的循环结束条件。这是因为弧2 的结束点就是弧1 的结束点。若设BF=b*b, AF=a*a, BF4=b*b*4, AF4=a*a*4。在循环体内部, 则有: 当d<0 时, d+=(BF4*x+2*BF) ; 当d≥0 时, d+=(BF4*x+2*BF) - AF4*y。d 的增量部分显然是x、y 的线性函数,由于x、y 均为增量变量, 所以, d 的增量部分完全可用增量表达式来确定。
3.3 算法的效率分析
该算法绘制一条直线段( 水平、垂直、对角) 的计算量与画点算法的计算量是相同的, 但是本算法的输出量只有画点算法的1 /N( 其中N 为一条线段的像素数) 。由于N ≥2, 所以, 该算法的效率显然高于画点算法, 当两个半轴之比较大时, 椭圆主要由较长的水平直线段或垂直直线段组成, 即N 的平均值远远大于2, 所以绘画效率将会提高很大。弧2 的结束条件stopy 的引入, 进一步减少了对角线段绘制的计算量。在天逸Y- 510笔记本电脑、Windows- xp 操作系统下, 绘制5 000 个椭圆的进行实测统计情况如表1 所示, 可以看出, 在两个半轴之比( a /b 或b /a) 小于3 时, 本算法的效率是中点算法[3]和Bresenham 改进算法[2]的2 倍以上, 是内切或外接圆算法[3]的1.5 倍左右; 本算法的效率随两个半轴之比的增大明显提高, 当两个半轴之比大于6 时, 本算法的效率是中点算法[1]和Bresenham 改进算法[2]的4 倍以上。总之该算法具有非常高的效率, 特别是当椭圆的两个半轴相差较大时, 绘图效率更加明显。
4 一种高效的整数型椭圆生成算法
对已有的椭圆生成算法进行深入的研究, 仔细分析了各种算法的优缺点; 并在此基础上, 提出一种新颖而实用的椭圆生成算法. 与同类算法相比, 该算法具有设计思想简单, 全部采用整数型运算, 并且在转折点问题的处理上有较大突破.
4.1 引 言
计算机图形学中的基本元素包括直线, 圆, 椭圆等. 目前广大学者的注意力大都集中在直线和圆弧的生成算法上, 也因此应运而生一些著名算法, 如Br esenham 直线生成算法,DDA 直线生成算法, 正负法[ 1] 、Bresenham 画圆算法
[2] 、多边形逼近法画圆[ 3] ; 而对于椭圆生成算法的研究却不十分活跃. 但生成椭圆的操作, 同样是一项经常性的操作, 因此对于椭圆生成算法的任何一个微小进步, 也同样是非常有意义的. 目前, 比较有影响的椭圆生成算法当属文献[ 4-10] , 总结上述算法发现存在以下缺点:
(1) 多处使用非常耗时的浮点运算和取整运算;
(2) 使用三角函数运算;
(3) 通过缩小整数范围来弥补执行速度的缓慢;
(4) 在算法推导过程中, 引入过多新概念, 使算法思想过于复杂;
(5) 以牺牲所使用空间范围的增加为代价, 来换取运行
的高效率.
4.2 算法的提出与算法思想 设椭圆的标准方程为
12222=+b y a x , 其中a, b 分别为椭圆的长、短轴, 圆心
()y x 00, 为坐标原点. 为了不失一般性, 如果圆心不在坐标原点, 可作相应的平移变换, 生成圆心在坐标原点的椭圆. 另外, 考虑椭圆的四分对称性, 我们
只讨论第一象限内的椭圆的生成即可.
椭圆与圆不同, 在第一象限内通常要分为2 个区域来处理, 2 个区域之间以斜率为- 1 的点( 即法向量的2 个分量相等的点) 作为分界. 从点( 0, b) 开始, 在第一象限内沿椭圆路径顺时针步进, 在区域1 内斜率大于- 1, 以X 方向作为单位步长来衡量Y 方向的走向; 当斜率变为小于- 1 时, 则转向区域2, 即以Y 方向作为单位步长来衡量X 方向的走向.
2. 1 区域1 中决策参数的判定
从图1 中A 点开始, 向右下方逐点寻找显示a 要用的点.如图2 所示, 假设P i 1-为a 上已选定的点, 根据a 的走向, 下一点应从H i 或T i 中选择. 显然应
选图1中离a 最近的点. 设H i 和T i
图1 中点在原点的标准椭圆
两点的坐标分别为()y x h h , 和()t x t t ,, 又设有一对()b a s
s ,足0*,***,**222222222222=??
? ??++??? ??+b a y a x b b a y a x b s s t s t s t s h s h t 即此椭圆弧( 长轴为a s , 短轴为b s ) 满足H i 和T i 点到该弧的距离相等. 则我们可以把这个椭圆弧s 作为一条分界线: 当a 在s 的上方时应选H i 点来显示a ; 当a 在s 的下
方时应选T i 点来显示a 。
图2 当a 在s 上方时，应当取H i ，否则取T i
本算法从区域转折点的定义入手, 即在转折点处的斜率值为- 1, 又根据椭圆方
程, 可得dy / dx =y x a b 222/2.由此可得, 在区域1和区域2的交界处
dX
dY = 1, 即y x a b 22=;则移出区域1的条件为： y x a b 22≥ (5)
为了进一步节省运算时间, 提高算法效率, 对于式( 5) 的判断, 我们采用增量式判断. 具体做法是: 在X 方向每走一步, x b 2 增加( 或减少) b 2; 在Y
方向每走一步, y a 2 增加( 或减少) a 2
, 具体实现不再详述.
另外, 在区域2 内, 我们不再把式(5) 的判断作为该区域的终止条件, 而是在进入区域2 之前, 把区域1 的最后一点的坐标记录下来, 记为X end 和Y end ; 然后, 在区域2 内, 从( a, 0) 点开始, 逆时针显示; 以Y 方向为单位
步长, 判断X 方向的变化, 从而显示区域2 内的椭圆弧. 即该区域内生成最后一点的终止条件为X = X end 且Y = Y end . 在此也省略了一些运算.
4.3、算法的复杂度分析与比较
(1) 计算量比较，表1 所示为采用本算法与常用的中点法及正负法得到椭圆弧上的任一点的计算量比较.
表1 计算量的比较
算法 除法 乘法 加减法
正负法 0 4*n 2*n
中点法 0 2*n 浮点乘 4*n
本算法 0 0 n
可以看出, 中点法使用了比较复杂又影响精度的运算,而采用本算法对于分界点问题进行处理时, 可完全不必进行如此复杂的计算.
(2) 运算时间比较本算法已在PC 机上加以验证, 取被试时间为1s, 将用本算法与用中点法生成的椭圆数进行比较, 椭圆的长、短轴分别从( 130, 160) 增加至( n+130, n+160) , 其中n 为运用该算法得到的椭圆数. 测试结果为本算法的n= 248, 中点法的n= 180.
由此可得, 若忽视长、短轴的变化所带来的时间变化, 本算法在1 s 内可生成248 个椭圆, 而中点法在1 s 内生成180个椭圆.
综上所述, 该算法与同类算法相比, 具有生成速度快且不具有突变和失真现象等优点.
参考文献:
[1] 孙家广.计算机图形学[M].北京: 清华大学出版社, 2004.
[2] 唐棣, 孙岩.一种高效的整数型椭圆生成算法[J].计算机辅助设计与
图形学学报, 2002, 14( 1) .
[3] 鲁成东.一种基于Bresenham 算法的椭圆算法[J].河南师范大学学
报, 1996, 24( 4) .
[4] 曹建忠, 孟庆波.椭圆的高质量、快速生成算法[J].华北工学院学报, 1996, 17( 1) .
[5] HOLLAND J H.Adaptation in natural and artificial system: an introduction analysis with applications to biology, control, and artificial intelligence[M].Michigan: The University of Michigan Press, 1975.
[6] 刘洪杰, 王秀峰, 王治宝.多峰搜索的自适应遗传算法[J].控制理论
与应用, 2004, 21( 2) : 302- 305.
[7] KENNEDY J, EBERHART R C.Particle swarm optimization[C] / / proceeding of IEEE Int’l Conf on Neural Networks.Piscataway, NJ: IEEE Service Center, 1995, IV: 1942- 1948.
[8] Tang Zesheng, et al. Computer Graphics' Base [ M ] . Beijing
: Tsinghua University Press, 1998. 63～72( in Chinese)
( 唐泽圣, 等. 计算机图形学基础[ M] . 北京: 清华大学出版社,
1998. 63～72)
[9] 赵京东. 一个椭圆生成算法[J]. 计算机工程与应用,2006, 35(6): 27-29.
[10] 陈震岳, 朱桂林. 基于几何关系的椭圆图形生成算法[J]. 计算机工程与科学, 2004, 26(8): 56-59.
[11] 阎双, 唐棣. 椭圆的双步生成算法[ J] . 计算机工程与应用, 2006, (33) : 65- 67.
[12] 刘凯, 侯伯亨, 等. 椭圆的双步增量生成算法及其硬件实现[ J] . 计算机辅助设计与图形学学报, 2003, 15( 4) : 393- 396.
[13]椭圆曲线著颜松远大连理工大学出版社
[14]椭圆曲线算术中的高等论题著西尔弗曼(Joseph H.Silverman) 世界图书出版公司
[15]椭圆函数(第2版) 著 https://www.wendangku.net/doc/5118319040.html,ng 世界图书出版公司
计算机图形学课程设计由：天空乐园网站郑州大学生兼职收集
由开封市同力基础工程有限公司整理出版！
椭圆曲线上的部分盲签名方案
第２７卷第４期纺织高校基础科学学报Ｖｏｌ．２７，Ｎｏ．４ ２０１４年１２月ＢＡＳＩＣＳＣＩＥＮＣＥＳＪＯＵＲＮＡＬＯＦＴＥＸＴＩＬＥＵＮＩＶＥＲＳＩＴＩＥＳＤｅｃ．，２０１４ 文章编号：１００６‐８３４１（２０１４）０４‐０５０８‐０４ 椭圆曲线上的部分盲签名方案 张建中，陈 楠，苑 飞 （陕西师范大学数学与信息科学学院，陕西西安７１００６２） 摘要：针对椭圆曲线密码体制具有签名密钥短、运行速度快等优点，结合动态秘密共享和部分盲签名技术，提出了一个新的动态部分盲签名方案．该方案不但具备门限签名和盲签名的特性而且还可以随时更新签名密钥，密钥的分发和更新过程采用公开验证的方法，可以有效地抵抗相互欺诈行为的发生．分析表明，该方案操作简单，安全性高，应用范围广． 关键词：椭圆曲线；动态秘密共享；部分盲签名；门限签名 中图分类号：ＴＰ３９３ 文献标识码：Ａ ０ 引 言 在现实生活中，人们从安全和保险的角度考虑，对一些具有重要价值的信息的访问权限不能只交给一个人掌握，如果只有一人拥有打开某信息的密钥，一旦密钥丢失或持有者无法提供正确的密钥，就会带来严重的损失．因此，１９７９年Ｓｈａｍｉｒ［１］提出了将秘钥分解成多个碎片发送给多个人掌管，其中达到一定数量的成员的集合便可以恢复密钥的（ｔ，ｎ）秘密分享的思想．秘密分享是门限密码学的基础，人们在这种思想的基础上提出了可验证的秘密分享体制［２］，公开可验证秘密分享体制［３］．为了避免密钥受到长期的、逐步的攻击，有时需要随时更新签名者的密钥，人们又提出了动态秘密分享体制［４］，其后又提出许多新的秘密共享体制［５‐６］．将这些思想与一些密码体制相结合形成了一些更安全、高效的新方案，比如基于ＲＳＡ的门限签名方案，基于ＥＬＧａｍａｌ的门限签名方案，还有基于椭圆曲线的门限签名方案等．与同等条件下的一些密码体制相比，椭圆曲线密码体制因具有签名密钥短、运行速度快、安全性高等优点而成为密码学界研究的热点．１９９２年ＳｃｏｔｔＶａｎｓｔｏｎｅ提出了椭圆曲线数字签名的算法［７］（ＥＣＤＳＡ），由于这种算法需要求解椭圆曲线上的逆元，运算复杂，经不断被改进，新的高效的椭圆曲线数字签名方案［８‐９］被提出，算法中尽量避免求解逆元，从而提高了椭圆曲线数字签名方案的运行效率． 盲签名的概念［１０］是１９８２年Ｃｈａｕｍ在美国密码学会上首次提出的，盲签名要求用户和签名者之间达成一个协议，如果协议被正确执行，则用户获得签名者的签名，但是对签名人来说却不知道所签消息的具体内容［１１］．部分盲签名［１２］是在盲签名的基础上由Ａｂｅ和Ｆｕｊｉｓａｋｉ在１９９６年提出的，在部分盲签名方案中［１３］，签名人可以在签名中嵌入一个和用户事先约定好的公共信息，用来防止普通盲签名中被签名的消 收稿日期：２０１４‐０１‐１０ 基金项目：国家自然科学基金资助项目（６１１７３１９０，６１２７３３１１）；陕西省自然科学基础研究计划资助项目（２０１０ＪＱ８０２７）； 陕西省教育厅科研计划项目（２０１０ＪＫ３９８，１２ＪＫ１００３）；中央高校基本科研业务费专项资金资助项目 （ＧＫ２０１００２０４１） 通讯作者：张建中（１９６０‐），男，陕西省周至县人，陕西师范大学教授，博士．研究方向为信息安全与密码学及认证理论．Ｅ‐ｍａｉｌ：ｊｚｚｈａｎｇ＠ｓｎｎｕ．ｅｄｕ．ｃｎ
一种椭圆曲线快速生成算法
一种椭圆曲线参数生成的快速算法 谷勇浩 刘勇 （北京邮电大学通信网络综合技术研究所） 摘要：椭圆曲线密码体制是公钥密码中的研究热点。该文介绍了椭圆曲线密码体制的基本概念及相关知识，讨论了目前基于离散对数问题的椭圆曲线密码的研究动态。本文的创新点是针对目前椭圆曲线研究重点之一——椭圆曲线参数生成算法，给出了一种生成参数a 、b 的快速算法。这种算法利用了Jacobi 符号和二次剩余的理论，并且用matlab 计算出利用这种算法生成一个椭圆曲线的平均时间，最后我们分析了今后椭圆曲线密码系统的研究方向和重点。 关键词：椭圆曲线；离散对数问题；Jacobi 符号；二次剩余；阶 1976年Diffie 和Hellman 提出公钥密码思想以来，国际上提出了许多种公钥密码体制的实现方案。一些已经被攻破，一些被证明是不可行的。目前，只有3类公钥密码体制被认为是安全有效的，按照其所依据的数学难题划分为：基于大整数分解问题（IFP ），如RSA 体制和Rabin 体制；基于有限域离散对数问题（DLP ），如Diffie-Hellman 体制和ElGamal 体制；基于椭圆曲线离散对数问题（ECDLP ），如椭圆密码体制。椭圆曲线应用到密码学上最早是由Neal Koblitz 和Victor Miller 在1985年分别独立提出的。它是目前已知的公钥体制中，对每一比特所提供加密强度最高的一种体制。它具有安全性高、密钥量小、灵活性好的特点，受到了国际上的广泛关注。而SET(Secure Electronic Transaction)协议的制定者已把它作为下一代SET 协议中缺省的公钥密码算法。深入研究基于椭圆曲线离散对数问题的公钥密码具有很大的现实意义。 1建立椭圆曲线公钥密码体制 1.1椭圆曲线域的参数 在基于椭圆曲线的加解密和数字签名的实现方案中，首先要给出椭圆曲线域的参数来确定一条椭圆曲线。在 IEEE P1363标准中，定义其参数为一个七元组：T=(q,FR,a,b,G,n,h)，其中q 代表有限域GF(q)，q 为素数或 2 m ;FR 为域表示法，如f(x)为 2 m F 域元素的不可约 多项式的表示法；曲线的方程，当q 为素数时，方程为2 3 ax b y x =++，当q 为2m 时， 方程为 2 32 xy a b y x x +=++，a,b 是方程中的系数；G 为基点；n 为大素数并且等于点G 的阶，h 是小整数称为余因子且#()/q h E n F =。主要的安全性参数是n ，因此ECC 密钥 的长度就定义为n 的长度。 1.2椭圆曲线密码的密钥 选取了基域 q F 和椭圆曲线后，得到了在有限域 q F 上的曲线E 确定的具体形式，即 上述的椭圆曲线域参数的一个七元组。每个用户选取一个整数d(1≤d ≤n-1) 作为其私钥，而以点Q=dG(G 为基点)作其公钥，这样形成一个椭圆曲线公钥密码系统。在这个密码体制中，具体的曲线，基域 q F ，基点G 及其阶n ，以及每个用户的公钥都是该系统的公开参
直线和圆弧的生成算法
第3章直线和圆弧的生成算法 3.1直线图形的生成算法 数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。 由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法（DDA）、中点画线法和Bresenham算法。 3.1.1逐点比较法 3.1.2数值微分(DDA)法 设过端点P0(x0 ,y0)、P1(x1 ,y1)的直线段为L(P0 ,P1)，则直线段L的斜率 L的起点P 的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个像素)，用L 的直线方程y=kx+b计算相应的y坐标，并取像素点(x,round(y))作为当前点的坐标。因为： y = kx i+1+b i+1 = k1x i+b+k x = y i+k x 所以，当x =1; y i+1 = y i+k。也就是说，当x每递增1，y递增k(即直线斜率)。根据这个原理，我们可以写出DDA（Digital Differential Analyzer）画线算法程序。
DDA画线算法程序： void DDALine(int x0,int y0,int x1,int y1,int color) { int x； float dx, dy, y, k； dx = x1-x0； dy=y1-y0； k=dy/dx,；y=y0； for (x=x0；x< x1；x++) { drawpixel (x, int(y+0.5), color); y=y+k; } } 注意：我们这里用整型变量color表示像素的颜色和灰度。 举例：用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 图3.1.1 直线段的扫描转换 注意：上述分析的算法仅适用于|k| ≤1的情形。在这种情况下，x每增加1,y最多增加1。当|k| 1时，必须把x，y地位互换，y每增加1，x相应增加1/k。在这个算法中，y与k必须用浮点数表示，而且每一步都要对y 进行四舍五入后取整，这使得它不利于硬件实现。
椭圆拓展(一)椭圆中的中点弦点差法
椭圆拓展（一） 椭圆内的中点弦点差法 【学习重点】 1.点差法的基本思想方法：设而不求 2.点差法适用范围：斜率固定的平行线截二次曲线所得线段 中点的轨迹，一般用于椭圆内的中点弦问题。（在圆内应该用特殊方法） 3.点差法的核心：求直线斜率和中点弦坐标的等量关系。 【核心推论】 1. 过定点直线和封闭曲线恒有公共点的充要条件是定点在曲线内部或曲线上。 过定点直线和封闭曲线恒有两个公共点的充要条件是定点在曲线内部。 2. 斜率为k1的直线，交椭圆x2 a2 + y2 b2 =1 (a>b>0)于两点，弦中 点与原点连线的斜率为k2，则k1?k2= b2 a2。
斜率为k 1的直线，交椭圆 y 2a 2 x 2b 2 =1 (a>b>0)于两点，弦 中点与原点连线的斜率为k 2，则 k 1?k 2= 2。 3. 平行弦的中点轨迹方程是过原点的、一条无端点、取椭圆内部分的线段。 【重点例题解析】 例题 已知P(-3,0),过点P 作直线l 交椭圆 x 2 4 +y 2 =1 于A 、 B 两点，求A 、B 的中点M 的轨迹方程。 解：设A(x 1,y 1)、B(x 2,y 2)、 x 1 2 4 +y 12 =1 x 22 4 +y 22 =1 x 12 -x 2 2 4 +(y 12-y 22 )=0 14 (x 1+x 2)(x 1-x 2) +(y 1+y 2)(y 1-y 2)=014 (x 1+x 2)+(y 1+y 2) (y 1-y 2)(x 1-x 2) =0
∴轨迹方程为： 14 (2x)+(2y)?k AB =0 14 (2x)+(2y)?k MP =0 14 (2x)+(2y)? y x+3 =0 x 2 +3x+4y 2 =0 (取x 2 24 +y 22 =1的内部）
椭圆曲线加密算法
椭圆曲线加密算法 椭圆曲线密码学（英语：Elliptic curve cryptography，缩写为 ECC），一种建立公开密钥加密的算法，基于椭圆曲线数学。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。 ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA 加密算法——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长 1.椭圆曲线 在数学上，椭圆曲线（英语：Elliptic curve，缩写为EC）为一代数曲线，被下列式子所定义 y2=x3+ax+b 其是无奇点的；亦即，其图形没有尖点或自相交。 满足此条件的a b满足：4a3+27b2≠0 图1 在基础上需要定义一个无穷远的点，将此点作为零点：此时椭圆曲线定义为：{(x,y)∈?2|y2=x3+ax+b,4a3+27b2≠0}∪{0} 在椭圆曲线中的群的运算律： 1. 所有的点都在椭圆曲线上 2. 0点作为群上的单元点即 P+0=P 3. P点关于X轴的对称点为P点的逆即 P+(?P)=0
4.对于位于同一条直线上的三个点P,Q,R.则有 P+Q+R=0 图2 P+Q+R=0（无限远点 P Q R三个点的位置是任意的，他们满足加法的结合律，因为这个群是一个阿贝尔群。 2.椭圆曲线加法 当P和Q不相等时(x P≠x Q) 由于是在阿贝尔群上可以将P+Q+R=0改写为P+Q=?R所以在椭圆曲线上的加法定义为P Q 两点加法为P,Q两点连线与曲线的交点R的关于X轴对称点?R 图2-3 P+Q=-R P Q两点的直线的斜率为： m=y P?y Q x P?x Q 这条线与曲线的交点为：R=(x R,y R) x R=m2?x P?x Q y R=y P+m(x R?x P) 因此(x P,y P)+(x Q,y Q)=(x R,?y R)如果在图上表示即为上述的P+Q=?R
数字积分圆弧第一二三四象限顺逆插补计算
数控技术课程设计说明书 设计题目：数字积分法圆弧插补计软件设计指导老师： 专业：机械设计制造及其自动化 班级：机 姓名： 学号：
目录 一、课程设计题目 (1) 二、课程设计的目的 (1) 三、课程设计使用的主要仪器设备 (1) 四、课程设计的任务题目描述和要求 (1) 五、数字积分法插补原理 (2) 5.1从几何角度来看积分运算 (2) 5.2数字积分圆弧插补 (3) 5.3数字积分法圆弧插补程序流程图 (5) 5.4插补实例 (6) 六、程序清单 (7) 七、软件运行效果仿真 (18) 八、课程小节 (21) 九、参考文献 (22)
一、课程设计题目 数字积分法第一、二、三、四象限顺、逆圆插补计算 二、课程设计的目的 《数控原理与系统》是自动化（数控）专业的一门主要专业课程，安排课程设计的目的是通过课程设计方式使学生进一步掌握和消化数控原理基本内容，了解数控系统的组成，掌握系统控制原理和方法，通过设计与调试，掌握各种功能实的现方法，为今后从事数控领域的工作打下扎实的基础。 1)了解连续轨迹控制数控系统的组成原理。 2) 掌握数字积分法（DDA）插补的基本原理。 3）掌握数字积分法（DDA）插补的软件实现方法。 三、课程设计使用的主要仪器设备 1、PC计算机一台 2、数控机床实验装置一台 3、支持软件若干（选用VB环境） 四、课程设计的任务题目描述和要求 数字积分法又称数字微分分析法DDA(Digital Differential Analyzer)。数字积分法具有运算速度快、脉冲分配均匀、易于实现多坐标联动及描绘平面各种函数曲线的特点，应用比较广泛。其缺点是速度调节不便，插补精度需要采取一定措施才能满足要求。由于计算机有较强的计算功能和灵活性，采用软件插补时，上述缺点易于克服。 本次课程设计具体要求如下： （1）掌握数字积分插补法基本原理 （2）设计出数字积分（DDA）插补法插补软件流程图 （3）编写出算法程序清单算法描述（数字积分法算法在VB中的具体实现）（4）要求软件能够实现第一、二、三、四象限顺、逆圆插补计算 （5）软件运行仿真效果插补结果要求能够以图形模式进行输出
中点画椭圆法实验报告
一、实验目标 1.了解中点画椭圆法的基本思想； 2.掌握中点画椭圆法的基本步骤。 二、实验内容 本次实验要解决的问题主要是中点画椭圆法，椭圆中心不在原点及长轴和短轴任意长度的画椭圆问题。 原理简述：中点法依据椭圆斜率将第一像限的椭圆(b ≤a)分成两部分。根据 斜率变化确定步长方向：斜率绝对值小于1的区域1内x 方向取单位步长；斜率绝对值大于 1的区域2内y 方向取单位步长。 椭圆对称性质：椭圆分别关于X 轴、Y 轴对称。因此在计算椭圆生成的时候，只需要计算1/4个椭圆，经过对称原理就可以实现其他3/4个椭圆的生成了，即：计算出目标点（x,y ）的坐标，必然存在（x,-y ）、（-x,y ）（-x,-y ）。此方案中采用计算第一象限中椭圆的生成，即：计算x=0到y=0的1/4的椭圆。先通过平移的方法将假设椭圆中心在坐标原点，然后计算，最后再平移到真实中心位置。 三、实验步骤 一、打开cgdemoMFC 工程 1.打开Microsoft Visual Studio 2008 2.File-->Open-->cgdemo.sln 二、添加菜单 1.左侧视图栏中有三个视图：ClassView 、ResourceView 、FileView ，点击 ResourceView 2.展开cgdemo ，展开Menu ，双击IDR_MAINFRAME 第一象限椭圆区域划分 区域1：椭圆切线斜率小于1； 区域2：椭圆切线斜率大于1。
3.在右侧窗口菜单栏中找到“基本图形生成”菜单项，在该菜单项中添加“中点画圆法”，在“中点画圆法”属性框中找到ID框填：ID_LINE_ELLIPSE。 三、创建、编辑函数 1.打开cgdemoView.h头文件，在cgdemoView类枚举类型成员变量m_drawstyle中添加LINE_ELLIPSE。 2.给菜单项“中点画椭圆法”添加命令消息响应函数OnLineCircle()在该函数中添加以下程序代码。 void CcgdemoView::OnLineEllipse() { // TODO: Add your command handler code here m_drawstyle=LINE_ELLIPSE; Invalidate(true); } 3.在鼠标左键按下消息响应函数中添加当m_drawstyle为LINE_ELLIPSE时的情况，代码如下所示。 void CcgdemoView::OnLButtonDown(UINT nFlags, CPoint point) { // TODO: Add your message handler code here and/or call default switch(m_drawstyle) { case LINE_DDA: case LINE_MIDPT: case LINE_ELLIPSE: } 4.在鼠标移动消息响应函数中添加m_drawstyle为LINE_CIRCLE时的情况，代码如下所示。 void CcgdemoView::OnMouseMove(UINT nFlags, CPoint point) { // TODO: Add your message handler code here and/or call default switch(m_drawstyle) { case LINE_DDA: case LINE_MIDPT: case LINE_ELLIPSE: } 5.在cgdemoView.h头文件类中添加成员函数void MidpointEllipse(CDC* pDC, int x0,int y0,int x1, int y1,int color);并在cgdemoView.cpp源文件中void CcgdemoView::MidpointEllipseCDC* pDC,int x0,int y0,int x1,int y1,int color)为其 添加我们编写的中点画椭圆法代码；在中点画圆法中我们要计算两点之间的距离
圆弧加减速插补算法
机电工程学院 数控加工技术课程设计——插补算法实现 学号：S311077006 专业：机械工程 学生姓名：胡晓锋 任课教师：李霞副教授 2011年4月
基于PC的圆弧曲线加减速算法实现 插补算法一直以来就是数控系统中的核心技术。从数控系统的原理来说，插补的本质问题就是对任意曲线进行分解，成为若干段微小的曲线，当对曲线的分解达到无穷级时，每一段曲线便成为微小的直线段。然后利用与相应微小曲线相类似的直线段代替，通过控制刀具按直线段行走进行加工，完成为整个曲线的插补运算加工。实际问题中不可能对任意曲线的分解达到无穷，因此总是存在相应的误差。然而在实际运用中对误差的容忍度有限，因此只需在满足精度的情况下进行曲线的分解。对曲线的分解过程即是将其坐标点进行密化，不但要保证精度，还需要在极短的时间内完成。受现代技术的限制，这一过程目前还存在一定的问题。由此而产生的对插补算法的研究也一直没有停止过，从经典的逐点比较法到现在的自由曲面直接插补法，各种算法层出不穷。 本次对圆弧的插补算法是基于PC技术的算法，利用MATLAB软件编写相应的插补程序，实现对插补轨迹的模拟与分析。 一、问题描述 本次设计针对圆弧曲线进行插补，采用加减速的方式完成刀具的行走过程。根据数据采样插补原理，实现数控轨迹的密化。本次插补的难点在于对刀具行走轨迹的自动加减速进行控制，由控制器发出相应指令，当刀具以不同速度运行到不同位置时，能够根据当前的状态判断下一个插补周期需要的状态，从而连续平滑的完成插补过程。 二、速度曲线的数学表达式 刀具在进行插补时的速度应该是一个加速-匀速-减速的过程，各个过程与时间的关系应该由相应的加速度来控制。因此曲线的形状呈现一定的抛物线形。 另初始进给速度为F1，末端进给速度为F2，指令速度为F，当前速度为V，减速距离为S，当前距离为CS，n为插补周期个数，t为当前时刻。则速度的数学表达式如下： (F1
直线和圆弧的生成算法讲课稿
直线和圆弧的生成算 法
第3章直线和圆弧的生成算法 3.1直线图形的生成算法 数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。 由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法（DDA）、中点画线法和Bresenham算法。 3.1.1逐点比较法 3.1.2数值微分(DDA)法 设过端点P0(x0,y0)、P1(x1,y1)的直线段为L(P0,P1)，则直线段L的斜率 L的起点P0的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个像素)，用L的直线方程y=kx+b计算相应的y坐标，并取像素点(x,round(y))作为当前点的坐标。因为： y i+1= kx i+1+b = k1x i+b+k?x = y i+k?x
所以，当 x =1; y i+1= y i+k。也就是说，当x每递增1，y递增k(即直线斜率)。根据这个原理，我们可以写出DDA（Digital Differential Analyzer）画线算法程序。 DDA画线算法程序： void DDALine(int x0,int y0,int x1,int y1,int color) { int x； float dx, dy, y, k； dx = x1-x0； dy=y1-y0； k=dy/dx,；y=y0； for (x=x0；x< x1；x++) { drawpixel (x, int(y+0.5), color); y=y+k; } } 注意：我们这里用整型变量color表示像素的颜色和灰度。 举例：用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5
椭圆离心率的三种求法中点弦方程三种求法
椭圆离心率的三种求法： (1)若给定椭圆的方程，则根据焦点位置确定a 2，b 2，求a ，c 的值，利用公式e ＝c a 或利用 22 1a b e -=直接求解. (2)求椭圆的离心率时，若不能直接求得c a 的值，通常由已知寻求a ， b ， c 的关系式，再与a 2 ＝b 2＋c 2组成方程组，消去b 得只含a ，c 的方程，再化成关于e 的方程求解. (3)求离心率时要充分利用题设条件中的几何特征构建方程求解，从而达到简化运算的目的. 涉及椭圆离心率的范围问题要依据题设条件首先构建关于a ，b ，c 的不等式，消去b 后，转化为关于e 的不等式，从而求出e 的取值范围. 1. 若椭圆x 2a 2＋y 2b 2＝1(a ＞b ＞0)的左、右焦点分别为F 1，F 2，线段F 1F 2被点??? ??0,2b 分成5∶3 的两段，则此椭圆的离心率为( ) A.1617 B.41717 C.45 D.25 5 解析 依题意，得c ＋b 2c －b 2 ＝5 3，∴c ＝2b ，∴a ＝ b 2＋ c 2＝5b ，∴e ＝ 2b 5b ＝255. 答案D 点评 本题的解法是直接利用题目中的等量关系，列出条件求离心率. 2. 设P 是椭圆x 2a 2＋y 2 b 2＝1(a ＞b ＞0)上的一点，F 1，F 2是其左，右焦点.已知∠F 1PF 2＝60°， 求椭圆离心率的取值范围. 分析 本题主要考查椭圆离心率取值范围的求法，建立不等关系是解答此类问题的关键. 解 方法一 根据椭圆的定义，有|PF 1|＋|PF 2|＝2a .① 在△F 1PF 2中，由余弦定理，得 cos 60°＝|PF 1|2＋|PF 2|2－|F 1F 2|22|PF 1||PF 2|＝1 2， 即|PF 1|2＋|PF 2|2－4c 2＝|PF 1||PF 2|.② ①式平方，得|PF 1|2＋|PF 2|2＋2|PF 1||PF 2|＝4a 2.③ 由②③，得|PF 1||PF 2|＝4b 2 3 .④
基于椭圆曲线的一种高效率数字签名
第26卷第2期 计算机应用与软件 Vol 126No .2 2009年2月 Computer App licati ons and Soft w are Feb .2009 基于椭圆曲线的一种高效率数字签名 侯爱琴 高宝建 张万绪 强 媛 (西北大学信息科学与技术学院 陕西西安710069) 收稿日期:2007-07-09。陕西省自然科学基金项目(2004A11)。侯爱琴,讲师,主研领域:信息安全,电子信息技术。 摘 要 为给出一种基于椭圆曲线密码的高效率的数字签名方案。不仅在算法设计时完全避免了费时的求逆运算,而且利用消 息HASH 值的汉明重量作为消息摘要进行签名与验证。结果在同等安全性下,该方案比通用的ECDS A 等方案运行时间更短。新方案可适用于网络等对签名实时性要求较高的场合。 关键词 椭圆曲线密码 哈希函数 汉明重量 椭圆曲线数字签名 A H I GH EFF IC I ENCY D IG ITAL S IGNATURE BASED O N ELL I PT IC CURVE Hou A iqin Gao Baojian Zhang W anxu Q iang Yuan (School of Infor m ation Science and Technology,N orthw est U niversity,X i ’an 710069,Shaanxi,China ) Abstract T o offer a high efficiency digital signature based on elli p tic curve cryp t ography .The design of the algorith m not only avoids ti m e 2costing inverse operati on comp letely but als o uses the hamm ing weight of HASH code of a message instead of HASH code itself as the message digest t o partici pate in the signature and verifying calculati on .The ne w scheme cost less ti m e than the popular EC DS A.The ne w sche me is a 2dap ted t o higher real 2ti m e needs f or signature such as internet . Keywords Elli p tic curve cryp t ography (ECC ) Hash Ha mm ing weight Elli p tic curve digital signature (EC DS A ) 0 引 言 数字签名是电子商务和网络安全认证的核心技术。基于公钥密码的数字签名体制一般有三类:基于大整数分解问题(I FP )的,如RS A;基于离散对数问题(DLP )的,如著名的E I Ga 2mal,DS A 等;基于椭圆曲线离散对数问题(EC DLP )的,如I EEE P1363标准中的EC DS A 等椭圆曲线数字签名。其中ECDLP 最难解,除几类特殊椭圆曲线外迄今没有找到有效的求解算法。椭圆曲线密码(ECC )是迄今为止每比特具有最高安全强度的密码系统,160位ECC 密钥的安全性能与1024位RS A 或ElGa mals 的密钥相当。 本文研究了以椭圆曲线密码理论为基础的一种高效率数字签名系统。 1 基于ECC 的数字签名方案分析 现有的椭圆曲线数字签名方案,典型的如ECDS A 是美国国家标准技术研究所(N I ST )出台的ANSI X9.62标准,其详细描述可参见文献[1-3];EC 2KC DS A 方案是韩国基于证书数字签名算法(KC DS A )的椭圆曲线版本,具体方案可参见文献[1]描述。还有E I Ga mal 方案等都是将有限域F p 上离散对数签名方案移植到椭圆曲线群上。 据文献[4]把一个传统的离散对数体制转变为椭圆曲线体制需要进行以下转换:①把模乘运算转变为椭圆曲线上的点加运算;②把模幂运算转换为椭圆曲线上的点乘运算。 而有限域F p 上离散对数签名方案一般是基于签名方程u =dv +kw (mod p -1),详见文献[5,6]。它由五个元素(d,k,u, v,w )组成,其中d 是签名者的密钥,k 是每次签名时生成的随机 整数(即消息密钥),u,v,w 可以分别取e,r ,s,其中,e =h (m )为被签名消息的Hash 值,r 是一个与k 有关的量,s 是消息m 的签名。 可以用不同的(e,r ,s )组合代替(u,v,w ),并且e,r,s 可分别换成其加法或乘法逆元,由此可以衍生出不同的签名方程,即可得到不同的数字签名方案。但不是所有的数学组合都能产生安全的数字签名方案,Harn 和Xu 给出了安全的离散对数签名方案的设计规则,并列出所有符合这种设计规则的数字签名方案[7]。 基于ECC 的E I Ga mal 方案和EC DS A 是其中的第(4)种方案,取u =e,v =r ,w =s,即为通用方程u =vd +kw (mod p )的变体:e =dr +ks,等价于s =k -1(e +dr ),该方程为EC DS A 签名方程;相应的验证方程s -1(eG +r Q )=kG 。 ECDS A 方案中的公钥产生算法是Q =dG,在签名的生成和验证时分别计算k -1mod n 和s -1mod n ,需要模逆运算。EC 2 KC DS A 方案最大的特点是公钥产生算法是Q =d -1 P ,采用了逆的预运算,这使得签名的生成和验证过程不需要进行模逆运算;EC 2KC DS A 方案的另一个特点是在计算消息的Hash 值前,将签名者的证书数据加入消息(计算e =H (hcert,m )),能够抵抗基于参数组数据的攻击。 在现有的椭圆曲线加密或者签名过程中,求逆是最费时的操作,一次求逆的时间大约相当于80次点乘运算,因而求逆是
基于FPGA的逐点比较圆弧插补算法设计
二○一三届毕业设计 基于FPGA逐点比较圆弧插补算法设计 学院：电子与控制工程学院 专业：电子科学与技术 姓名：…….. 学号：……… 指导教师：…….. 完成时间：2013年5月 二〇一三年五月
摘 要 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 摘 要 本课题主要是研究基于VHDL 实现数控系统中的逐点比较圆弧插补，要求圆弧运动过程平滑，在各象限能顺利过渡，并有较小的设计误差，能与运动控制部分很好的集成，实现较高的切割频率。 本课题采用QuartusII 软件来调试程序，并进行波形仿真。主要的工作如下： 1） 理解数控系统中逐点比较圆弧插补算法的原理及其实现方法； 2） 通过硬件描述语言VHDL 在FPGA 上实现上述算法； 3） 完成圆弧插补的仿真与测试。 关键词：VHDL ，FPGA ，逐点比较法，QuartusII
ABSTRACT ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ABSTRACT This topic mainly studies based on VHDL realization of point by point comparison circular arc interpolation in nc system, the movement for arc process smooth, in each quadrant can smooth transition, and a relatively small design error, can very good integration with motion control part, realize the high frequency of cutting. This subject adopts software QuartusII to debug program and waveform simulation. The main work is as follows: 1. Understand CNC system the principle of point by point comparison in circular arc interpolation algorithm and its realization method 2. Through the hardware description language VHDL FPGA to realize the above algorithms. 3. Finish arc interpolation of simulation and test KEY WORDS : VHDL, FPGA, point-by-point comparison, QUARTUS II
直线、圆、椭圆的生成算法
计算机科学与技术学院 2012－2013学年第一学期《计算机图形学》实验报告 班级：100341C 学号：100341328 姓名：魏然 教师：惠康华 成绩：
实验项目:直线、圆、椭圆的生成算法 一、实验目的与要求 （1）了解Visual C++等编程环境中常用控件命令与绘图函数，初步掌握在实验设计集成环境（IDE）下进行图形处理程序的设计方法。 （2）熟练掌握直线的3种扫描转换算法：DDA算法，中点算法和Bresenham算法。 （3）掌握中点画圆算法、圆的Brensenham算法和椭圆的中点算法。 二、实验内容 （1）在Visual C++环境中设计MFC单文档程序，利用消息处理函数，搭建能运行图形算法程序的平台。（2）在平台中使用已有的点、线、圆等绘图函数，设计一个平面图形。Visual C++基本绘图函数可参考有关文献。 （3）根据教材中给定的算法，实现直线段的3种生成算法：DDA算法，中点法和Bresenham算法。（4）根据教材中给定的算法，实现圆与椭圆的生成算法。 三、重要算法分析 （一）、直线的生成 1、DDA算法 定义直线两端点和直线颜色：整型变量 x0=?, y0=?,x1=?,y1=?,c=颜色; 定义整型变量x,y,i；浮点数dx,dy,k; 根据数学算法得到斜率k, k=dy/dx,其中dx=(float)(x1-x0),dy=(float)(y1-y0); 定义x=x0;y=y0; 通过对x和y各增加一个小增量，计算下一步的x、y值。 当k的绝对值小于1的时候，标记一个像素点,像素点的坐标为(x，int（y+0.5），c)，y=y+k,如果x=x i,则停止； 当k的绝对值大于或等于1的时候，标记一个像素点,像素点的坐标为(int(x+0.5)，y，c)，x=x+1/k,如果y=y i,则停止； 2、中点算法 定义直线两端点和直线颜色：整型变量 x0=?, y0=?,x1=?,y1=?,c=颜色; 定义浮点数：a,b,d1,d2,d,x,y;
基于椭圆曲线和RSA的数字签名的性能分析,数字签名,椭圆曲线
基于椭圆曲线和RSA的数字签名的性能分析，数字签名，椭圆曲线密码体制，RSA，C++ 1引言数字签名是实现认证的重要工具，他在身份认证、数据完整性、抗抵赖性以及匿名性等方面有重要的应用，是电子商务应用、电子政务推广中的核心技术，数字签名能保证文件中每页内容均不会被改动或替换。数字签名是特指以公钥密码实现的签名，或者可以定义为记录的一次变换，通过一个非对称密码系统和一个杂凑函数，使得有初始记录和签名者公钥的任何人都可以准确地判断该变换是否由相对应的私钥产生、初始记录在变换之后是否被修 1 引言 数字签名是实现认证的重要工具，他在身份认证、数据完整性、抗抵赖性以及匿名性等方面有重要的应用，是电子商务应用、电子政务推广中的核心技术，数字签名能保证文件中每页内容均不会被改动或替换。数字签名是特指以公钥密码实现的签名，或者可以定义为记录的一次变换，通过一个非对称密码系统和一个杂凑函数，使得有初始记录和签名者公钥的任何人都可以准确地判断该变换是否由相对应的私钥产生、初始记录在变换之后是否被修改。 常用的数字签名体制：RSA，EIGamal，ECC。其中基于RSA的数字签名算法现在应用十分广泛，而基于ECC的数字签名算法ECDSA则是未来签名算法的热点方向，本文就两种算法的性能进行了分析和比较，同时讨论了各自的应用范围。 2 RSA的数字签名算法 RSA算法是公钥密码体制中最著名的算法，他是以其发明人Rivest，Shamir和Adleman三人的首字母来命名的。RSA是建立在大整数分解的困难上的，是一种分组密码体制。RSA即可用于数据加密，也可用于数字签名。 2．1 RSA数字签名算法密钥对产生的过程 (1)选择2个大的素数p，q。 (2)计算n：n=pq。 (3)随机选取e，满足1<e<φ(n)，gcd(e．φ(n))=1，那么公钥就是(e，n)。 (4)计算d：满足ed=1modφ(n)，那么私钥就是(d，n)。 2．2 RSA数字签名算法的签名过程
快速判断直线与椭圆位置关系的方法
快速判断直线与椭圆位置关系的方法（原创） 四川省宜宾县第二中学 傅小力 在解决椭圆的选择、填空问题中需要快速判断与坐标轴不平行的直线0:=++C By Ax l 和椭圆)0(122 22 >>=+b a b y a x 的位置关系时，我建议我的学生： 第一步：找出直线与坐标轴的交点，判断是否在已知椭圆内部或在椭圆上， 否，则第二步：设椭圆上任一点P （θθsin ,cos b a ）， C By Ax m ++=，则 C b B a A C Bb Aa m +++=++=)sin(sin cos 2222?θθθ， 其中R Bb Aa ∈=θ?,tan ， 故],[22222222 b B a A C b B a A C m +++-∈。 结合线性规划的知识，结论如下： ① 若0>m 恒成立 即0>++C By Ax 恒成立，则椭圆上的点都在直线l 的同一侧，故直 线l 与椭圆相离；若0
§3.2圆、圆弧的生成—Bresenham算法
§3.2圆的生成——Bresenham算法 条件：给定圆心(x c,y c)和半径R 约定：只考虑圆心在原点，半径为整数R的圆x2+y2.=R2。对于圆心不在原点的圆，可先通过平移转换，化为圆心在原点的圆，再进行扫 描转换，把所得到的像素集合加上一个位移量，就可以把目标圆光 栅化。 在众多圆的生成算法，如逐点比较法、角度DDA法、Bresenham算法中，Bresenham画圆法是一种最简单有效的的方法。 首先注意到只要生成一个八分圆，那么，圆的其它部分就可以通过一系列的对成变换得到。 1 2 3 4 5 6 7 8 由算法生成 y=x 第一八分圆关于y=x对称变换 第一四分圆关于x=0对称变换 上半圆关于y=0对称变换 如果以点x=0，y=R为起点按顺时针方向生成圆，则在第一象限内y是x 的单调递减函数。 要在这三个像素中选择一个使其与理想圆的距离的平方达到最小，即下 列数值中的最小者。 R
(0,R) (R,0) x y 这样，从圆上任一点出发，按顺时针方向生成圆时，为了最佳逼近该圆，对于下一像素的取法只有三种可能的选择，即正右方像素、正下方像素和右下角像素，分别记作：m H、m V、m D。 (x i，y i) (x i，y i-1) (x i+1，y i) (x i+1，y i-1) m H m D m V m H=|(x i+1)2+(y i)2-R2| m V=|(x i)2+(y i+1)2-R2| m D=|(x i+1)2+(y I-1)2-R2| m H (x i,y i) (x i+1,y i) (x i+1,y i+1) (x i+1,y i-1) (x i-1,y i-1) (x i,y i-1) m V m D 1 2 3 5 4 圆与点(x i，y i)附近光栅格网的相交关系只有五种可能。
椭圆曲线参数选取
关于SM2椭圆曲线参数选取 一．安全的椭圆曲线的选取 1.椭圆曲线上的公钥密码体制的安全性是建立在椭圆曲线离散对数的基础上, 但并不是所有椭圆曲线都可以应用到公钥密码体制中, 为了保证其安全性, 必须选取安全椭圆曲线,即只有选到合适的有限域GF(p)和椭圆曲线(ECC)，能够抵抗攻击ECDLP算法的攻击，才能保证所选ECC的安全性。 若某椭圆曲线存在优于n1/2级（n是基点阶次）计算复杂度的攻击方法，则称此曲线为弱椭圆曲线。Fp上的超奇异椭圆曲线（有限域Fp的特征整除q+1-#E（Fp））和Fp上的异常曲线（#E（Fp）=p）都是弱椭圆曲线。（国密局文档p4，p25A.4抗攻击椭圆曲线满足的条件）。下面是选取曲线时应遵循的原则：（一种椭圆曲线参数生成的快速算法） （1）为了抗击Pollard-ρ攻击，所选取椭圆曲线的阶#E(GF(p))的分解式中应该包含一个大的素数因子，目前应不小于160bit； （2）为了抗击Weil对和Tate对的攻击，对于1≤k≤30，n不能除p k-1（不宜选取超奇异椭圆曲线）； （3）为了抗击Semaev-Smart-Satoh-Araki的攻击所选曲线的阶不能等于该曲线所定义的有限域的阶，即#E(F P)≠p（不宜选取异常椭圆曲线）； （4）对于二进制域GF(2m)的度m不宜为合数。Gaudry，Hess和Smart 提出，若m有小约数l（l=4），存在比Pollard's rho算法更快求解ECDLP 的方法。 （5）选择GF(p)的子域H，满足它的阶|H| 是#E 的最大素因子n，并在H 上实现ECC。
2.一般来说有4 种寻找安全椭圆曲线的方法:（椭圆曲线密码体制及其参数生成的研究.2006.DR） (1) 有限域GF( p) 上随机生成一椭圆曲线, 直接计算其阶, 判断阶是否为大素数或含大素数因子, 若是即确定,否则继续选取曲线, 直至符合条件。 (2) 取具有一定特殊性椭圆曲线的系数, 计算该椭圆曲线的阶, 对该阶进行判断, 直至找到所需要的安全曲线。 (3) 如果p = 2m , 其中m 能被一个比较小的整数d 整除, 首先在有限域GF( p1 ) ( p1 = 2 d ) 上选择一椭圆曲线E，并计算其阶, 根据此值, 利用Weil 定理[ 2] 计算该曲线在其扩域GF( p) 上的阶, 若此阶符合安全标准, 再找曲线E在域GF( p) 上的嵌入E, 则E 即为所需的安全椭圆曲线。 (4) 首先给出具有安全条件的曲线阶, 然后构造一具有此阶的椭圆曲线。目前国内外比较流行的计算椭圆曲线阶的算法有complex multiplication 算法、SEA 算法、Satoh 算法。应用广泛的椭圆曲线公钥密码体制( ECC) 中大多是基于特征2 的有限域上。 3.尽管ECC的参数选取方法有许多种，应用最多的是随机选择方法，它是根据任意给定曲线的系数，计算曲线的阶直到找到素数(或近素数)阶的椭圆曲线。 （1）参数p的选取：p当然越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求； （2）参数a、b的选取：已知素域的规模p，求解比特串SEED及Fp中的元素a，b(D.1p37参数生成)