STEP BY STEP

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

如标题所示，如果该类没有父类也没有任何子类，把析构函数还定义成虚的，确实没多大必要吧。对象的构建和析构完全是一个入栈和出栈的过程，也就是说肯定会从父类构造到子类，也肯定会从子类析构到父类，这些都是毋容置疑的。

那么把析构函数定义成virtual有个什么意义了。确实没有多大意义，至少对于一个非delete造成的析构。无论是析构一个堆栈对象还是全局对象，编译器肯定能在编译时就做出决策了。但是，假如有人一时兴起，new了一个子类对象并且将地址存储在基类指针中。那么，你该怎么删除这个对象了，只能delete父类指针了。

问题就出在这里了。你既然delete父类指针，假如是在编译层次决策的话，编译器只能帮你调用父类的析构函数了。但是，事实上你是一个子类对象，那么子类的析构函数没有调用，假如你在子类的析构函数做了些什么释放，结果就是那个释放永远不会执行，这样就造成内存泄漏或者资源重复申请之类的。

其实，上面的这种写法就是利用多态的性质，既然要利用多态，肯定得把析构函数定义成virtual的，那么调用哪个析构函数的决策就能到运行时候再决定。如果基类的析构函数定义成virtual的话，其所有子类的析构函数当然也是virtual的，那么我们删除基类指针的时候，就能通过多态机制决定该调用子类的析构函数，也就是从子类的析构函数开始往基类的析构函数调用释放整个对象。这样就不会造成任何资源泄漏了。

以下的代码展示了这样的一种情况，注意Class CA作为基类，就需要把析构函数定义成virtual的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>

class CA
{
    public:
        CA(int nS = 100): nSize(nS)
        {
            nA = new int[nSize];
            printf("构造CA\n");
        }
        virtual ~CA()
        {
            delete [] nA;
            printf("析构CA\n");
        }

    private:
        int* nA;
        int nSize;
};

class CB : public CA
{
    public:
        CB(int nS = 100): nSize(nS)
        {
            nB = new int[nSize];
            printf("构造CB\n");
        }
        ~CB()
        {
            delete [] nB;
            printf("析构CB\n");
        }

    private:
        int* nB;
        int nSize;
};

int main()
{
    CA* pCA = new CB();
    delete pCA;
}

效果如图:

，

如果删掉CA析构函数前面的virtual，效果如图，

你也可以实验在主函数里面定义些栈变量的CA和CB的对象，无论构造函数是否是virtual的，都能够正确的析构。

发表于 分类于 ， 阅读次数： Valine：
本文字数： 19k 阅读时长 ≈ 17 分钟

写了下第三章部分作业和例子的代码，如下。

3.2节 sinc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <windows.h>
#include <math.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"")

const float PI = atan(1.0) * 4;
const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;

//设置世界窗口
void SetWindow(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top)
{
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(left, right, bottom, top);
}

//设置视口
void SetViewport(GLint left, GLint right, GLint bottom, GLint top)
{
    glViewport(left, bottom, right - left, top - bottom);
}

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//白色背景
    glColor3f(0.0, 0.0, 1.0);
    glLineWidth(2.0);
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);
    glMatrixMode(GL_MODELVIEW);//使视图矩形栈有效
    glLoadIdentity();

    SetViewport(0, WINDOW_WIDTH / 2, 0, WINDOW_HEIGHT);//这个函数调用在main里面一直没效果
    glBegin(GL_LINE_STRIP);
    for (float x = -4.0; x <= 4.0; x += 0.1)
    {
        if (fabs(x) < 1e-8)
        {
            glVertex2f(0.0, 1.0);
        }
        else
        {
            glVertex2f(x, sin(PI * x) / (PI* x));
        }
    }
    glEnd();

    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("The Famous Sinc Function");
    glutDisplayFunc(myDisplay);
    myInit();
    SetWindow(-5.0, 5.0, -0.3, 1.0);
    glutMainLoop();//进入消息循环

    return 0;
}

3.2节 放大显示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <windows.h>
#include <math.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"")

const float PI = atan(1.0) * 4;
int nWidth = 640;
int nHeight = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;

//设置世界窗口
void SetWindow(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top)
{
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(left, right, bottom, top);
}

//设置视口
void SetViewport(GLint left, GLint right, GLint bottom, GLint top)
{
    glViewport(left, bottom, right - left, top - bottom);
}

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//白色背景
    glColor3f(0.0, 0.0, 1.0);
    glLineWidth(2.0);
}

/////////////////////////////////////////////////////////////////
// Function: hexswirl()
// This draws a hexagon on the screen many times.  Each new
// hexagon is slightly bigger than the previous one and rotated
// slightly so that a hexagon "swirl" is drawn.
/////////////////////////////////////////////////////////////////
void hexSwirl()
{
    double angle;                       //the angle of rotation
    double angleInc = 2*3.14159265/6.0; //the angle increment
    double inc = 5.0 / 100;               //the radius increment
    double radius = 5.0 / 100.0;          //the radius to be used

    //glMatrixMode(GL_MODELVIEW);
    //glLoadIdentity();
    //clear the background

    //draw the hexagon swirl
    for (int j = 0; j <= 100; j++)
    {
        //the angle of rotation depends on which hexagon is 
        //being drawn.
        angle = j* (3.14159265/180.0);

        //draw one hexagon
        glBegin (GL_LINE_STRIP);
        for (int k=0; k <= 6; k++)
        {
            angle += angleInc;
            glVertex2d(radius * cos(angle), radius *sin(angle));

        }
        glEnd();

        //determine the radius of the next hexagon
        radius += inc;
    }

    //swap buffers for a smooth change from one
    //frame to another
    glutSwapBuffers();
    glFlush();
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);
    float cx = 0.3, cy = 0.2;
    float H, W, aspect = 0.7;

    int frame = 50;
    for (int i = 0; i < frame; ++i)
    {
        glClear(GL_COLOR_BUFFER_BIT);
        W *= 0.7;
        H = W * aspect;
        SetWindow(cx - W, cx + W, cy - H, cy + H);
        hexSwirl();
    }

    glFlush();
}

