/
ellipse.go
144 lines (137 loc) · 2.78 KB
/
ellipse.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
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
package draw
type point struct {
x, y int
}
// ellipseArea returns a list of consecutive point pairs. Each pair lies on a
// horizontal line (i.e. both generator have the same y position) and if you draw
// horizontal pixels lines for all pairs, you will have the requested ellipse.
//
// c···d
// g·········h
// i···········j
// e·········f
// a···b
//
func ellipseArea(x, y, w, h int) (p []point) {
quarter := quaterEllipsePoints(w, h)
xPivot, yPivot := 0, 0
if w%2 == 0 {
xPivot = 1
}
if h%2 == 0 {
yPivot = 1
}
dx, dy := x+w/2, y+h/2
for i := 0; i < len(quarter); i++ {
if i == len(quarter)-1 || quarter[i].y != quarter[i+1].y {
p = append(p,
// this line
point{
x: -quarter[i].x - xPivot + dx,
y: quarter[i].y + dy,
},
point{
x: quarter[i].x + dx,
y: quarter[i].y + dy,
},
// the line mirrored in y
point{
x: -quarter[i].x - xPivot + dx,
y: -quarter[i].y - yPivot + dy,
},
point{
x: quarter[i].x + dx,
y: -quarter[i].y - yPivot + dy,
},
)
}
}
// remove the last line if it is contained twice at the end
n := len(p)
if n >= 4 && p[n-1] == p[n-3] {
p = p[:n-2]
}
return
}
// ellipseOutline returns a list of pixel positions that mark the outline of the
// requested ellipse.
//
// jih
// lk gf
// m e
// no cd
// pab
//
func ellipseOutline(x, y, w, h int) []point {
quarter := quaterEllipsePoints(w, h)
xPivot, yPivot := 0, 0
if w%2 == 0 {
xPivot = 1
}
if h%2 == 0 {
yPivot = 1
}
dx, dy := x+w/2, y+h/2
p := make([]point, 0, len(quarter)*4)
for i := range quarter {
p = append(p, point{
x: quarter[i].x + dx,
y: quarter[i].y + dy,
})
}
for i := len(quarter) - 1 - (1 - yPivot); i >= 0; i-- {
p = append(p, point{
x: quarter[i].x + dx,
y: -quarter[i].y - yPivot + dy,
})
}
for i := 1 - xPivot; i < len(quarter); i++ {
p = append(p, point{
x: -quarter[i].x - xPivot + dx,
y: -quarter[i].y - yPivot + dy,
})
}
for i := len(quarter) - 1 - (1 - yPivot); i >= 1-xPivot; i-- {
p = append(p, point{
x: -quarter[i].x - xPivot + dx,
y: quarter[i].y + dy,
})
}
return p
}
func quaterEllipsePoints(w, h int) (p []point) {
if w <= 0 || h <= 0 {
return nil
}
a, b := (w-1)/2, (h-1)/2
x, y := 0, b
a2, b2 := a*a, b*b
crit1 := -(a2/4 + a%2 + b2)
crit2 := -(b2/4 + b%2 + a2)
crit3 := -(b2/4 + b%2)
t := -a2 * y
dxt := 2 * b2 * x
dyt := -2 * a2 * y
d2xt := 2 * b2
d2yt := 2 * a2
for y >= 0 && x <= a {
p = append(p, point{x: x, y: y})
if t+b2*x <= crit1 || t+a2*y <= crit3 {
x++
dxt += d2xt
t += dxt
} else if t-a2*y > crit2 {
y--
dyt += d2yt
t += dyt
} else {
x++
dxt += d2xt
t += dxt
y--
dyt += d2yt
t += dyt
}
}
return
}