下载文档原格式
ecc椭圆曲线算法摘要：1.椭圆曲线算法简介2.椭圆曲线算法的数学原理3.椭圆曲线算法在加密和解密中的应用4.椭圆曲线算法的优势和局限性5.椭圆曲线算法在现代加密技术中的地位正文：椭圆曲线算法（ECC，Elliptic Curve Cryptography）是一种基于椭圆曲线数学模型的公钥加密算法。
它与RSA和离散对数一样，也是基于一个数学求解的难题，但是它的难度比RSA和离散对数都要大。
椭圆曲线算法的数学原理是利用椭圆曲线上的点加和乘法运算。
在椭圆曲线上，任意两个点可以通过加法或乘法生成一个新的点。
通过这种运算，我们可以实现公钥和私钥的生成，以及数字签名的生成和验证。
椭圆曲线算法在加密和解密中的应用主要包括以下几个步骤：1.密钥生成：通过椭圆曲线上的点加和乘法运算，生成公钥和私钥。
2.加密：利用公钥对数据进行加密，生成密文。
3.解密：利用私钥对密文进行解密，还原原始数据。
4.数字签名：利用椭圆曲线算法生成数字签名，用于验证数据的完整性和真实性。
椭圆曲线算法具有以下优势：1.安全性高：由于椭圆曲线算法的数学难题难度较大，使得破解所需的计算量极大，从而保证了数据的安全性。
2.密钥长度短：相较于RSA算法，椭圆曲线算法所需的密钥长度更短，从而降低了密钥管理和传输的难度。
3.资源消耗低：椭圆曲线算法的计算复杂度较低，对计算资源的消耗较小。
然而，椭圆曲线算法也存在一定的局限性：1.兼容性问题：相较于RSA算法，椭圆曲线算法在某些应用场景中可能存在兼容性问题。
2.性能问题：在某些计算环境下，椭圆曲线算法的性能可能不如RSA算法。
尽管如此，椭圆曲线算法在现代加密技术中仍然具有重要的地位。
随着量子计算技术的发展，椭圆曲线算法的安全性可能会受到更大的挑战。
一种椭圆曲线参数生成的快速算法谷勇浩 刘勇（北京邮电大学通信网络综合技术研究所）摘要：椭圆曲线密码体制是公钥密码中的研究热点。
该文介绍了椭圆曲线密码体制的基本概念及相关知识，讨论了目前基于离散对数问题的椭圆曲线密码的研究动态。
本文的创新点是针对目前椭圆曲线研究重点之一——椭圆曲线参数生成算法，给出了一种生成参数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 为素数或2m ;FR 为域表示法，如f(x)为2m F 域元素的不可约多项式的表示法；曲线的方程，当q 为素数时，方程为23ax b y x =++，当q 为2m时，方程为232xy a b y x x +=++，a,b 是方程中的系数；G 为基点；n 为大素数并且等于点G 的阶，h 是小整数称为余因子且#()/q h E n F =。
计算机图形学实验03
《计算机图形学》实验报告
圆（椭圆）的生成算法
一、实验教学目标与基本要求
1．实现圆的生成算法；
2．实现椭圆的生成算法；
二、实验课程内容 (2学时)
1．写出完整的圆的Bresenham生成算法；
2．写出完整的椭圆的中点生成算法；
三、算法思想
1．圆的Bresenham生成算法：
如果我们构造函数 F(_,y)=_+y-R，则对于圆上的点有F(_,y)=0，对于圆外的点有F(_,y)_gt;0，对于圆内的点F(_,y)_lt;0 。
与中点画线法一样，构造判别式:d=F(M)=F(_p+1,yp-0.5)=(_p+1)+(yp-0.5)-R。
若d_lt;0，则应取P1为下一象素，而且再下一象素的判别式为：
222d=F(_p+2,yp-0.5)=(_p+2)+(yp-0.5)-R=d+2_p+3
若d≥0，则应取P2为下一象素，而且下一象素的判别式为：
d=F(_p+2,yp-1.5)=(_p+2)+(yp-
1.5)-R=d+2(_p-yp)+5我们这里讨论的第一个象素是（0,R），判别式d的初始值为：d0=F(1,R-0.5)=1.25-R。
为了进一步提高算法的效率，将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。
2．椭圆的中点生成算法：
椭圆中点生成算法是将椭圆在第一象限中分为两个部分：
1)对于斜率绝对值小于1的区域内在_方向取单位量；
2)对于斜率绝对值大于1的区域内在y方向取单位量；
斜率可以通过椭圆的标准方程中获得为K = - (ry_ry)__/(r__r_)_y;这里中点椭圆222222222。
椭圆曲线加密算法实现椭圆曲线加密算法(ECDSA)的实现涉及到椭圆曲线的参数选择、密钥生成、签名和验证等过程。
1. 参数选择：要实现椭圆曲线加密算法，首先需要选择合适的椭圆曲线参数。
常用的椭圆曲线参数有两种类型：素数域曲线和二进制域曲线。
参数选择需要考虑安全性和效率。
常见的参数选择有NIST提供的曲线参数。
2. 密钥生成：椭圆曲线加密算法使用椭圆曲线上的点作为密钥。
生成密钥的步骤如下：- 随机选择一个私钥k，私钥范围在[1, n-1]之间，n为椭圆曲线的阶。
- 计算公钥P = kG，其中G为椭圆曲线上的基点。
- 公钥P和私钥k即为加密算法的密钥对。
3. 签名：签名的过程包括选择消息的哈希算法、生成签名的随机数、计算签名值等步骤。
- 随机选择一个正整数r，使得1<=r<n。
- 计算椭圆曲线上的点R = rG。
- 计算r对于素数n的模反元素s，即s = r^(-1) (mod n)。
- 计算签名值sig = (R, s)，其中R为点，s为整数。
4. 验证：验证签名的过程包括计算验证签名的哈希值、计算验证点和比较验证点与签名值中的点的情况。
- 计算消息的哈希值。
- 计算签名值sig中的s的模反元素w，即w = s^(-1) (mod n)。
- 计算u1 = hash(m)w (mod n)和u2 = Rw (mod n)。
- 计算验证点X = u1G + u2P。
- 如果X的x坐标和签名的R的x坐标相等，验证成功；否则，验证失败。
上述是椭圆曲线加密算法(ECDSA)的基本实现步骤，具体实现过程需要参考具体的编程语言和密码学库的文档和示例代码。
椭圆的生成算法原理椭圆是数学中一个重要的几何图形，其形状类似于拉伸的圆，具有许多特殊的性质和应用。
椭圆的生成算法是指通过一系列步骤和公式来确定椭圆上各个点的坐标，即生成椭圆的过程。
下面将详细介绍椭圆的生成算法原理。
椭圆的生成算法主要有两种，一种是解析生成算法，另一种是数值生成算法。
1. 解析生成算法：解析生成算法是通过椭圆的几何性质以及数学公式来确定椭圆上各个点的坐标。
椭圆的数学定义是平面上到两个定点F1和F2的距离之和恒定的点的集合，这个距离之和被称为椭圆的焦距。
椭圆的生成算法可以通过以下步骤来实现：（1）确定椭圆的中心点坐标：椭圆的中心点坐标是椭圆坐标系的原点，可以通过给定的椭圆中心点位置来确定。
（2）确定椭圆的长轴和短轴长度：椭圆的长轴和短轴是确定椭圆形状的关键参数，可以通过给定的椭圆长轴长度和短轴长度来确定。
（3）确定椭圆的旋转角度：椭圆可以绕着中心点旋转一定角度，旋转角度可以通过给定的旋转角来确定。
（4）根据椭圆的数学公式确定椭圆上各个点的坐标：椭圆的数学公式为：x = a * cosθ，y = b * sinθ，其中a和b分别是椭圆的长轴和短轴长度，θ是点P在椭圆上的极角。
通过以上步骤，椭圆的生成算法能够确定椭圆上任意给定角度的点的坐标。
2. 数值生成算法：数值生成算法是通过数值计算的方法来确定椭圆上各个点的坐标。
常用的数值生成算法有Bresenham算法和中点画圆法。
（1）Bresenham算法：Bresenham算法是一种通过离散化的方法来绘制椭圆的生成算法。
该算法通过遍历椭圆的象限来确定椭圆上各个点的坐标，并在每个象限内使用Bresenham画线算法来绘制曲线。
（2）中点画圆法：中点画圆法是一种通过迭代计算的方法来绘制椭圆的生成算法。
该算法通过以椭圆的中心点为起点，按照逆时针方向遍历椭圆的一个象限，根据一个决策参数来确定椭圆上各个点的坐标。
这两种数值生成算法能够准确地绘制椭圆，适用于计算机图形学等领域。
椭圆曲线密码算法（ECC）是一种非对称加密算法，它通过椭圆曲线上的点来实现密钥的生成与交换。
ECC的安全性与RSA等传统非对称加密算法相当，但它所需的密钥长度较短，使得它在移动设备等资源受限环境下具有明显的优势。
而椭圆曲线密钥生成算法就是ECC中用来生成密钥对的重要算法之一。
椭圆曲线密码算法的安全性建立在椭圆曲线离散对数问题的困难性上。
也就是说，在已知一个点P和整数kP的情况下，要很难计算出整数k。
这一性质使得椭圆曲线密码算法成为一种非常有前景的加密算法，因为相较于RSA等算法，可以用更短的密钥长度实现同等级的安全性。
椭圆曲线密钥生成算法的过程可以分为如下几个步骤：1. 选择椭圆曲线参数首先需要选择一个合适的椭圆曲线来作为公开参数。
这个椭圆曲线的选择直接影响到了密钥对的生成过程以及算法的安全性。
一般来说，椭圆曲线的安全性和性能是一对矛盾体，需要在其中寻找一个平衡点。
2. 生成私钥选择一个随机数作为私钥，私钥的大小通常是根据椭圆曲线的位数来确定的。
在ECC中，私钥通常是一个整数，它是生成公钥的重要参数。
3. 计算公钥利用椭圆曲线参数和私钥，可以通过一系列计算得到对应的公钥。
公钥通常是一个椭圆曲线上的点，它将被用于加密和数字签名等操作中。
4. 密钥对生成完成私钥和公钥组成了一个完整的密钥对，可以用于加密通信和身份认证等操作。
椭圆曲线密钥生成算法的实现涉及到大量数论和代数运算，其中包括模运算、点乘、椭圆曲线点加等复杂运算。
如何高效地实现这些运算对于算法的性能和安全性都有很大的影响。
椭圆曲线密钥生成算法是一种重要的非对称加密算法，它在移动设备、物联网设备等资源受限环境下具有明显的优势。
加之它在相同安全级别下所需的密钥长度较短，因此在当前信息安全领域有着广泛的应用前景。
椭圆曲线密钥生成算法（ECC）是当今信息安全领域中备受瞩目的一种加密算法。
其独特的数学原理和高效的计算性能使得它成为了许多安全通信协议和应用中不可或缺的一部分。
椭圆蝴蝶定理过定点斜率之比-概述说明以及解释1.引言1.1 概述概述椭圆蝴蝶定理是一种重要的数学定理，它研究了椭圆曲线上的点与过该点的切线之间的关系。
具体来说，该定理指出：过椭圆任意一点的切线斜率的平方与过该点的切线所形成的直线与椭圆的切线斜率的平方之比保持不变。
在本文中，我们将探讨这一定理并进一步研究其特殊情况——过定点斜率之比。
我们将通过介绍椭圆蝴蝶定理的基本原理和证明过程来解释这一定理的数学基础。
同时，我们还将介绍过定点斜率之比的定义和性质，并通过具体的示例来说明其应用。
通过研究椭圆蝴蝶定理过定点斜率之比，我们可以更深入地理解椭圆曲线的特性和几何性质。
这不仅对数学理论具有重要意义，而且在实际应用中也有着广泛的应用。
例如，在密码学中，椭圆曲线密码学利用了椭圆曲线上的点操作进行加密和解密，而椭圆蝴蝶定理可以帮助我们更好地理解椭圆曲线加密算法的安全性。
通过本文的阅读，读者可以对椭圆蝴蝶定理过定点斜率之比有一个较为全面的了解，并进一步探索其研究意义和应用领域。
在开始正文之前，我们将首先介绍文章的结构以及我们的研究目的，以帮助读者更好地理解和阅读后续内容。
1.2 文章结构文章结构部分的内容可以按照以下方式来编写：本文将分为引言、正文和结论三个部分，以探讨椭圆蝴蝶定理过定点斜率之比的相关内容。
在引言部分，我们将对整篇文章进行一个简要的概述，介绍研究的背景和目的。
首先，我们将概述椭圆蝴蝶定理及其在数学中的重要性。
接着，我们将说明本文的结构和组织方式，让读者能够清晰地了解本文的内容安排。
最后，我们将明确本文的目的，即探讨通过椭圆蝴蝶定理求解过定点斜率之比，并进一步说明此研究的意义和应用。
正文部分将详细介绍椭圆蝴蝶定理和过定点斜率之比的相关理论。
首先，我们将介绍椭圆蝴蝶定理的定义和基本性质。
通过数学推导和几何解释，我们将阐述椭圆蝴蝶定理的重要意义，并提供实例来帮助读者更好地理解该定理的应用。
接着，我们将探讨过定点斜率之比的求解方法。
计算机图形学课程设计题目名称: 椭圆生成算法的研究2012 年 1 月椭圆生成算法的研究摘要作为计算机图形学中基本几何元素之一的椭圆，其生成算法在几乎所有计算机图形学相关领域都要用到，尤其在计算机辅助设计中经常涉及。
因此，研究椭圆生成对计算机图形系统十分重要。
目前，已有大量的文献讨论了如何高效生成误差小的椭圆。
文献一中方法之一在扫描转换的同时复制椭圆宽度数个像素，这种方法比较简单，但造成椭圆切线斜率接近-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=+by 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 的中间点)21,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+21）在椭圆的内还是外，选择下一个扫描点。
如果中点在内，则下一个点p 1′为（x ，y +1）否则为（x -1，y +1）。
以上简单介绍了椭圆中点扫描生成算法，接下来基于中点扫描算法来生成宽椭圆。
宽椭圆生成算法思路：先以中点圆算法[1]生一个圆心在原点直径为w 的圆，填充该圆，然后以椭圆扫描转换算法[1]求得椭圆12222=+by a x 上的点，将填充的圆平移到扫描转换得到的各点处（如图1）。
图1 生成椭圆第一象限1.2 算法实现过程如图2，椭圆扫描转化得到的相邻点P 0(x 0，y 0)、P 1(x 1，y 1)，它们对应的圆形填充区为U 1、U 0，填充圆于造成中间大量的像素U 1U2重复绘制，算法复杂性较高，实际上只须绘制U 1-U 2，即图中黑色的部分，这些点全在圆边上，为“半圆弧”，这个半圆弧相对扫描点P 1 的位置以及它的形状取决于扫描推进的方向，也就是P 1 与P 0的位置关系。
图1 所示，根据椭圆扫描转换分4种来考虑它们的位置（θ为圆心角）：（1） 扫描第一区间(切线斜率r >-1)，p 1 取S 1，X 1=X+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 qq ,,,210平移(j i y x 11,) ,()y x 11,为p 1 的坐标；4） 判断是不是最后一个点，不是的话，取下一个点；回到2）；是则圆弧绘完。
图2 中点扫描向右推进时相邻两次填充区的关系（2） 扫描第一区间（切线斜率r >-1），p 1取s 2，X 1=X 0+1 ，101-=yy ，如图3 所示。
图3 中点扫描斜下推进时相邻两次填充区的关系U U 01-为图中黑色半圆弧⎪⎭⎫ ⎝⎛≤≤-443πθπ，图中类似p 点的凹点要绘制，绘制右下半圆弧的算法：1） 从最左的一个点开始， 取1/8 圆⎪⎭⎫ ⎝⎛≤≤24πθπ上的一个点q ；2） 由对称性，计算q 对应在1/2 圆⎪⎭⎫ ⎝⎛≤≤-443πθπ的3 个对称点q q q q ,,,210；3） 将q q qq ,,,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 中点扫描向下推进时相邻两次填充区的关系UU 01-为图中黑色半圆弧(−π≤θ ≤ 0)，绘制下半圆弧的算法：1） 从最左的一个点开始，取1/8 圆⎪⎭⎫ ⎝⎛≤≤24πθπ上的一个点q ；2） 由对称性，计算q 对应在1/2 圆(−π≤θ ≤ 0)的3 个对称点q q q q ,,,210；3） 将q q qq ,,,210平移(j i y x 11,) ,()y x 11,为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=+by a x ，即F( x , y )=0222222=-+ba y axba, b 为x 轴方向和y 轴方向的两个半轴, 且a, b 均为正整数, 任意位置的椭圆可通过图形的复合变换得到。
由于椭圆的四分对称性, 只需考虑第一象限1/4 椭圆的生成, 其它象限的像素点可由图形的对称变换得到。
对隐函数F( x , y ) 求导可得dXdY = 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 的值, 下半部分满足|dXdY | ≥1 即y x a b 22≥, y 的变化量大于x 的变化量, 由y 从点( a, 0) 开始递增步长来确定x 的值.由于这两部分是相互独立的, 可用两个处理器( 或线程) 并行处理, 而不用考虑同步问题, 从而能最大化的提高并行效率.2.2 两部分的算法描述对划分后的两个独立弧段, 可以借用Bresenham 算法思想从一个已知点开始根据构造的判别递推公式逐点生成, 这个过程可利用两个处理器( 或线程) 并行执行.对于上半部分, 假设已知点为()y x ii, 则下一点()y x i i 11,++ 在其右方()y x ii,1+ 点或右下方()1,1-+y x ii 点中选择离椭圆弧最近的点, 而| F ()y x ii,1+ | 为右方点到椭圆弧的距离, | F ()1,1-+y x ii| 为右下方点到椭圆弧的距离, 通过做差: d i = | F ()y x ii,1+ | - | F ()1,1-+y x ii| =| F ()y x ii,1+ | + | F ()1,1-+y x ii|可判断出所要选择的点, 即: d i < 0 选择右方的点, d i ≥0 选择右下方的点. 根据所得到的()yxi i 11,++ 利用上述思想推下一点即可得到di+ 1 与di 的递推关系式:d i 1+=d i +4,2212a yai ++d i < 0且d i 1+=d i +4xba ya i i 1221242++-+，d i ≥0该算法在VS . NET2005 平台下编译通过, 根据笔者的思路该算法可以利用任何并行编程环境如PVM 或MPI 在并行机或集群网络上实现.3 一个椭圆生成算法计算机图形学中, 关于椭圆的生成算法较多, 如中点椭圆生成算法[1], 高效的整数型椭圆生成算法[2], 基于Bresenham 算法的画椭圆算法[3], 椭圆的高质量、快速生成算法[4]等, 这些算法的主体思想均是以递推方式每次生成椭圆上一个点的坐标, 再调用画点函数在显示器上点亮一个像素。