void reShape(int nNewWidth, int nNewHeight)
{
    nWidth = nNewWidth;
    nHeight = nNewHeight;
    SetViewport(0, nWidth, 0, nHeight);
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(nWidth, nHeight);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("hexSwirl");
    glutDisplayFunc(myDisplay);
    glutReshapeFunc(reShape);
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

3.2节 回旋的旋涡
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <windows.h>
#include <math.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"")

const float PI = atan(1.0) * 4;
int nWidth = 640;
int nHeight = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;
const int ROW = 8;
const int COLUMU = 6;

//设置世界窗口
void SetWindow(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top)
{
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(left, right, bottom, top);
}

//设置视口
void SetViewport(GLint left, GLint right, GLint bottom, GLint top)
{
    glViewport(left, bottom, right - left, top - bottom);
}

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//白色背景
    glColor3f(0.0, 0.0, 1.0);
    glLineWidth(2.0);
}

/////////////////////////////////////////////////////////////////
// Function: hexswirl()
// This draws a hexagon on the screen many times.  Each new
// hexagon is slightly bigger than the previous one and rotated
// slightly so that a hexagon "swirl" is drawn.
/////////////////////////////////////////////////////////////////
void hexSwirl()
{
    double angle;                       //the angle of rotation
    double angleInc = 2*3.14159265/6.0; //the angle increment
    double inc = 5.0 / 100;               //the radius increment
    double radius = 5.0 / 100.0;          //the radius to be used

    //glMatrixMode(GL_MODELVIEW);
    //glLoadIdentity();
    //clear the background

    //draw the hexagon swirl
    for (int j = 0; j <= 100; j++)
    {
        //the angle of rotation depends on which hexagon is 
        //being drawn.
        angle = j* (3.14159265/180.0);

        //draw one hexagon
        glBegin (GL_LINE_STRIP);
        for (int k=0; k <= 6; k++)
        {
            angle += angleInc;
            glVertex2d(radius * cos(angle), radius *sin(angle));

        }
        glEnd();

        //determine the radius of the next hexagon
        radius += inc;
    }
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);

    const int  L = nWidth / ROW;

    for (int i = 0; i < ROW; ++i)
    {
        for (int j = 0; j < COLUMU; ++j)
        { 
            if ((i + j) % 2 == 0)
            {
                SetWindow(-0.6, 0.6, -0.6, 0.6);
            }
            else
            {
                SetWindow(-0.6, 0.6, 0.6, -0.6);
            }
            SetViewport(i * L, L + i * L, j * L, L + j * L);
            hexSwirl();
            //for (int k = 0; k <= 200000000; k++);
        }
    }

    //swap buffers for a smooth change from one
    //frame to another
    glutSwapBuffers();
    glFlush();
}

