谢尔宾斯基三角形

使用 golang 绘制一个带颜色的谢尔宾斯基三角形。

定义1

使用去掉中心法：

  1. 取一个实心的三角形（多数使用等边三角形）
  2. 沿三边中点的连线，将它分成四个小三角形
  3. 去掉中间的那一个小三角形
  4. 对其余三个小三角形重复 1~4 步骤

实现

三角形

因为需要上色，首先需要一个三角形填充函数。
我的做法是首先将三角形四边边界求出，然后逐点判断是否在三角形内部23。

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
const (
    _TRIANGLE_SIDE = false
)

func triangle_cross(a, b, c image.Point) int {
    ab := image.Point{b.X - a.X, b.Y - a.Y}
    ac := image.Point{c.X - a.X, c.Y - a.Y}
    return ab.X*ac.Y - ab.Y*ac.X
}

func triangle_right_side(a, b, c image.Point) bool {
    if triangle_cross(a, b, c) > 0 {
        return true
    }
    return false
}

/*
 * 排序
 * 最靠近 x 轴的点为第一个点，剩下逆时针排序
 */
func triangle_sort(a, b, c image.Point) (image.Point, image.Point, image.Point) {
    sort := []image.Point{a, b, c}
    n := 0
    for i := 1; i < 3; i++ {
        if sort[i].Y < sort[n].Y {
            n = i
        } else if sort[i].Y == sort[n].Y {
            if sort[i].X < sort[n].X {
                n = i
            }
        }
    }
    if n != 0 {
        t := sort[0]
        sort[0] = sort[n]
        sort[n] = t
    }
    if triangle_right_side(sort[0], sort[1], sort[2]) == _TRIANGLE_SIDE {
        return sort[0], sort[1], sort[2]
    }
    return sort[0], sort[2], sort[1]
}

func triangle_min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func triangle_max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func triangle_1(img *image.RGBA, A, B, C image.Point, c color.Color) {
    A, B, C = triangle_sort(A, B, C)
    // fmt.Println(A, B, C)

    // 扫描正方形
    x_min, x_max := A.X, A.X
    y_min, y_max := A.Y, A.Y

    x_min = triangle_min(x_min, B.X)
    x_min = triangle_min(x_min, C.X)
    x_max = triangle_max(x_max, B.X)
    x_max = triangle_max(x_max, C.X)

    y_min = triangle_min(y_min, B.Y)
    y_min = triangle_min(y_min, C.Y)
    y_max = triangle_max(y_max, B.Y)
    y_max = triangle_max(y_max, C.Y)

    for i := x_min; i <= x_max; i++ {
        for j := y_min; j <= y_max; j++ {
            D := image.Point{i, j}
            if triangle_right_side(A, B, D) == _TRIANGLE_SIDE &&
                triangle_right_side(B, C, D) == _TRIANGLE_SIDE &&
                triangle_right_side(C, A, D) == _TRIANGLE_SIDE {
                img.Set(i, j, c)
            }
        }
    }
}

查看资料4由图片启发，可以从顶点开始 S 形式扫描，但是以下的代码并不是所有三角形都能绘制，目前还未想好如何不增加计算时间又能改进的办法。

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
/* BUG: 一些锐角三角形无法绘出 */
func triangle_2(img *image.RGBA, A, B, C image.Point, c color.Color) {
    A, B, C = triangle_sort(A, B, C)
    // fmt.Println(A, B, C)

    // 蛇字形扫描
    x_min, x_max := A.X, A.X
    x_min = triangle_min(x_min, B.X)
    x_min = triangle_min(x_min, C.X)
    x_max = triangle_max(x_max, B.X)
    x_max = triangle_max(x_max, C.X)

    x := A.X
    x_step := 1
    for y, loop := A.Y, true; loop; y++ {
        loop = false
        for ; x >= x_min && x <= x_max; x += x_step {
            D := image.Point{x, y}
            if triangle_right_side(A, B, D) == _TRIANGLE_SIDE &&
                triangle_right_side(B, C, D) == _TRIANGLE_SIDE &&
                triangle_right_side(C, A, D) == _TRIANGLE_SIDE {
                loop = true
                img.Set(x, y, c)
            } else if loop {
                break
            }
        }
        x_step *= -1
    }
}

谢尔宾斯基三角

通过递归函数绘制，颜色未指定则随机生成。

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
func sierpinski_fc(img *image.RGBA, A, B, C image.Point, c []color.Color) {
    if len(c) <= 0 {
        return
    }
    triangle_1(img, A, B, C, c[0])
    D := image.Point{(A.X + B.X) / 2, (A.Y + B.Y) / 2}
    E := image.Point{(B.X + C.X) / 2, (B.Y + C.Y) / 2}
    F := image.Point{(C.X + A.X) / 2, (C.Y + A.Y) / 2}
    c1 := c[1:]
    sierpinski_fc(img, A, D, F, c1)
    sierpinski_fc(img, D, B, E, c1)
    sierpinski_fc(img, F, E, C, c1)
}

func sierpinski(img *image.RGBA, x, y int) {
    A := image.Point{x / 2, 0}
    B := image.Point{0, y}
    C := image.Point{x, y}
    c := []color.Color{
    // color.RGBA{0xEC, 0xD6, 0xC6, 255},
    // color.RGBA{0xD4, 0xDA, 0x90, 255},
    // color.RGBA{0xC1, 0xBC, 0x44, 255},
    // color.RGBA{0x63, 0x21, 0x5D, 255},
    // color.RGBA{0xB4, 0x3C, 0xAC, 255},
    // color.RGBA{0xD6, 0x85, 0xCB, 255},
    // color.RGBA{0xA1, 0x36, 0x5F, 255},
    }
    s := rand.NewSource(time.Now().Unix())
    r := rand.New(s)
    if len(c) == 0 {
        for i := 0; i < 7; i++ {
            t := r.Intn(0xFFFFFF)
            c_r := uint8(t >> 16)
            c_b := uint8(t >> 8)
            c_g := uint8(t)
            c = append(c, color.RGBA{c_r, c_b, c_g, 255})
        }
    }
    sierpinski_fc(img, A, B, C, c)
}

测试

1
2
3
4
5
6
7
8
9
10
11
func Test_sierpinski(t *testing.T) {
    const (
        x = 4000
        y = 3500
    )
    img := image.NewRGBA(image.Rect(0, 0, x, y))
    sierpinski(img, x, y)
    f, _ := os.OpenFile("sierpinski.png", os.O_WRONLY|os.O_CREATE, 0600)
    defer f.Close()
    png.Encode(f, img)
}

结果：

code
#golang #draw #分形
谢尔宾斯基三角形
https://wishlily.github.io/article/code/2017/04/07/undefined/
作者
Wishlily
发布于
2017年4月7日
许可协议