/
quadtree.go
88 lines (70 loc) · 1.87 KB
/
quadtree.go
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
package main
import (
"image"
colorlib "image/color"
)
const (
NE = iota
NW = iota
SW = iota
SE = iota
)
type QuadTreeNode struct {
Quadrant [4]*QuadTreeNode
Color uint32
}
type QuadTree struct {
Root *QuadTreeNode
Height int
Width int
}
func BuildQuadTree(img image.Image) (*QuadTree, error) {
qt := QuadTree{}
qt.Width = img.Bounds().Max.X - 1 - img.Bounds().Min.X
qt.Height = img.Bounds().Max.Y - 1 - img.Bounds().Min.Y
qt.Root = buildQuadTree(img, img.Bounds().Min.X, img.Bounds().Min.Y, qt.Width, qt.Height)
return &qt, nil
}
func buildQuadTree(img image.Image, x, y, w, h int) *QuadTreeNode {
if w == 0 && h == 0 {
qn := QuadTreeNode{Color: PackColor(img.At(x, y))}
return &qn
}
qn := QuadTreeNode{}
qn.Quadrant[NW] = buildQuadTree(img, x, y, w/2, h/2)
qn.Quadrant[NE] = buildQuadTree(img, x+(w/2), y, w/2, h/2)
qn.Quadrant[SW] = buildQuadTree(img, x, y+(h/2), w/2, h/2)
qn.Quadrant[SE] = buildQuadTree(img, x+(w/2), y+(h/2), w/2, h/2)
if qn.Quadrant[NE] != nil && qn.Quadrant[NW] != nil && qn.Quadrant[SW] != nil && qn.Quadrant[SE] != nil {
var red uint32
var green uint32
var blue uint32
var alpha uint32
for _, child := range []*QuadTreeNode{qn.Quadrant[NE], qn.Quadrant[NW], qn.Quadrant[SE], qn.Quadrant[SW]} {
red_, green_, blue_, alpha_ := UnpackColor(child.Color).RGBA()
red += red_
green += green_
blue += blue_
alpha += alpha_
}
red /= 4
green /= 4
blue /= 4
alpha /= 4
qn.Color = PackColor(colorlib.RGBA64{R: uint16(red), G: uint16(green), B: uint16(blue), A: uint16(alpha)})
}
return &qn
}
func (q *QuadTree) Leaves() int {
return q.Root.leaves()
}
func (q *QuadTreeNode) leaves() int {
leaves := 1
if q.Quadrant[NE] != nil { //not a leaf node
leaves += q.Quadrant[NE].leaves()
leaves += q.Quadrant[NW].leaves()
leaves += q.Quadrant[SE].leaves()
leaves += q.Quadrant[SW].leaves()
}
return leaves
}