void reShape(int nNewWidth, int nNewHeight)
{
    nWidth = nNewWidth;
    nHeight = nNewHeight;
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(nWidth, nHeight);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("hexSwirl");
    glutDisplayFunc(myDisplay);
    glutReshapeFunc(reShape);
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

3.4节 5花环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 
const int NUM = 55000;
const double PI = atan(1.0) * 4;

struct GLintPoint
{
    GLint x;
    GLint y;
}; 

class Point2
{
public:
    float x, y;
    void set(float dx, float dy) {x = dx; y = dy;}
    void set(Point2 p) {x = p.x; y = p.y;}
    Point2(float xx, float yy) {x = xx, y = yy;}
    Point2() {x = y = 0;}
};
Point2 curpos, cp;

void moveTo(Point2 p)
{
    cp.set(p);
}

void lineTo(Point2 p)
{
    glBegin(GL_LINES);
    glVertex2f(cp.x, cp.y);
    glVertex2f(p.x, p.y);
    glEnd();
    glFlush();
    cp.set(p);
}

void myInit()
{
    glClearColor(1.0, 0.0, 0.0, 0.0);
    glColor3f(0.0f, 1.0f, 0.0f);
    glPointSize(4.0);//设置点的大小为4*4像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(-WINDOW_WIDTH / 2, WINDOW_WIDTH / 2, -WINDOW_HEIGHT / 2, WINDOW_HEIGHT / 2);
}

void rosette(int N, float radius)
{
    Point2* pointlist = new Point2[N];

    GLfloat theta = (2.0 * PI) / N;
    for (int c = 0; c < N; ++c)
    {
        pointlist``` stylus.set(radius * sin(c * theta), radius * cos(theta * c));
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            moveTo(pointlist[i]);
            lineTo(pointlist[j]);
        }
    }
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏
    glViewport(10, 10, 640, 480);
    rosette(5, 200);
    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("花环");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

3.4.3 阴阳符号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <algorithm>
#include <math.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
using namespace std;
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"")

const double PI = atan(1.0) * 4;
const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;
const double BIG_R = 100;
const double MID_R = 50;
const double SML_R = 10;

void myInit()
{
    glClearColor(0.5, 0.5, 0.5, 0.0);
    glColor3f(0.0, 0.0, 1.0);
    glLineWidth(2.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);
}

void drawArc(double fX, double fY, double fR, double fBeg, double fEnd)
{
    double fAdd = 0.0001;

    fBeg = fBeg * PI / 180;
    fEnd = fEnd * PI / 180;
    if (fBeg > fEnd)
    {
        swap(fBeg, fEnd);
    }

    glBegin(GL_POLYGON);
    while (fBeg < fEnd)
    {
        glVertex2f(fX + fR * cos(fBeg), fY + fR * sin(fBeg));
        fBeg += fAdd;
    }
    glEnd();
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);

    glColor3f(0.0, 0.0, 0.0);//黑
    drawArc(WINDOW_WIDTH / 2, WINDOW_HEIGHT / 2, BIG_R, 0, 180);
    glColor3f(1.0, 1.0, 1.0);//白
    drawArc(WINDOW_WIDTH / 2, WINDOW_HEIGHT / 2, BIG_R, 180, 360);
    glColor3f(0.0, 0.0, 0.0);//黑
    drawArc(WINDOW_WIDTH / 2 - MID_R, WINDOW_HEIGHT / 2, MID_R, 0, 360);
    glColor3f(1.0, 1.0, 1.0);//白
    drawArc(WINDOW_WIDTH / 2 + MID_R, WINDOW_HEIGHT / 2, MID_R, 0, 360);
    drawArc(WINDOW_WIDTH / 2 - MID_R, WINDOW_HEIGHT / 2, SML_R, 0, 360);
    glColor3f(0.0, 0.0, 0.0);//黑
    drawArc(WINDOW_WIDTH / 2 + MID_R, WINDOW_HEIGHT / 2, SML_R, 0, 360);

    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("阴阳图");
    glutDisplayFunc(myDisplay);
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

3.4.4 Koch雪花

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <algorithm>
#include <math.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
using namespace std;
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"")

const double PI = atan(1.0) * 4;
const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;
const int DEPTH = 8;

struct GLdoublePoint
{
    GLdouble fX, fY;
};

GLdoublePoint operator + (const GLdoublePoint a, const GLdoublePoint b)
{
    GLdoublePoint c;
    c.fX = a.fX + b.fX;
    c.fY = a.fY + b.fY;
    return c;
}

GLdoublePoint operator - (const GLdoublePoint a, const GLdoublePoint b)
{
    GLdoublePoint c;
    c.fX = a.fX - b.fX;
    c.fY = a.fY - b.fY;
    return c;
}

GLdoublePoint operator * (const GLdoublePoint a, double fScale)
{
    GLdoublePoint c;
    c.fX = a.fX * fScale;
    c.fY = a.fY * fScale;
    return c;
}

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);
    glColor3f(0.0, 0.0, 0.0);
    glLineWidth(2.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);
}

void drawKoch(GLdoublePoint beg, GLdoublePoint end, int depth, bool left)
{
    if (depth == 0)
    {
        glBegin(GL_LINES);
        glVertex2f(beg.fX, beg.fY);
        glVertex2f(end.fX, end.fY);
        glEnd();
        return;
    }

    GLdoublePoint pts[3];
    GLdoublePoint vct = end - beg;
    pts[0] = beg + (vct * (1.0 / 3.0));
    pts[2] = beg + (vct * (2.0 / 3.0));
    GLdoublePoint nvct;

    if (left)
    {
        nvct.fX = -vct.fY;
        nvct.fY = vct.fX;
    }
    else
    {
        nvct.fX = vct.fY;
        nvct.fY = -vct.fX;
    }

    double fSize = sqrt(nvct.fX * nvct.fX + nvct.fY * nvct.fY);
    double fLen = (fSize / 3) * (sqrt(3) / 2);
    nvct.fX = nvct.fX / fSize * fLen;
    nvct.fY = nvct.fY / fSize * fLen;
    pts[1] = beg + (vct * 0.5);
    pts[1] = pts[1] + nvct;

    drawKoch(beg, pts[0], depth - 1, left);
    drawKoch(pts[0], pts[1], depth - 1, left);
    drawKoch(pts[1], pts[2], depth - 1, left);
    drawKoch(pts[2], end, depth - 1, left);
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);

    GLdoublePoint beg, end;
    beg.fX = WINDOW_WIDTH / 3;
    beg.fY = WINDOW_HEIGHT / 3 * 2;
    end.fX = (WINDOW_WIDTH / 3) * 2;
    end.fY = WINDOW_HEIGHT / 3 * 2;
    drawKoch(beg, end, DEPTH, true);

    beg.fX = WINDOW_WIDTH / 3;
    beg.fY = WINDOW_HEIGHT / 3 * 2;
    end.fX = WINDOW_WIDTH / 2;
    end.fY = WINDOW_HEIGHT / 3 * 2 - (WINDOW_WIDTH / 3) * (sqrt(3) / 2);
    drawKoch(beg, end, DEPTH, false);

    beg.fX = WINDOW_WIDTH / 2;
    beg.fY = WINDOW_HEIGHT / 3 * 2 - (WINDOW_WIDTH / 3) * (sqrt(3) / 2);
    end.fX = WINDOW_WIDTH / 3 * 2;
    end.fY = WINDOW_HEIGHT / 3 * 2;
    drawKoch(beg, end, DEPTH, false);

    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("Koch雪花");
    glutDisplayFunc(myDisplay);
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

3.5.3 心脏线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <math.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 
const double PI = atan(1.0) * 4;

void myInit()
{
    glClearColor(1.0, 0.0, 0.0, 0.0);
    glColor3f(0.0f, 1.0f, 0.0f);
    glPointSize(4.0);
}

void myDisplay()
{
    double fAdd = 0.01;
    double K = 0.4;
    double fX, fY, fValue;
    glClear(GL_COLOR_BUFFER_BIT);//清屏

    glBegin(GL_POINTS);
    for (float fTheta = 0.0; fTheta <= 360; fTheta += fAdd)
    {
        double fAngle = fTheta / ( 2 * PI);
        fValue = K * (1 + cos(fAngle));
        fX = fValue * cos(fAngle);
        fY = fValue * sin(fAngle);
        glVertex2f(fX, fY);
    }
    glEnd();
    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("阿基米德螺线");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

玫瑰曲线
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <math.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 
const double PI = atan(1.0) * 4;

void myInit()
{
    glClearColor(1.0, 0.0, 0.0, 0.0);
    glColor3f(0.0f, 1.0f, 0.0f);
    glPointSize(4.0);
}

void myDisplay()
{
    double fAdd = 0.01;
    double K = 1;
    double fX, fY, fValue;
    int N = 5;
    glClear(GL_COLOR_BUFFER_BIT);//清屏

    glBegin(GL_POINTS);
    for (float fTheta = 0.0; fTheta <= 360; fTheta += fAdd)
    {
        double fAngle = fTheta / ( 2 * PI);
        fValue = K * cos(N * fAngle);
        fX = fValue * cos(fAngle);
        fY = fValue * sin(fAngle);
        glVertex2f(fX, fY);
    }
    glEnd();
    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("玫瑰曲线");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

阿基米德曲线
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <math.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 
const double PI = atan(1.0) * 4;

void myInit()
{
    glClearColor(1.0, 0.0, 0.0, 0.0);
    glColor3f(0.0f, 1.0f, 0.0f);
    glPointSize(4.0);
}

void myDisplay()
{
    double fAdd = 0.01;
    double A = 0.01;
    double fX, fY, fValue;
    glClear(GL_COLOR_BUFFER_BIT);//清屏

    glBegin(GL_POINTS);
    for (float fTheta = 0.0; fTheta <= 360; fTheta += fAdd)
    {
        double fAngle = fTheta / ( 2 * PI);
        fValue = A * fAngle;
        fX = fValue * cos(fAngle);
        fY = fValue * sin(fAngle);
        glVertex2f(fX, fY);
    }
    glEnd();
    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("阿基米德螺线");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

对数螺旋线
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <math.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 
const double PI = atan(1.0) * 4;

void myInit()
{
    glClearColor(1.0, 0.0, 0.0, 0.0);
    glColor3f(0.0f, 1.0f, 0.0f);
    glPointSize(2.0);
}

void myDisplay()
{
    double fAdd = 0.01;
    double K = 0.018;
    double a = 0.07;
    double fX, fY, fValue;
    glClear(GL_COLOR_BUFFER_BIT);//清屏

    glBegin(GL_POINTS);
    for (float fTheta = 0.0; fTheta <= 360; fTheta += fAdd)
    {
        double fAngle = fTheta / ( 2 * PI);
        fValue = K * exp(a * fAngle);
        fX = fValue * cos(fAngle);
        fY = fValue * sin(fAngle);
        glVertex2f(fX, fY);
    }
    glEnd();
    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("对数螺旋线");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.5k 阅读时长 ≈ 2 分钟

先讲下OpenGL的坐标系。OpenGL的坐标系和Windows窗口默认的坐标系是不同的。WindowsGDi的默认原点在左上角，X向右递增，Y向下递增，而OpenGL的原点在窗口的左下角，X向右递增，Y向上递增。

OpenGL里面所谓的窗口就是我们创建出来的窗口，也叫做屏幕窗口，我们可以在这整个窗口里面绘图。而视口则是窗口的一个子区域，通过设置视口就可以把绘图区域限定为窗口的一个子区域，而这个子区域的别名就叫做视口。这个函数是glViewport。该函数原型为
void glViewport(GLint x,
GLint y,
GLsizei width,
GLsizei height)

第一个参数和第二个参数是左下角的坐标，第三个参数和第四个参数则分别是视口的宽度和高度。记住一点，OpenGL用的是笛卡尔坐标系，而我一直习惯了WindowsGDI的坐标系设置。

现在来讲解最关键的东西—-世界窗口（裁剪区）。

这个东西理解了，我们就可以通过一些设置做出一些漂亮的图形裁剪啊之类的，总之能达到一些很爽的效果。以计算机图形学OpenGL版3.2节的例子来说明，世界窗口即是能容纳sinc(x) = sin(PIx) / (PI x)的定义域和值域的二维矩阵。比如说，这个例子里面绘画函数的时候x的范围是[-4.0,4.0]，该函数最大值不会超过1.0，在该范围内最小值也会大于-0.3，那么我们可以设置世界窗口为[-4.0,4.0,-0.3,1.0]，四个值分别是描述了现实世界中的一个与坐标轴平行的矩形。如果把世界窗口设置为[-5.0,5.0,-0.3,1.0]，该函数的显示效果可能会更好一点，因为可以看到边界外面的部分。

现在很明显的看到，世界窗口和视口大小基本上是不一致的，那么我们要显示的图形肯定会被拉伸。这个拉伸也是很简单的按照比例尺计算出来的。可以很形象的想象下，把一个人放小显示在一个窗口里面，或者把一只蚂蚁放大显示在一个窗口里面。

附3.2节sinc源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <windows.h>
#include <math.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"")

const float PI = atan(1.0) * 4;
const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;

//设置世界窗口
void SetWindow(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top)
{
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(left, right, bottom, top);
}

//设置视口
void SetViewport(GLint left, GLint right, GLint bottom, GLint top)
{
    glViewport(left, bottom, right - left, top - bottom);
}

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//白色背景
    glColor3f(0.0, 0.0, 1.0);
    glLineWidth(2.0);
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);
    glMatrixMode(GL_MODELVIEW);//使视图矩形栈有效
    glLoadIdentity();

    SetViewport(0, WINDOW_WIDTH / 2, 0, WINDOW_HEIGHT);//这个函数调用在main里面一直没效果
    glBegin(GL_LINE_STRIP);
    for (float x = -4.0; x <= 4.0; x += 0.1)
    {
        if (fabs(x) < 1e-8)
        {
            glVertex2f(0.0, 1.0);
        }
        else
        {
            glVertex2f(x, sin(PI * x) / (PI* x));
        }
    }
    glEnd();

    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("The Famous Sinc Function");
    glutDisplayFunc(myDisplay);
    myInit();
    SetWindow(-5.0, 5.0, -0.3, 1.0);
    glutMainLoop();//进入消息循环

    return 0;
}

显示效果如图，

由于我设置了视口为左半窗口，可以明显的看到，函数曲线挤压在左边了。注意，在主函数里面设置视口一直没有效果，我也不知道为什么。

发表于 分类于 ， 阅读次数： Valine：
本文字数： 15k 阅读时长 ≈ 13 分钟

最近在用这本书学习计算机图形学，发现这本书在网上基本找不到配套的代码，找到的也是乱七八糟的，很不爽的那种，或者根本是语言初学者对着敲的。故打算把自己写的每个例子贡献出来。

散乱点图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 
const int NUM = 1000;

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(4.0);//设置点的大小为4*4像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏
    glBegin(GL_POINTS);
    for (int i = 0; i < NUM; ++i)
    {
        glVertex2i(rand() % WINDOW_WIDTH, rand() % WINDOW_HEIGHT);
    }
    glEnd();
    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("散乱点图");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    srand(time(NULL));
    glutMainLoop();//进入消息循环

    return 0;
}

Sierpinski垫片
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 
const int NUM = 55000;

struct GLintPoint
{
    GLint x;
    GLint y;
}; 
GLintPoint pts[3] = {{10, 10}, {600, 10}, {300, 600}};

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(4.0);//设置点的大小为4*4像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
}

void drawDot(GLintPoint pt)
{
    glBegin(GL_POINTS);
    glVertex2i(pt.x, pt.y);
    glEnd();
}

void sierpinskiRender()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏
    int nIndex = rand() % 3;
    GLintPoint pt = pts[nIndex];

    drawDot(pt);
    for (int i = 0; i < NUM; ++i)
    {
        nIndex = rand() % 3;
        pt.x = (pt.x + pts[nIndex].x) / 2;
        pt.y = (pt.y + pts[nIndex].y) / 2;
        drawDot(pt);
    }
    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("Sierpinski垫片");
    glutDisplayFunc(sierpinskiRender);//注册重绘回调函数
    myInit();
    srand(time(NULL));
    glutMainLoop();//进入消息循环

    return 0;
}

绘制函数曲线:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <math.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment( linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"" ) //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 
const double PI = atan(1.0) * 4.0; 
GLdouble A, B, C, D;

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(2.0);//设置点的大小为2*2像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
    A = WINDOW_WIDTH / 4.0;
    B = 0.0;
    C = D = WINDOW_HEIGHT / 2.0;
}

void myDisplay()
{
    GLdouble fAdd = 0.001;

    glClear(GL_COLOR_BUFFER_BIT);//清屏
    glBegin(GL_POINTS);
    for (GLdouble x = 0.0; x < 4.0; x += fAdd)
    {
        GLdouble fValue = exp(-x) * cos(2 * PI * x);
        glVertex2d(A * x + B, C * fValue + D);
    }
    glEnd();
    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("Dot Plot of a Function");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

画矩形:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <math.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;
const int NUM = 8;
const int BOARD_WIDTH = WINDOW_WIDTH / NUM;
const int BOARD_HEIGHT = WINDOW_HEIGHT / NUM;
const GLfloat r1 = 0.0, g1 = 0.0, b1 = 0.0;
const GLfloat r2 = 1.0, g2 = 1.0, b2 = 1.0;

struct GLintPoint
{
    GLint x;
    GLint y;
};

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(2.0);//设置点的大小为2*2像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
}

//根据中心,高和宽绘画矩形
void drawRectangleCenter(GLintPoint center, double fWidth, double fHeight)
{
    glRectf(center.x - fWidth / 2.0, center.y - fHeight / 2.0,
            center.x + fWidth / 2.0, center.y + fHeight / 2.0);
}

//根据左上角,高和宽高比绘画矩形
void drawRectangleCornersize(GLintPoint topleft, double fHeight, double fScale)
{
    glRectf(topleft.x, topleft.y, topleft.x + fHeight * fScale, topleft.y + fHeight);
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏
    GLintPoint center, topleft;

    for (int i = 0; i < NUM; ++i)
    {
        for (int j = 0; j < NUM; ++j)
        {
            if ((i + j) % 2 == 0)
            {
                glColor3f(r1, g1, b1);
                center.x = i * BOARD_WIDTH + BOARD_WIDTH / 2.0;
                center.y = j * BOARD_HEIGHT + BOARD_HEIGHT / 2.0;
                drawRectangleCenter(center, BOARD_WIDTH, BOARD_HEIGHT);
            }
            else
            {
                glColor3f(r2, g2, b2);
                topleft.x = i * BOARD_WIDTH;
                topleft.y = j * BOARD_HEIGHT;
                drawRectangleCornersize(topleft, BOARD_HEIGHT, BOARD_HEIGHT * 1.0 / BOARD_WIDTH);
            }
        }
    }
    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("画矩形");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

画棋盘:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <math.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;
const int NUM = 8;
const int BOARD_WIDTH = WINDOW_WIDTH / NUM;
const int BOARD_HEIGHT = WINDOW_HEIGHT / NUM;
const GLfloat r1 = 0.0, g1 = 0.0, b1 = 0.0;
const GLfloat r2 = 1.0, g2 = 1.0, b2 = 1.0;

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(2.0);//设置点的大小为2*2像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏
    for (int i = 0; i < NUM; ++i)
    {
        for (int j = 0; j < NUM; ++j)
        {
            if ((i + j) % 2 == 0)
            {
                glColor3f(r1, g1, b1);
            }
            else
            {
                glColor3f(r2, g2, b2);
            }
            glRecti(i * BOARD_WIDTH, j * BOARD_HEIGHT,
                    i * BOARD_WIDTH + BOARD_WIDTH, j * BOARD_HEIGHT + BOARD_HEIGHT);
        }
    }
    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("棋盘");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

根据不同长宽比画矩形:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 400;
const int WINDOW_HEIGHT = 400;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;
const int MAX = 100000;
double R = 1.7;

struct GLintPoint
{
    GLint x;
    GLint y;
};

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(2.0);//设置点的大小为2*2像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏

    double fWidth, fHeight;
    if (R > 1.0)
    {
        fWidth = WINDOW_WIDTH;
        fHeight = fWidth / R;
    }
    else
    {
        fHeight = WINDOW_HEIGHT;
        fWidth = fHeight * R;

    }
    glRectf(0.0, 0.0, fWidth, fHeight);
    R = (rand() % MAX) * 1.0 / (MAX / 10.0);

    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("不同长宽比");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    srand(time(NULL));
    glutMainLoop();//进入消息循环

    return 0;
}

鼠标和键盘:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 
const int NUM = 1000;

struct GLintPoint
{
    GLint x, y;
};
GLintPoint corner[2];
bool bSelect = false;

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(4.0);//设置点的大小为4*4像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
    glLineWidth(4.0);
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏

    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();

    if (bSelect)
    {
        glBegin(GL_QUADS);
        glVertex2i(corner[0].x, corner[0].y);
        glVertex2i(corner[0].x, corner[1].y);
        glVertex2i(corner[1].x, corner[1].y);
        glVertex2i(corner[1].x, corner[0].y);
        glEnd();
    }
    glutSwapBuffers();
}

void myMouse(int button, int state, int x, int y)
{
    if (button == GLUT_LEFT_BUTTON  state == GLUT_DOWN)
    {
        corner[0].x = x;
        corner[0].y = WINDOW_HEIGHT - y;
        bSelect = true;
    }
    glutPostRedisplay();
}

//鼠标在窗口上面移动并且没有按钮按下
void myPassiveMotion(int x, int y)
{
    corner[1].x = x;
    corner[1].y = WINDOW_HEIGHT - y;
    glutPostRedisplay();
}

void myKeyboard(unsigned char key, int mouseX, int mouseY)
{
    switch (key)
    {
    case 'P':
    case 'p':
        glBegin(GL_POINTS);
        glVertex2i(mouseX, WINDOW_HEIGHT - mouseY);
        glEnd();
        glutSwapBuffers();
        break;

    case 'Q':
    case 'q':
        exit(-1);
        break;

    default:
        break;
    }
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("Rubber Rect Demo");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    glutMouseFunc(myMouse);
    glutPassiveMotionFunc(myPassiveMotion);
    glutKeyboardFunc(myKeyboard);
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

菜单:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150; 

enum COLOR
{
    RED, GREEN, BLUE, WHITE
};
float angle = 0.0;
float red = 1.0, blue = 1.0, green = 1.0;

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);//清屏
    glLoadIdentity();

    glRotatef(angle, 0.0, 1.0, 0.0);
    glColor3f(red, green, blue);
    glBegin(GL_TRIANGLES);//下面的画点坐标为什么是这么设置的了?
    glVertex3f(-0.5, -0.5, 1.0);
    glVertex3f(0.5, 0.0, 0.0);
    glVertex3f(0.0, 0.5, 2.0);
    glEnd();
    angle++;
    glutSwapBuffers();
}

void myMenuEvents(int option)
{
    switch (option)
    {
    case RED: red = 1.0; green = blue = 0.0; break;
    case GREEN: green = 1.0; red = blue = 0.0; break;
    case BLUE: blue = 1.0; red = green = 0.0; break;
    case WHITE: red = green = blue = 1.0; break;
    }
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGBA);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("Menu Test");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    glutIdleFunc(myDisplay);
    glutCreateMenu(myMenuEvents);
    glutAddMenuEntry("Red", RED);
    glutAddMenuEntry("Blue", BLUE);
    glutAddMenuEntry("Green", GREEN);
    glutAddMenuEntry("Black", WHITE);
    glutAttachMenu(GLUT_RIGHT_BUTTON);
    glutMainLoop();//进入消息循环

    return 0;
}

姜饼人:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <math.h>
#include <stdlib.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;
const int M = 40;
const int L = 3;
const int TIMES = 1000000;

struct GLintPoint
{
    GLint x, y;
};
GLintPoint p, q;

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(2.0);//设置点的大小为2*2像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
    p.x = 121;
    p.y = 115;
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏
    glBegin(GL_POINTS);
    for (int i = 0; i < TIMES; ++i)
    {
        q.x = M * (1 + 2 * L) - p.y + abs(p.x - L * M);
        q.y = p.x;
        p = q;
        glVertex2f(p.x, p.y);
    }
    glEnd();
    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("姜饼人");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

先贴一个OpenGL程序的代码,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;
const int NUM = 1000;

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(4.0);//设置点的大小为4*4像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏
    glBegin(GL_POINTS);
    for (int i = 0; i < NUM; ++i)
    {
        glVertex2i(rand() % WINDOW_WIDTH, rand() % WINDOW_HEIGHT);
    }
    glEnd();
    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("散乱点图");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    srand(time(NULL));
    glutMainLoop();//进入消息循环

    return 0;
}

该程序只是创建一个窗口，然后在里面画一些随机的点。效果如图所示，

说实话这个程序非常简单，在主函数里面只是设置了窗口大小和位置，然后创建了个窗口，做了些初始化，并且为窗口设置了显示回调函数。初始化函数里面都有注释，显示回调函数里面只是一直在随机画点而已。

说实话，仅仅是使用最基本的opengl画图确实太简单了，也没什么多说的，如果你熟悉Windows程序设计和C++语言，只是换个库而已，真正需要学习的是计算机图形学。我觉得OpenGL相对于DirectX简洁明了很多了，所以才选择了计算机图形学OpenGL版这本书来学习图形学的。下面来简要介绍下OpenGL的库组成吧。

OpenGL库分为四个部分，GL和GLU，GLUT以及GLUI。GL和GLU都是用于绘图的，只是第一个是基本库，第二个是一些高级的绘图函数。GLUT库主要包含一些管理窗口和菜单的函数，GLUI则是一些高级的界面管理部分，比如各种复杂的按钮和菜单。

我觉得如果在VC下面建立控制台工程，然后设置链接命令去掉控制台窗口，再在main函数下执行OpenGL操作，这个过程不仅简洁而且感觉效果也不错。现在看来，OpenGL确实是一个比较美观的东西，至少相对于我用了几年的MFC来说。

发表于 分类于 阅读次数： Valine：
本文字数： 957 阅读时长 ≈ 1 分钟

本文是以OpenGL的代码为例子的。计算机图形学OpenGL版上面的例子都是控制台模式的，如果不进行设置，运行的时候会先出现黑窗口再出现Windows窗口。

其实要去除控制台窗口非常简单，只需要修改工程设置，把子系统改成Windows，程序的入口点改成mainCRTStartup。

下面我先把几中解决办法列举出来，再解释下我的理解。

方法一：在程序中加入一句#pragma comment(linker, “/subsystem:\”windows\” /entry:\”mainCRTStartup\””)，建议加在include的后面。

方法二：修改工程设置。

对于vc6，地方在Project->setting->Link->Project Options。

点开后的界面如图，

在右下角的Project Options里面找到/subsytem:,并把其后面其后面的参数改成为windows,然后再找到/entry:，把其后面的值改成”mainCRTStartup”，如果找不到就添加，最后的效果是/subsystem:windows /entry:”mainCRTStartup”。

对于vs2008，地方在项目->属性->链接器，

然后在左边选中高级，如图所示，

在最上面的入口点输入mainCRTStartup，再选中系统，如图所示，

在最上面的子系统选择Windows即可了。

为什么这样设置下就可以了了。主要是因为Windows系统下有几种子系统，一种是控制台，一种是窗口子系统，如果建立了控制台工程肯定是要创建控制台子系统程序了，建立了Windows Application和MFC之类的工程则是窗口子系统了。不同的子系统会链接不同的主函数，控制台的会链接main,窗口的会链接WinMain，如果不匹配肯定会链接失败。

现在我们使用OpenGL编程，又建立的是控制台工程，如果不进行设置肯定会出现黑窗口的，所以我们把工程的子系统改成Windows，但是我们不想改主函数为WinMain了，因为这样会很麻烦，所以我们再把程序入口改成mainCRTStartup。同样如果是win32 App工程下，我们可以把子系统改成控制台，再设置程序入口为WinMainCRTStartup，应该就会得到相反的效果了。

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1k 阅读时长 ≈ 1 分钟

首先，我们需要安装好VC6或者VS2008，然后获取OpenGL的开发包。剩下的一件麻烦事情就是配置了。

如果你找不到合适的开发包，可以从我这里下载，里面开发包和查询手册，可是我辛苦收集好的哦。地址：OpenGL SDK

在你下载好的开发包里面，会出现三个目录，分别是include和lib,system32。include里面当然是OpenGL的头文件了，那么lib则是动态链接时候的导入库了，system32里面是几个dll，dll你知道该放在哪里吧，放在你的程序同一个目录下，或者干脆放在系统目录下，即c盘下面的system32目录。开发包里面有个txt文件简要说明了如何设置include和lib，下面我要用图示详细说明vc6和vs2008下的设置方法。

vc6下的设置，
step1:
Tools->Options->directories

step2:
在Show Directories For选型卡里面选择include files
然后,在下面的directories里面添加一个新项，然后选择opengl的include目录，再用右上角的箭头上移到最上面。

step3:
在Show Directories For选型卡里面选择Library files
然后,在下面的directories里面添加一个新项，然后选择opengl的lib目录，再用右上角的箭头上移到最上面。

step4:
把opengl开发包里面的system32文件下面的dll全部拷贝的C:\WINDOWS\system32下面，当然不同的系统这个目录不同，
不过这都是系统目录。

现在你就可以用vc6下使用opengl学习图形学了。。。

vs2008下的设置,
step1:
工具->选项，打开如图所示的对话框，
点开左边的项目和解决方案，选择里面的vc++目录。

step2:
类似vc6下面的设置，在右边的显示一下内容的目录选项卡中选择包含文件，再在下面的列表框里面添加一个新的目录作为新的include目录。目录的路径设置同vc6，就是开发包的include文件夹。

step3:
类似vc6下面的设置，在右边的显示一下内容的目录选项卡中选择库文件，再在下面的列表框里面添加一个新的目录作为新的lib目录。目录的路径设置同vc6，就是开发包的lib文件夹。

step4:
同样是拷贝dll到系统目录下。

至此基本解决了，无论是哪种外部库的设置都是如果搞一下就ok了，无论是哪个版本的vs，基本上设置的地方差别不大。

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

ST算法可以说就是个二维的动态规划，黑书上有解释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

const int MAX_I = 50010;
const int MAX_J = 20;

int nMax[MAX_I][MAX_J];
int nMin[MAX_I][MAX_J];
int nArr[MAX_I];
int nN, nQ;

void InitRmq(int nN)
{
    for (int i = 1; i <= nN; ++i)
    {
        nMax[i][0] = nMin[i][0] = nArr[i];
    }

    for (int j = 1; (1 << j) <= nN; ++j)
    {
        for (int i = 1; i + (1 << j) - 1 <= nN; ++i)
        {
            nMax[i][j] = max(nMax[i][j - 1],
                             nMax[i + (1 << (j - 1))][j - 1]);
            nMin[i][j] = min(nMin[i][j - 1],
                             nMin[i + (1 << (j - 1))][j - 1]);                
        }
    }
}

int Query(int nA, int nB)
{
    int k = (int)(log(1.0 * nB - nA + 1) / log(2.0));
    int nBig = max(nMax[nA][k], nMax[nB - (1 << k) + 1][k]);
    int nSml = min(nMin[nA][k], nMin[nB - (1 << k) + 1][k]);
    return nBig - nSml;
}

int main()
{
    while (scanf("%d%d", &nN, &nQ) == 2)
    {
        for (int i = 1; i <= nN; ++i)
        {
            scanf("%d", &nArr[i]);
        }
        InitRmq(nN);
        for (int i = 0; i < nQ; ++i)
        {
            int nA, nB;
            scanf("%d%d", &nA, &nB);
            printf("%d\n", Query(nA, nB));
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

该题就是求一个字符串的最长回文子串，就是一个满足本身是回文的最长的子串。
该题貌似可以用后缀数组和扩展kmp做，但是好像后缀数组貌似会tle，改学了下一个专门的叫Manacher算法的东西。。。
这又是一个线性改良算法。找到有篇文章写的不错，链接如下：
http://www.felix021.com/blog/read.php?2040。
该算法说起来也不是太复杂，比较容易看懂的那种，当然是接触过其它字符串算法的前提下了。记得以前就看了看，硬是没看懂，想不到现在这么快就明白了。
该算法需要额外的O(N)空间。说起来是空间换时间吧。
大概的思路是先预处理字符串，使其成为一个长度一定为偶数的串。而且第一个字符是’$’，假设’$’没有在原串出现过。然后再在原来的每个字符前面加上’#’，最后再加个
‘#’。比如，abc就变成了$#a#b#c#。现在再对新的字符串进行处理。
开一个新的数组nRad[MAX]，nRad[i]表示新串中第i个位置向左边和向右边同时扩展并且保持对称的最大距离。如果求出了nRad数组后，有一个结论，nRad[i]-1恰好表示原串对应的位置能够扩展的回文子串长度。这个的证明，应该比较简单，因为新串基本上是原串的2倍了，而且新串每一个有效字符两侧都有插入的#，这个找个例子看下就知道是这样了。
最重要的是如何求出nRad数组。
求这个数组的算法也主要是利用了一些间接的结论优化了nRad[i]的初始化值。比如我们求nRad[i]的时候，如果知道了i以前的nRad值，而且知道了前面有一个位置id，能够最大的向两边扩展距离max。那么有一个结论，nRad[i] 能够初始化为min(nRad[2*id - i], max - i)，然后再进行递增。关键是如何证明这个，这个的证明，对照图片就很清楚了。
证明如下：
当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，
以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。

当 P[j] > mx - i 的时候，以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中，但是基于
对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会
扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。

这个就说明得很清楚了。。。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX = 110010 * 2;
char szIn[MAX];
char szOut[MAX];
int nRad[MAX];

int Proc(char* pszIn, char* pszOut)
{
    int nLen = 1;

    *pszOut++ = '$';
    while (*pszIn)
    {
        *pszOut++ = '#';
        nLen++;
        *pszOut++ = *pszIn++;
        nLen++;
    }
    *pszOut++ = '#';
    *pszOut = '\0';

    return nLen + 1;
}

void Manacher(int* pnRad, char* pszStr, int nN)
{
    int nId = 0, nMax = 0;

    //pnRad[0] = 1;
    for (int i = 0; i < nN; ++i) 
    { 
        if (nMax > i)
        {
            pnRad[i] = min(pnRad[2 * nId - i], nMax - i);
        }
        else pnRad[i] = 1;

        while (pszStr[i + pnRad[i]] == pszStr[i - pnRad[i]])
        {
            ++pnRad[i];
        }
        if (pnRad[i] + i > nMax)
        {
            nMax = pnRad[i] + i;
            nId = i;
        }
    }
}

int main()
{
    while (scanf("%s", szIn) == 1)
    {
        int nLen = Proc(szIn, szOut);
        Manacher(nRad, szOut, nLen);
        int nAns = 1;
        for (int i = 0; i < nLen; ++i)
        {
            nAns = max(nRad[i], nAns);
        }
        printf("%d\n", nAns - 1);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.8k 阅读时长 ≈ 3 分钟

此题就是给出N个字符串，然后求一个最长的子串，它至少出现在N/2+1个字符串中，如果有多个这样的子串，按字典序输出，如果没有这样的子串，输出?。
此题是罗穗骞论文里面的例11，他有讲述具体的解法。要用后缀数组做这样的题真不容易，用后缀数组就感觉是一件非常纠结的事情了。
这个题的解法还是那种模式化的思路。把N个字符串连接成一个，注意中间加不出现在任何一个字符串中的分隔符，然后建立sa数组和height数组等。最后二分答案，根据答案，即子串的长度对height数组进行分组，分组的思路还是罗穗骞论文里面例3的思路，即从到后枚举height数组，把连续大于等于答案的值放做一组，一旦小于答案那么就是新的分组。这个题需要找到一些分组，其中的后缀是能够出现在N个原串中，这个分组的公共前缀就是sa[i]开始的nMid个字符了(nMid是二分时候获得的子串长度)。由于这个题需要按字典序输出多个满足要求的子串，所以麻烦了点。需要在Check函数里面记录这些子串，而且输出答案的时候需要排序，再unique，由于是按height数组的顺序查找的，而sa[i]已经排好序了，所以排序答案的过程可以省略，但是必须unique。想下Check函数里面遍历height数组的过程就知道可能出现重复的子串。。。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX_N = 110;
const int MAX_L = 1010;
const int MAX = MAX_N * MAX_L;
int nAns;
char szStr[MAX_L];
char szAns[MAX][MAX_L];
char* pszAns[MAX];
int nNum[MAX];
int nLoc[MAX];
bool bVis[MAX_N];
int sa[MAX], rank[MAX], height[MAX];
int wa[MAX], wb[MAX], wv[MAX], wd[MAX];
bool CmpStr(const char* pszOne, const char* pszTwo)
{
    return strcmp(pszOne, pszTwo) < 0;
}
bool EqualStr(const char* pszOne, const char* pszTwo)
{
    return strcmp(pszOne, pszTwo) == 0;
}
int cmp(int* r, int a, int b, int l)
{
    return r[a] == r[b]  r[a + l] == r[b + l];
}
//倍增算法,r为待匹配数组,n为总长度,m为字符串范围
void da(int* r, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;

    for (i = 0; i < m; ++i) wd[i] = 0;
    for (i = 0; i < n; ++i) wd[x[i] = r[i]]++;
    for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
    for (i = n - 1; i >= 0; --i) sa[--wd[x[i]]] = i;

    for (j = 1, p = 1; p < n; j *= 2, m = p)
    {
        for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
        for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;

        for (i = 0; i < n; ++i) wv[i] = x[y[i]];
        for (i = 0; i < m; ++i) wd[i] = 0;
        for (i = 0; i < n; ++i) wd[wv[i]]++;
        for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
        for (i = n - 1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];

        swap(x, y);
        for (p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
        {
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++;
        }
    }
}
//求height数组
void calHeight(int* r, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; ++i) rank[sa[i]] = i;
    for (i = 0; i < n; height[rank[i++]] = k)
    {
        if (k) --k;
        for(j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
    }
}
bool Check(int nMid, int nN, int nK)
{
    int nCnt = 0;
    int nNo = 0;

    memset(bVis, false, sizeof(bVis));
    for (int i = 1; i <= nN; ++i)
    {
        if (height[i] < nMid)
        {
            nCnt = 0;
            memset(bVis, false, sizeof(bVis));
        }
        else
        {
            if (!bVis[nLoc[sa[i - 1]]])
            {
                ++nCnt;
                bVis[nLoc[sa[i - 1]]] = true;
            }
            if (!bVis[nLoc[sa[i]]])
            {
                ++nCnt;
                bVis[nLoc[sa[i]]] = true;
            }
            if (nCnt == nK)
            {
                for (int j = 0; j < nMid; ++j)
                {
                    szAns[nNo][j] = nNum[sa[i] + j];
                }
                szAns[nNo][nMid] = 0;
                ++nNo;
                nCnt = 0;
            }
        }
    }

    if (nNo > 0) nAns = nNo;
    return nNo > 0;
}
int main()
{
    int nN;
    bool bFirst = true;

    while (scanf("%d", &nN), nN)
    {
        if (bFirst) bFirst = false;
        else putchar('\n');

        int nEnd = 300;
        int nP = 0;
        for (int i = 0; i < nN; ++i)
        {
            scanf("%s", szStr);
            int nLen = strlen(szStr);
            for (int j = 0; j < nLen; ++j)
            {
                nNum[nP] = szStr[j];
                nLoc[nP++] = i;
            }
            nNum[nP] = nEnd;
            nLoc[nP++] = nEnd++;
        }
        nNum[nP] = 0;

        if (nN == 1)
        {
            printf("%s\n\n", szStr);
            continue;
        }
        da(nNum, nP + 1, 500);//500是估计的字符集大小
        calHeight(nNum, nP);

        int nLeft = 1, nRight = strlen(szStr);
        int nTemp = 0, nMid;
        int nK = nN / 2 + 1;
        nAns = 0;
        while (nLeft <= nRight)
        {
            nMid = (nLeft + nRight) >> 1;
            if (Check(nMid, nP, nK))
            {
                nTemp = nMid;
                nLeft = nMid + 1;
            }
            else nRight = nMid - 1;
        }
        if (nTemp == 0)
        {
            printf("?\n");
        }
        else
        {
            for (int i = 0; i < nAns; ++i)
            {
                pszAns[i] = szAns[i];
            }
            //sort(pszAns, pszAns + nAns, CmpStr);
            nAns = unique(pszAns, pszAns + nAns, EqualStr) - pszAns;
            for (int i = 0; i < nAns; ++i)
            {
                printf("%s\n", pszAns[i]);
            }
        }
    }

    return 0;
}