Koch

使用 golang 绘制一个科赫曲线（Koch）雪花。

科赫曲线 1

给定线段 AB，科赫曲线可以由以下步骤生成：

  1. 将线段分成三等份：AC，CD，DB
  2. 以 CD 为底，向外（内外随意）画一个等边三角形 DMC
  3. 将线段 CD 移除
  4. 分别对 AC，CM，MD，DB 重复 1~3。

科赫雪花是以等边三角形三边生成的科赫曲线组成的。

等边三角形

想要完成该曲线的生成首先要解决一个几何问题，如何通过两点坐标求出等边三角形第三个顶点坐标，数学有很多种解法，可是如何变成代码呢？
查到有人总结了一个万能公式2：

对于任意两个不同点 A 和 B，A 绕 B 逆时针旋转 θ 角度后 C 坐标为：
$$
  \begin{cases}
  x = |x_A-x_B| \times \cosθ - |y_A-y_B| \times \sinθ + x_B \\
  y = |y_A-y_B| \times \cosθ + |x_A-x_B| \times \sinθ + y_B
  \end{cases}
$$
而等边三角形已知 θ 角为 60 度。

具体的推导过程请移步原博文。

实现

下面是用 golang 实现的 Koch 函数，其中 line 为两点画一条直线，line_len 为计算直线的长度。

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
const (
    _KOCH_LINE_MIN_LENGTH = 15
)

func koch_point(x1, y1, x2, y2 int) []image.Point {
    var pots [5]image.Point

    pots[0].X = x1
    pots[0].Y = y1
    pots[4].X = x2
    pots[4].Y = y2

    dx := float64(x2 - x1)
    dy := float64(y2 - y1)
    pots[1].X = x1 + int(dx/3)
    pots[1].Y = y1 + int(dy/3)
    pots[3].X = x2 - int(dx/3)
    pots[3].Y = y2 - int(dy/3)

    dx = float64(pots[3].X - pots[1].X)
    dy = float64(pots[3].Y - pots[1].Y)
    pots[2].X = int(dx*0.5-dy*0.8660254) + pots[1].X
    pots[2].Y = int(dy*0.5+dx*0.8660254) + pots[1].Y

    return pots[:]
}

func koch(img *image.RGBA, x1, y1, x2, y2 int, c color.Color) {
    p := koch_point(x1, y1, x2, y2)
    next := true
    for i := 0; i < len(p)-1; i++ {
        if line_len(p[i].X, p[i].Y, p[i+1].X, p[i+1].Y) < _KOCH_LINE_MIN_LENGTH {
            next = false
        }
    }
    for i := 0; i < len(p)-1; i++ {
        if next {
            koch(img, p[i].X, p[i].Y, p[i+1].X, p[i+1].Y, c)
        } else {
            line(img, p[i].X, p[i].Y, p[i+1].X, p[i+1].Y, c)
        }
    }
}

测试

绘制一片科赫雪花。

1
2
3
4
5
6
7
8
9
10
func Test_koch(t *testing.T) {
    img := image.NewRGBA(image.Rect(0, 0, 600, 600))
    // 等边三角形
    koch(img, 250, 0, 0, 433, color.RGBA{0, 0, 0, 255})
    koch(img, 0, 433, 500, 433, color.RGBA{0, 0, 0, 255})
    koch(img, 500, 433, 250, 0, color.RGBA{0, 0, 0, 255})
    f, _ := os.OpenFile("koch.png", os.O_WRONLY|os.O_CREATE, 0600)
    defer f.Close()
    png.Encode(f, img)
}

结果：

code
#golang #draw #分形
Koch
https://wishlily.github.io/article/code/2017/03/21/undefined/
作者
Wishlily
发布于
2017年3月21日
许可协议