曲线算法

圆的生成算法

我们将圆定义为所有距中心位置 $x_c,y_c$ 为给定值 $r$ 的点集，对于任意的圆点 $x,y$ ,这个距离关系可以使用笛卡尔坐标系中的勾股定理来定义

$x - x_c^2 + y - y_c^2 = r^2$

利用上式，我们可以沿 x 轴从 $x_cx -r$ 到 $x_c + r$ 为单位步长计算对应的 y 值，从而得到每个圆周上的点位置

$y = y_c \pm \sqrt{r^2 - x_c - x^2}$

但是这不是生成圆的最好方法，这个方法的每一个问题就是每一步包含很大的计算量

或者我们可以使用极坐标的方式如下图来计算圆周的点，可以得到方程组

$\begin{cases}x = x_c + r cos \theta \\y = y_c + r sin \theta\end{cases}$

使用上述方法可以以固定角度为步长生成显示结果时，就可以利用沿圆周的等距点来绘制圆，但是三角函数的计算是十分耗时的

具体实现细节请参考计算机图形学及实用编程技术下圆的生成算法_中点画圆算法

椭圆是经过修改的圆，他的半径从一个方向的最大值变为其非正交方向的最小值，椭圆内部这两个正交方向的直线线段称为椭圆的长轴和短轴

通过椭圆上任意一点到称为椭圆焦点的两个定点的距离可以给出椭圆的精确定义: 椭圆上任意一点到这两个定点的距离之和都等于与一个常数

$\frac{x - x_c}{r_x}^2 + \frac{y - y_c}{r_y}^2 = 1$

或者利用极坐标 r 和 $\theta$ 使用参数方程来描述

$\begin{cases}x = x_c + r_x \cos \theta \\y = y_c + r_y \sin \theta\end{cases}$

具体实现细节请参考计算机图形学及实用编程技术下椭圆的生成算法_中点椭圆算法

常见的曲线包括圆锥曲线、三角和指数函数、概率分布、通用多项式和样条函数
显示一指定的曲线函数的简单方法是使用直线段来逼近，也可以按照曲线的斜率来选择自增方向

通常我们可以使用二次方程来描述圆锥曲线

$Ax^2 + By^2 + Cxy + Dx + Ey + F = 0$

通过对判别式 $B^2 - 4AC$ 的值来决定要生成的特定曲线

$B^2 - 4AC = < 0 \text{生成椭圆或者圆} \\B^2 - 4AC = 0 \text{生成抛物线} \\B^2 - 4AC = > 0 \text{生成双曲线}$

曲线拟合是在每对指定点之间构造一三次多项式曲线段，每个曲线段可以通过参数形式藐视为

$\begin{cases}x = ax_0 + ax_1u + ax_2u^2 + ax_3u^3 \\x = ay_0 + ay_1u + ay_2u^2 + ay_3u^3\end{cases}$
其中参数u在0和1之间变换，参数方程中的u的系数值根据曲线段的边界条件确定。

我们可以采用顺序算法将曲线按曲线分段分配给处理器，也可以使用其他方法来分配