forked from wcharczuk/go-chart
-
Notifications
You must be signed in to change notification settings - Fork 0
/
curve.go
158 lines (132 loc) · 3.79 KB
/
curve.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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
package drawing
import (
"math"
)
const (
// CurveRecursionLimit represents the maximum recursion that is really necessary to subsivide a curve into straight lines
CurveRecursionLimit = 32
)
// Cubic
// x1, y1, cpx1, cpy1, cpx2, cpy2, x2, y2 float64
// SubdivideCubic a Bezier cubic curve in 2 equivalents Bezier cubic curves.
// c1 and c2 parameters are the resulting curves
func SubdivideCubic(c, c1, c2 []float64) {
// First point of c is the first point of c1
c1[0], c1[1] = c[0], c[1]
// Last point of c is the last point of c2
c2[6], c2[7] = c[6], c[7]
// Subdivide segment using midpoints
c1[2] = (c[0] + c[2]) / 2
c1[3] = (c[1] + c[3]) / 2
midX := (c[2] + c[4]) / 2
midY := (c[3] + c[5]) / 2
c2[4] = (c[4] + c[6]) / 2
c2[5] = (c[5] + c[7]) / 2
c1[4] = (c1[2] + midX) / 2
c1[5] = (c1[3] + midY) / 2
c2[2] = (midX + c2[4]) / 2
c2[3] = (midY + c2[5]) / 2
c1[6] = (c1[4] + c2[2]) / 2
c1[7] = (c1[5] + c2[3]) / 2
// Last Point of c1 is equal to the first point of c2
c2[0], c2[1] = c1[6], c1[7]
}
// TraceCubic generate lines subdividing the cubic curve using a Liner
// flattening_threshold helps determines the flattening expectation of the curve
func TraceCubic(t Liner, cubic []float64, flatteningThreshold float64) {
// Allocation curves
var curves [CurveRecursionLimit * 8]float64
copy(curves[0:8], cubic[0:8])
i := 0
// current curve
var c []float64
var dx, dy, d2, d3 float64
for i >= 0 {
c = curves[i*8:]
dx = c[6] - c[0]
dy = c[7] - c[1]
d2 = math.Abs((c[2]-c[6])*dy - (c[3]-c[7])*dx)
d3 = math.Abs((c[4]-c[6])*dy - (c[5]-c[7])*dx)
// if it's flat then trace a line
if (d2+d3)*(d2+d3) < flatteningThreshold*(dx*dx+dy*dy) || i == len(curves)-1 {
t.LineTo(c[6], c[7])
i--
} else {
// second half of bezier go lower onto the stack
SubdivideCubic(c, curves[(i+1)*8:], curves[i*8:])
i++
}
}
}
// Quad
// x1, y1, cpx1, cpy2, x2, y2 float64
// SubdivideQuad a Bezier quad curve in 2 equivalents Bezier quad curves.
// c1 and c2 parameters are the resulting curves
func SubdivideQuad(c, c1, c2 []float64) {
// First point of c is the first point of c1
c1[0], c1[1] = c[0], c[1]
// Last point of c is the last point of c2
c2[4], c2[5] = c[4], c[5]
// Subdivide segment using midpoints
c1[2] = (c[0] + c[2]) / 2
c1[3] = (c[1] + c[3]) / 2
c2[2] = (c[2] + c[4]) / 2
c2[3] = (c[3] + c[5]) / 2
c1[4] = (c1[2] + c2[2]) / 2
c1[5] = (c1[3] + c2[3]) / 2
c2[0], c2[1] = c1[4], c1[5]
return
}
// TraceQuad generate lines subdividing the curve using a Liner
// flattening_threshold helps determines the flattening expectation of the curve
func TraceQuad(t Liner, quad []float64, flatteningThreshold float64) {
// Allocates curves stack
var curves [CurveRecursionLimit * 6]float64
copy(curves[0:6], quad[0:6])
i := 0
// current curve
var c []float64
var dx, dy, d float64
for i >= 0 {
c = curves[i*6:]
dx = c[4] - c[0]
dy = c[5] - c[1]
d = math.Abs(((c[2]-c[4])*dy - (c[3]-c[5])*dx))
// if it's flat then trace a line
if (d*d) < flatteningThreshold*(dx*dx+dy*dy) || i == len(curves)-1 {
t.LineTo(c[4], c[5])
i--
} else {
// second half of bezier go lower onto the stack
SubdivideQuad(c, curves[(i+1)*6:], curves[i*6:])
i++
}
}
}
// TraceArc trace an arc using a Liner
func TraceArc(t Liner, x, y, rx, ry, start, angle, scale float64) (lastX, lastY float64) {
end := start + angle
clockWise := true
if angle < 0 {
clockWise = false
}
ra := (math.Abs(rx) + math.Abs(ry)) / 2
da := math.Acos(ra/(ra+0.125/scale)) * 2
//normalize
if !clockWise {
da = -da
}
angle = start + da
var curX, curY float64
for {
if (angle < end-da/4) != clockWise {
curX = x + math.Cos(end)*rx
curY = y + math.Sin(end)*ry
return curX, curY
}
curX = x + math.Cos(angle)*rx
curY = y + math.Sin(angle)*ry
angle += da
t.LineTo(curX, curY)
}
}