学号：171860635 姓名：陈振宇
- 使用java语言和swing/awt框架，搭建了图形化界面；
- 完全完成了命令解析模块，完成了基本的错误报告机制；
- 为后续可能添加的鼠标操作功能做了准备；
- 完成了DDA直线绘制算法和Bersenham直线绘制算法，在此之上完成了对应的两种多边形绘制算法；
- 完成了图形平移功能，若当前画布上的所有图形都使用已经完成的算法，则可以完成平移操作；
- 完成了对于
<Integer,Shape>键值对的保存功能，用于实现平移/旋转/缩放时的重绘。
目前的代码调用可以分为3个层次：Main->MyMouseListener->MyGraphics，“->”代表调用。其中，Main类中包含了main函数和层次调用信息，MyMouseListener继承了MouseListener，主要包含的功能是命令解析和鼠标操作解析。MyGraphics中包含了主界面中的JFrame，JPanel和对应JPanel的Graphics，主要完成了绘图逻辑。从下面这段main函数中的代码可以看出层次调用关系，其中g为p.getGraphics()，p为JPanel，f为JFrame；
MyGraphics mg=new MyGraphics();
mg.init(g,p,f);
MyMouseListener mml=new MyMouseListener();
mml.init(mg);
p.addMouseListener(mml);考虑到画板大小不会超过1000x1000，主界面的分辨率被设置为1280x1024，且不可更改。
命令解析模块完成的功能很容易理解，鉴于所需要实现的命令不多且后续不会更改，在这里没有使用表驱动而是使用了普通的if{}else{}进行解析。命令解析模块每次将文件中的一行读入String中，再将这个String通过split()分解为String[] token。
BufferedReader in=new BufferedReader(new FileReader(path));
String str;
while((str=in.readLine())!=null)
{
commands.add(str);
}String[] token=commands.get(i).split(" ");为了防止读取过程中代码的错误和自己完成的测试用例中产生的错误，在命令解析模块中实现了简单的报错机制。这个报错机制主要处理token中的数量错误，在词组数量不正确时打印错误信息和命令文件中产生错误的行号，同时抛出一个Exception。
private void printError(String[] token,int len,int line)
{
try {
if (token.length != len) {
System.out.println("Error @ MyMouseListener @ resolveCommands: invalid command @ line " + String.valueOf(line + 1) + ".\n");
throw (new Exception());
}
} catch (Exception e)
{
e.printStackTrace();
}
}算法部分在MyGraphics模块中完成。考虑到现有的框架不提供对于像素的操作，但是BufferedImage提供对于像素的操作，同时Graphics类中提供了显示BufferedImage的简洁接口，ImageIO类中提供了保存BufferedImage为各种格式的接口，所以采用的思路是在BufferedImage中绘制需要的图片，在需要时与JPanel同步，同时保存时仅涉及对于BufferedImage的保存。
public void save(String name)
{
print("save");
//保存为bmp格式
try{
ImageIO.write(img,"bmp",new File(name+".bmp"));
}
catch (Exception e)
{
e.printStackTrace();
}
}private void panelSync() {originalGraphics.drawImage(img,0,0,null);}private void drawPixel(int x,int y)
{
int rgb_int=originalGraphics.getColor().getRGB();
img.setRGB(x,y,rgb_int);
//panelSync();//效率太低。
}项目中同时还包括了图形的保存功能。初步考虑，想要保存图形有两种方式：第一种方式是基类+派生类；第二种方式是基类+动态数组。这里采用了第二种方式。Shape类中保存了各个图形的类型，颜色，ID，使用的算法信息。在需要的时候调用相应的函数进行保存。
public int id;
public int type;
public Point[] location;
public Color color;
public String algorithm;其中Point类中保存两个int。
DDA直线算法相比Bresenham直线算法较为简单。对于特殊情况的直线，如垂直于x轴或y轴的直线，要单独做特殊处理。对于其他所有情况下的直线，考虑直线的斜截式：
先考虑$|k|<1$的情况。在这种情况下，以$x$作为算法的循环体。直线的斜率可以用另一种形式表达：
$$ k=\frac{\Delta y}{\Delta x} $$
在$\Delta x=1$的情况下，也就是一般化DDA算法中循环体的步长，$\Delta y=k$，所以在每次循环中要将$y$（作为一个double变量）加上$k$。同理，在$|k| \geq 1$的情况下，以$y$作为循环体，每次循环中$x$（作为一个double变量）加上$\frac{1}{k}$即可。每次取点时，利用Math.round()操作，将$x$或者$y$四舍五入取整即可完成画点操作。
Bresenham算法相较而言更为复杂。除去两种特殊情况之外，算法整体分为8种情况，最终可以归类为2种情况，方便代码完成。两种特殊情况同DDA直线算法中的特殊情况，分别是直线垂直于x轴和直线垂直于y轴，这两种情况都很好完成。
下面给出一种泛用式Bresenham算法的推导过程，只需要考虑两种情况即可。先考虑第一种情况，直线的斜率绝对值在$(0,1]$中。
设需要画线的两个点分别是$(x_b,y_b)$和$(x_b,y_b)$。其中b和e分别代表着begin和end。设通过算法画出的第i个点为$(x_i,y_i)$，其中$i$从$0$开始计数。
定义$\Delta x=x_e-x_b$，$\Delta y=y_e-y_b$。定义$x_s$和$y_s$，对应代码中的sx和sy，代表x和y的步长，取值为1或-1。当$x_e>x_b$时，$x_s=1$，否则为$-1$。$y_s$同理。
设决策参数为$T$，$T$的定义将会在之后完成。定义所需要解决的问题$A$：已知$(x_i,y_i)=(x_t,y_t)$，以及$T_i$，其中$T_i$是用来决策第$i+1$个点的决策参数。现在要求根据Bresenham直线算法求$(x_{i+1},y_{i+1})$和$T_{i+1}$。
决策参数应该如何规定？假设现在我们要在两个整数点之间做决策，两个整数点的$y$坐标分别是$y_{bias}$和$y_{same}$，定义$d_1=y_{bias}-y$，$d_2=y-y_{same}$，其中$y$为在这个横坐标处真正的$y$值。一个简单易懂的定义是$T=|\Delta x|(|d_2|-|d_1|)$，这样当$T>0$时，显然要选择$d_1$对应的点，也就是$y_{bias}$。当$T\leq 0$时，选择另一个点。这是对本程序中采用算法的决策参数的一个直观的理解。
下面给出$T$的严格定义：$T_{i+1}$为算法中预测$(x_{i+2},y_{i+2})$的决策参数。$T_{i+1}=|\Delta x|(|d_2|-|d_1|)$，其中$d_1=y_{bias}-y_{real}$，$d_2=y_{real}-y_{same}$，$y_{bias}=y_{i+1}+y_s$，$y_{same}=y_{i+1}$，$y_{real}=k(x_{i+1}+x_s)+b$。
对于剩下一种情况，将上述公式中所有的$x$和$y$互相替换即可。
- 这次提交的重心在于图形化界面方向，预计下次提交完成所有算法；
- 基本完成了鼠标交互的图形化界面，并按照要求与之前的命令行交互程序做了区分。现在整个项目中同时存在两个
main函数，分别表示命令行交互（main）和图形界面交互（main_GUI）; - 算法方面，完成了椭圆的绘制算法；
- 对于图形化界面，完成了：
- 图片读取功能，目前仅支持png格式，但是得益于java强大的框架，想要支持其他格式只需要添加几行代码；
- 铅笔功能，实现这功能需要一些小技巧；
- 拖动绘制直线功能。类似于windows画图，不是在松开鼠标按键的时候绘制而是在拖动鼠标的时候实时地执行擦除-绘制操作，剩下的功能也都可以进行相同的操作；
- 拖动绘制矩形功能，相当于是拖动直线绘制功能的封装；
- 拖动绘制椭圆功能，调用椭圆绘制算法；
- 橡皮擦功能，提供一个固定大小的正方形作为画板的橡皮擦；
- 颜色更改功能，随意设置所需的颜色。目前只有黑白和RGB纯色可选，后续将添加选取任意颜色的方法，输入RGB值或在RGB色图上选取点即可选取新的颜色；
- 动态调整画板大小功能，与10月份提交的版本不同，现在画板大小可以任意调整，且在调整时不会发生画板被清零的情况，但是由于拖动从画板上消失的像素点不会重新出现；
- 鼠标拖动的边界控制功能，使得鼠标无论怎么拖动画板上的图形都不会出界。
- 考虑到项目需要同时接收鼠标按下操作，抬起操作，与拖动操作，所以
MyMouseListener类同时继承了MouseMotionListener和MouseListener的接口；
public class MyMouseListener implements MouseMotionListener,MouseListener- 使用了一个新的类
LayoutInitializer用于处理按钮与逻辑的绑定。按钮的生成在画布显示之前，而鼠标侦听器的生成在画布显示之后，所以按钮的绑定在画布的生成之后。这个顺序是唯一需要注意的点； - 使用了java自带的
JFileChooser生成窗口进行文件选择。使用这个窗口有利于跨平台。
JFileChooser jf=new JFileChooser();
jf.setFileSelectionMode(JFileChooser.FILES_ONLY);
jf.setMultiSelectionEnabled(false);
jf.showOpenDialog(mml.mg.frame);
File f=jf.getSelectedFile();- 对于铅笔的操作，直接在拖动侦测中画一个点是不行的，因为主循环的速度肯定要慢于鼠标移动一个像素的速度。解决方法就是在拖动侦测中绘制上一次记录的点A和鼠标所在点之间的直线，并把鼠标所在点赋给A；
@Override
public void mouseDragged(MouseEvent mouseEvent){
//省略
else if (penMode == MODE_PENCIL)
{
mg.drawPixelWrapper(mouseEvent.getX(),mouseEvent.getY());
mg.drawPixelWrapper(x_begin,y_begin);
mg.drawLineDDA(MyGraphics.ELEMENT,x_begin,y_begin,mouseEvent.getX(),mouseEvent.getY());
x_begin=mouseEvent.getX();
y_begin=mouseEvent.getY();
}
//省略
} - 如何实现在鼠标拖动过程中动态实现擦除-绘制功能是一个难点。在11月的提交中暂且采用最笨的方法，在按下鼠标的时候保存现在的图片，在拖动时将保存的图片写入画板并重新绘制新的图元。
if (penMode == MODE_LINE) {
mg.setImage(backGround);
mg.drawLineBresenham(MyGraphics.ELEMENT, x_begin, y_begin, mouseEvent.getX(), mouseEvent.getY());
//已经同步
}本次完成了椭圆绘制算法。剩下的所有算法将会在下一次更新中实现，届时可以进行测试。
考虑一个中心点在原点的椭圆。将椭圆的标准方程化为一个参数方程：
现在考虑以x为循环元的情况。
令决策参数为p。考虑已经选取点$(x_0,y_0)$，现有两个候选点$(x_0+1,y_0)$和$(x_0+1,y_0-1)$。这两个候选点的中点若在椭圆外部，则选取更接近椭圆外部的点$(x_0+1,y_0)$，否则选择$(x_0+1,y_0-1)$。所以选取$p=f(x_0+1,y_0-\frac{1}{2})$。当$p>0$时，中点更靠近椭圆外侧，所以选取候选点$(x_0+1,y_0)$，否则选取候选点$(x_0+1,y_0-1)$。
考虑算法中的情况。当绘制某个点$(x_0,y_0)$时，$p=f(x_0+1,y_0-\frac{1}{2})$，因为在上一轮循环中，当前的点已经被确定，同时用于处理下一个点的$p$也已经被计算得出。所以先根据$p$选择一个点。当选择外侧的点时：
现考虑以y为循环元的情况。首先要确定一个新的$p$。新的$p$通过第一阶段最后的点得出，代入原公式$p=f(x_0+1,y_0-\frac{1}{2})$即可。
同理，考虑算法中的情况。当绘制点$(x_0,y_0)$时，$p=f(x_0+\frac{1}{2},y_0-1)$。当$p>0$时，选取更接近外侧的点$(x_0+1.y_0-1)$，否则选取更靠近内侧的点$(x_0,y_0-1)$。
当需要选取$(x_0+1,y_0-1)$时：
相比于直线，椭圆的算法反而更加简单一些，因为椭圆的算法只需要考虑一种情况，甚至对于$r_x>r_y$情况和$r_x<r_y$的情况是相同的。直线的算法反而要考虑8种情况及它们的合并化简。
- 完成了所有所需的算法，并进行了一定的测试；
- 优化了GUI界面，现在界面更加美观，在缩放窗口时也不会出现工具栏消失的问题；
- GUI添加了“曲线”按钮和颜色设置窗口。
添加了曲线按钮。曲线可以使用Bezier绘制，也可以使用B样条绘制。在Main_GUI.java中，令CURVE_ALGORITHM为Bezier则绘制贝塞尔曲线，否则绘制B样条曲线。
优化了布局方式。这部分主要和框架有关，在此不赘述。
完成了颜色设置功能。现在可以在文本框中输入三个RGB分量来完成颜色的设置。错误的值会被设为最接近的RGB值。文本框中的RGB分量值会与选取的颜色同步。
更详细的功能介绍请阅读说明书。
首先完成了图形“形变”相关内容：平移，缩放，旋转。这部分主要是数学上的内容，将关键点进行坐标变换即可。
对于平移，将图形的关键点加上相应的$\Delta x$和$\Delta y$即可。
对于缩放，对于每一个关键点，可以从坐标系非常直观地理解以下公式：
旋转是三个变换中最为复杂的一个。考虑一个二维旋转矩阵：
令$(x_1,y_1)$为旋转之后的点，$(x_0,y_0)$为旋转之前的点，$(x,y)$为旋转中心点。则有下面的公式： $$ \left[ \begin{matrix} x_1 \ y_1 \end{matrix} \right] = \left[ \begin{matrix} x \ y \end{matrix} \right] + \left[ \begin{matrix} cos\theta & -sin\theta \ sin\theta & cos\theta \end{matrix} \right] \left[ \begin{matrix} x_0-x \ y_0-y \end{matrix} \right] $$
经过化简之后可以得到以下的公式：
这次提交中也完成了两个线段裁剪算法：Cohen-Sutherland算法（简称CS算法）和Liang_Barsky算法（简称LB算法）。这两个算法涉及数学的部分相对较少。
CS算法的创新之处在于使用了位运算来得到线段端点的位置信息。以裁剪区域为标准，上下左右和中间分别赋予一个二进制编码来标注位置信息，要求五个编码相同位置的二进制比特不同。在大多数算法实现中，上下左右分别赋予0001,0010,0100,1000中的一个，而中间，也就是裁剪区域，赋予0000。这样，这个画布就被分为9个部分，每个部分都有各自的独特的编码。 分配编码之后要确定线段两个端点的编码信息，也就是位置信息。对于每个端点的$x$坐标，若其小于$x_{min}$，则其编码相应位置（对应左边区域的位置）置为1。若其大于$x_{max}$，则其编码相应位置（对应右边区域的位置）置为1。对于y坐标也要做相同的处理。
for(int i=0;i<=1;i++)
{
if(s.location[i].x<x_min)
code[i]|=left;
else if(s.location[i].x>x_max)
code[i]|=right;
if(s.location[i].y<y_min)
code[i]|=down;
else if(s.location[i].y>y_max)
code[i]|=up;
}现在得到了两个端点的位置编码。第一种情况，如果code[0]==0&&code[1]==0，那么表明两个端点都在裁剪区域内部，不用对线段进行任何处理；第二种情况，如果code[0]&code[1]!=0，也就是说code[0]&code[1]中存在为1的比特，存在一个裁剪区域的某个方向，使得两个端点都在相同的方向，那么线段完全在裁剪区域之外，此时要进行相应的处理。
第三种情况，也就是最广泛的情况。在以上两种情况都不成立的情况下，对于两个端点，遍历四个方向，每次遍历时将相应的端点缩减到方向边缘,也就是求解线段和相应方向边缘的交点，然后把这个交点赋给相应的端点。这是CS算法中最为耗时的一部分，需要整数和浮点数的乘除法。
for(int i=0;i<2;i++)
{
if(code[i]!=0)
{
if((code[i]&up)!=0){
s.location[i].y=y_max;
s.location[i].x=s.location[0].x+(s.location[1].x-s.location[0].x)*(y_max-s.location[0].y)/(s.location[1].y-s.location[0].y);
}
else if((code[i]&down)!=0){
s.location[i].y=y_min;
s.location[i].x=s.location[0].x+(s.location[1].x-s.location[0].x)*(y_min-s.location[0].y)/(s.location[1].y-s.location[0].y);
}
if((code[i]&right)!=0){
s.location[i].x=x_max;
s.location[i].y=s.location[0].y+(s.location[1].y-s.location[0].y)*(x_max-s.location[0].x)/(s.location[1].x-s.location[0].x);
}
else if((code[i]&left)!=0){
s.location[i].x=x_min;
s.location[i].y=s.location[0].y+(s.location[1].y-s.location[0].y)*(x_min-s.location[0].x)/(s.location[1].x-s.location[0].x);
}
}
}CS算法就此完成。可以看到，CS算法在某种程度上还是需要大量复杂的运算。
LB算法的整体思路是利用直线的参数方程，取得线段与裁剪区域的两个交点的参数u0和u1，将参数代入参数方程得到新的端点从而重绘直线。
令$(x_1,y_1)$，$(x_2,y_2)$为线段的两个端点，$\Delta x=x_2-x_1$，$\Delta y=y_2-y_1$。
则有直线的参数方程：
当$u$满足下列不等式时，相应的部分线段在裁剪区域内：
max操作。对于$u_1$，它再大也不可能大于1，但是可以比1更小，所以$u_1$的初始值取1，每次与候选值做min操作。
由$$x_{min}\leq x_1+u\Delta x \leq x_{max}$$
可以看到LB算法相比CS算法，算式更为简单。 CS算法最多需要8次浮点数乘除法，最少需要4次浮点数乘除法。而LB算法最多需要4次浮点数除法。
接下来介绍两个曲线算法的实现。
for(int i=0;i<p.length;i++){
xarray[i]=p[i].x;yarray[i]=p[i].y;}
for(double t=0;t<=1;t+=0.05/p.length) {
//步长可以调整
for(int i=1;i<p.length;i++){
for(int j=0;j<p.length-i;j++){
xarray[j]=(1-t)*xarray[j]+t*xarray[j+1];
yarray[j]=(1-t)*yarray[j]+t*yarray[j+1];
}
}
drawLineDDA_noSync(ELEMENT, (int) x, (int) y, (int) xarray[0], (int) yarray[0]);
x=xarray[0];y=yarray[0];
}需要注意的是：
- 初始化，去除原表达式中$i=0$的情况；
-
j从0遍历到p.length-i，而不是反方向。
上述算法一眼就可以看出问题。对于参数t，按照公式，应该在t每次变化时重新对xarray和yarray初始化，上述算法中并没有，而是使用了上一轮循环中留下的烂摊子。但是诡异的是在实际使用中，上述算法和正确实现的算法（见下）竟然没有太多的差别，而且速度有一定的提升。初步估计是由于步长过短，上下两次循环中的数据差距不大，迭代运算又导致了数据逐渐接近真实值导致的。
完全按照公式实现的算法如下。
for(int i=0;i<p.length;i++){
xarray[i]=p[i].x;yarray[i]=p[i].y;}
for(double t=0;t<=1;t+=0.05/p.length) {
//步长可以调整
for(int k=0;k<p.length;k++){
xarray[k]=p[k].x;yarray[k]=p[k].y;}
for(int i=1;i<p.length;i++){
for(int j=0;j<p.length-i;j++){
xarray[j]=(1-t)*xarray[j]+t*xarray[j+1];
yarray[j]=(1-t)*yarray[j]+t*yarray[j+1];
}
}
drawLineDDA_noSync(ELEMENT, (int) x, (int) y, (int) xarray[0], (int) yarray[0]);
x=xarray[0];y=yarray[0];
}B样条曲线的实现相对而言更为复杂。代码中使用了两种方式实现B样条。在Main_GUI.java中，BSPLINE_ALGORITHM为Matrix则会使用第二种方式，否则使用第一种方式。
第一种是根据定义实现B样条。
==运算几乎不会成立，所以这样做可以说是安全的，但仍然存在一定风险。
if(x==0&&y==0)
continue;//当u为整数时一定为0 排除这种情况 另一种方法来自网络，使用了矩阵运算。公式如下： $$c_i(t)= \left[ \begin{matrix} 1,t,...,t^k \end{matrix} \right] M_k \left[ \begin{matrix} d_i \ d_{i+1} \ ... \ d_{i+k} \end{matrix} \right]$$ 其中三次均匀B样条的$M_k$矩阵为： $$M_k=\frac{1}{6} \left[ \begin{matrix} 1& 4& 1& 0\ -3& 0& 3& 0\ 3& -6& 3& 0\ -1& 3& -3& 1 \end{matrix} \right] $$ 对于三次均匀B样条曲线，$k=3$。 在不知道原理的情况下，成功使用了这个方法完成了B样条曲线。