Wishlily's blog谢尔宾斯基三角形
目录
使用 golang 绘制一个带颜色的谢尔宾斯基三角形。
定义1
使用去掉中心法：
- 取一个实心的三角形（多数使用等边三角形）
- 沿三边中点的连线，将它分成四个小三角形
- 去掉中间的那一个小三角形
- 对其余三个小三角形重复 1~4 步骤
实现
三角形
因为需要上色，首先需要一个三角形填充函数。
我的做法是首先将三角形四边边界求出，然后逐点判断是否在三角形内部23。
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 形式扫描，但是以下的代码并不是所有三角形都能绘制，目前还未想好如何不增加计算时间又能改进的办法。
/* 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
}
}
谢尔宾斯基三角
通过递归函数绘制，颜色未指定则随机生成。
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)
}
测试
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)
}