关于图形:贝塞尔曲线上的等距点

关于图形:贝塞尔曲线上的等距点

Equidistant points across Bezier curves

当前,我正在尝试使多个贝塞尔曲线具有等距的点。我目前正在使用三次插值法来找到这些点,但是由于贝塞尔曲线的工作方式某些区域比其他区域更密集,并且由于距离可变,证明了纹理贴图的总体效果。有没有一种方法可以通过距离而不是百分比来在贝塞尔曲线上找到点?此外,是否可以将其扩展到多个连接的曲线?


这称为"弧长"参数化。几年前,我写了一篇关于此的论文:

http://www.saccade.com/writing/graphics/RE-PARAM.PDF

这个想法是预先计算一条"参数化"曲线,并通过该曲线评估曲线。


P_0和P_3之间的距离(以立方形式表示),是的,但是我想您知道这很简单。

曲线上的距离仅是弧长:

图1 http://www.codecogs.com/eq.latex?\\\\int_{t_0}^{t_1} {| P \\'(t)| dt

其中:

图2 http://www.codecogs.com/eq.latex?P\\'(t)= [{x \\',y \\',z \\'}] = [{\\\\ frac {dx( t)} {dt},\\\\ frac {dy(t)} {dt},\\\\ frac {dz(t)} {dt}}]

(请参阅其余部分)

可能您将拥有t_0 = 0,t_1 = 1.0和dz(t)= 0(二维平面)。


我知道这是一个老问题,但是最近我遇到了这个问题,并创建了UIBezierPath扩展来解决给定Y坐标的X坐标,反之亦然。写得很快。

https://github.com/rkotzy/RKBezierMath

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
159
160
161
162
163
extension UIBezierPath {

func solveBezerAtY(start: CGPoint, point1: CGPoint, point2: CGPoint, end: CGPoint, y: CGFloat) -> [CGPoint] {

    // bezier control points
    let C0 = start.y - y
    let C1 = point1.y - y
    let C2 = point2.y - y
    let C3 = end.y - y

    // The cubic polynomial coefficients such that Bez(t) = A*t^3 + B*t^2 + C*t + D
    let A = C3 - 3.0*C2 + 3.0*C1 - C0
    let B = 3.0*C2 - 6.0*C1 + 3.0*C0
    let C = 3.0*C1 - 3.0*C0
    let D = C0

    let roots = solveCubic(A, b: B, c: C, d: D)

    var result = [CGPoint]()

    for root in roots {
        if (root >= 0 && root <= 1) {
            result.append(bezierOutputAtT(start, point1: point1, point2: point2, end: end, t: root))
        }
    }

    return result
}

func solveBezerAtX(start: CGPoint, point1: CGPoint, point2: CGPoint, end: CGPoint, x: CGFloat) -> [CGPoint] {

    // bezier control points
    let C0 = start.x - x
    let C1 = point1.x - x
    let C2 = point2.x - x
    let C3 = end.x - x

    // The cubic polynomial coefficients such that Bez(t) = A*t^3 + B*t^2 + C*t + D
    let A = C3 - 3.0*C2 + 3.0*C1 - C0
    let B = 3.0*C2 - 6.0*C1 + 3.0*C0
    let C = 3.0*C1 - 3.0*C0
    let D = C0

    let roots = solveCubic(A, b: B, c: C, d: D)

    var result = [CGPoint]()

    for root in roots {
        if (root >= 0 && root <= 1) {
            result.append(bezierOutputAtT(start, point1: point1, point2: point2, end: end, t: root))
        }
    }

    return result

}

func solveCubic(a: CGFloat?, var b: CGFloat, var c: CGFloat, var d: CGFloat) -> [CGFloat] {

    if (a == nil) {
        return solveQuadratic(b, b: c, c: d)
    }

    b /= a!
    c /= a!
    d /= a!

    let p = (3 * c - b * b) / 3
    let q = (2 * b * b * b - 9 * b * c + 27 * d) / 27

    if (p == 0) {
        return [pow(-q, 1 / 3)]

    } else if (q == 0) {
        return [sqrt(-p), -sqrt(-p)]

    } else {

        let discriminant = pow(q / 2, 2) + pow(p / 3, 3)

        if (discriminant == 0) {
            return [pow(q / 2, 1 / 3) - b / 3]

        } else if (discriminant > 0) {
            let x = crt(-(q / 2) + sqrt(discriminant))
            let z = crt((q / 2) + sqrt(discriminant))
            return [x - z - b / 3]
        } else {

            let r = sqrt(pow(-(p/3), 3))
            let phi = acos(-(q / (2 * sqrt(pow(-(p / 3), 3)))))

            let s = 2 * pow(r, 1/3)

            return [
                s * cos(phi / 3) - b / 3,
                s * cos((phi + CGFloat(2) * CGFloat(M_PI)) / 3) - b / 3,
                s * cos((phi + CGFloat(4) * CGFloat(M_PI)) / 3) - b / 3
            ]

        }

    }
}

func solveQuadratic(a: CGFloat, b: CGFloat, c: CGFloat) -> [CGFloat] {

    let discriminant = b * b - 4 * a * c;

    if (discriminant < 0) {
        return []

    } else {
        return [
            (-b + sqrt(discriminant)) / (2 * a),
            (-b - sqrt(discriminant)) / (2 * a)
        ]
    }

}

private func crt(v: CGFloat) -> CGFloat {
    if (v<0) {
        return -pow(-v, 1/3)
    }
    return pow(v, 1/3)
}

private func bezierOutputAtT(start: CGPoint, point1: CGPoint, point2: CGPoint, end: CGPoint, t: CGFloat) -> CGPoint {

    // bezier control points
    let C0 = start
    let C1 = point1
    let C2 = point2
    let C3 = end

    // The cubic polynomial coefficients such that Bez(t) = A*t^3 + B*t^2 + C*t + D
    let A = CGPointMake(C3.x - 3.0*C2.x + 3.0*C1.x - C0.x, C3.y - 3.0*C2.y + 3.0*C1.y - C0.y)
    let B = CGPointMake(3.0*C2.x - 6.0*C1.x + 3.0*C0.x, 3.0*C2.y - 6.0*C1.y + 3.0*C0.y)
    let C = CGPointMake(3.0*C1.x - 3.0*C0.x, 3.0*C1.y - 3.0*C0.y)
    let D = C0

    return CGPointMake(((A.x*t+B.x)*t+C.x)*t+D.x, ((A.y*t+B.y)*t+C.y)*t+D.y)
}

// TODO: - future implementation
private func tangentAngleAtT(start: CGPoint, point1: CGPoint, point2: CGPoint, end: CGPoint, t: CGFloat) -> CGFloat {

    // bezier control points
    let C0 = start
    let C1 = point1
    let C2 = point2
    let C3 = end

    // The cubic polynomial coefficients such that Bez(t) = A*t^3 + B*t^2 + C*t + D
    let A = CGPointMake(C3.x - 3.0*C2.x + 3.0*C1.x - C0.x, C3.y - 3.0*C2.y + 3.0*C1.y - C0.y)
    let B = CGPointMake(3.0*C2.x - 6.0*C1.x + 3.0*C0.x, 3.0*C2.y - 6.0*C1.y + 3.0*C0.y)
    let C = CGPointMake(3.0*C1.x - 3.0*C0.x, 3.0*C1.y - 3.0*C0.y)

    return atan2(3.0*A.y*t*t + 2.0*B.y*t + C.y, 3.0*A.x*t*t + 2.0*B.x*t + C.x)
}

}

推荐阅读