中点画圆算法----计算机图形学

圆的对称特性：

一个八分圆上的点可以映射为其余七个八分圆的点

这里写图片描述

利用圆的对称性可以减少计算量，只需要计算出一个八分之一圆上需要画的点，就可以映射出整个圆

中点画圆算法：

（对于原点为(xc,yc)的圆，假定圆心在坐标原点(0,0)的像素位置，把计算出每个圆上像素点(x,y)加到屏幕位置上，即(xc+x,yc+y) ）

现在来具体研究如何从点（0，R）到（ $R/\sqrt{2}$ , $R/\sqrt{2}$ ）顺时针地确定最佳逼近于该圆弧的像素序列。

假定横坐标为 xp 的像素中与该圆弧最近者已确定为 P=(xp,yp) ，那么，下一个像素只能是正右方的 E（xp+1,yp）或右下方的 SE（xp+1,yp-1）两者之一，如下图所示。

首先构造函数： $F(x,y)=x^{2}+y^{2}-R^{2}$

显然对于圆上的点，F（x, y）= 0；对于圆外的点，F（x, y）> 0 ; 对于圆内的点，F（x, y）< 0 .

假设 M 是 E 和 SE 的中点，即 M = （xp+1 , yp-0.5）. 那么，当 F（M）< 0 时， M 在圆内，说明 E 距离圆弧更近，应取 E 作为下一个像素；当 F（M）> 0 时，应取 SE 作为下一个像素。当 F（M）= 0 时，随便取 E 或 SE 。

构造判别式：

Di = F（M） = F（xp+1, yp-0.5） = $(x_{p}+1)^{2} + (y_{p} - 0.5)^{2} - R^{2}$

若 Di < 0 , 则应取 E 为下一个像素

D(i+1) = F（Mse） = F（xp+2, yp-1.5）= $(x_{p}+2)^{2} + (y_{p} - 1.5)^{2} - R^{2}$

= Di + 2*xp + 3

若 Di > 0 , 则应取 SE 为下一个像素

D(i+1) = F（Me） = F（xp+2, yp-0.5）= $(x_{p}+2)^{2} + (y_{p} - 0.5)^{2} - R^{2}$

= Di + (2*xp + 3) + (-2*yp + 2)

= Di + 2*(xp - yp) + 5

起始位置(0,R)处初始决策参数 D0 为：

D0 = F（0+1 , R-0.5）= 1.25 - R

注意：上述方法仅限于（0，R）到（ $R/\sqrt{2}$ , $R/\sqrt{2}$ ）区间，因为此区间圆弧切线斜率小于1。

如图，当点处于（ $R/\sqrt{2}$ , $R/\sqrt{2}$ ）到（R，0）区间时，假如当前选定点为图中绿色点，则下一点应在点 A与点 B中进行选择，而不是点 A上方灰色点。这时，应由（R，0）开始，将 y 轴坐标递增 1 进行计算。

核心代码：

(具体实现时，考虑到浮点运算耗内存，使用 E = Di - 0.5 代替 Di , 则初始化运算 D0 = 1.25 - R 对应于 E = 1-R。判别式 Di < 0 对应于 E < 0 （由于E 始终是整数，所以 E < -0.25 等价于 E < 0）

from PySide2.QtCore import *
class Circle:def __init__(self, p, r):self.p = pself.r = rdef points_list_circle(self):points = []if self.r < 1:return pointse = 1 - self.rx = 0y = self.rps0 = []ps1 = []ps2 = []ps3 = []ps4 = []ps5 = []ps6 = []ps7 = []while x <= y:#print("x:"+str(x)+" y:"+str(y))ps0.append(QPoint(x, y))ps1.append(QPoint(y, x))ps2.append(QPoint(-y, x))ps3.append(QPoint(-x, y))ps4.append(QPoint(y, -x))ps5.append(QPoint(x, -y))ps6.append(QPoint(-x, -y))ps7.append(QPoint(-y, -x))if e <= 0:e = e + 2*x + 3else:e = e + 2*x - 2*y + 5y -= 1x += 1for p1 in ps0:p1.setX(p1.x()+self.p.x())p1.setY(p1.y()+self.p.y())points.append(p1)for p1 in ps1:p1.setX(p1.x() + self.p.x())p1.setY(p1.y() + self.p.y())points.append(p1)for p1 in ps2:p1.setX(p1.x() + self.p.x())p1.setY(p1.y() + self.p.y())points.append(p1)for p1 in ps3:p1.setX(p1.x() + self.p.x())p1.setY(p1.y() + self.p.y())points.append(p1)for p1 in ps4:p1.setX(p1.x() + self.p.x())p1.setY(p1.y() + self.p.y())points.append(p1)for p1 in ps5:p1.setX(p1.x() + self.p.x())p1.setY(p1.y() + self.p.y())points.append(p1)for p1 in ps6:p1.setX(p1.x() + self.p.x())p1.setY(p1.y() + self.p.y())points.append(p1)for p1 in ps7:p1.setX(p1.x() + self.p.x())p1.setY(p1.y() + self.p.y())points.append(p1)return points