Эквидистантные точки на кривых Безье

В настоящее время я пытаюсь сделать так, чтобы у нескольких Безье были равноудаленные точки. В настоящее время я использую кубическую интерполяцию, чтобы найти точки, но поскольку методы Безье работают, некоторые области являются более плотными, чем другие, и получаются грубыми для наложения текстур из-за переменного расстояния. Есть ли способ найти точки на Безье по расстоянию, а не по процентам? Кроме того, возможно ли распространить это на несколько связанных кривых?

13.08.2008 23:31:32
Смотрите также math.stackexchange.com/a/61796/589 .
lhf 13.01.2016 12:09:59
3 ОТВЕТА
РЕШЕНИЕ

расстояние между P_0 и P_3 (в кубической форме), да, но я думаю, что вы знали это, прямо вперед.

Расстояние по кривой - просто длина дуги:

Рис. 1 http://www.codecogs.com/eq.latex?%5Cint_%7Bt_0%7D%5E%7Bt_1%7D%20%7B%20|P'(t)|%20dt

где:

рис 2 http://www.codecogs.com/eq.latex?P%27(t)%20=%20[%7Bx%27,y%27,z%27%7D]%20=%20[% 7В% 5Cfrac% 7Bdx (т)% 7D% 7Bdt% 7D,% 5Cfrac% 7Bdy (т)% 7D% 7Bdt% 7D,% 5Cfrac% 7Bdz (т)% 7D% 7Bdt% 7D% 7D]

(см остальное)

Возможно, вы бы имели t_0 = 0, t_1 = 1.0 и dz (t) = 0 (плоскость 2d).

4
14.08.2008 00:50:47
Вот как вы находите длину дуги по заданному параметру, но для нахождения равноотстоящих точек требуется обратная функция этой функции. Переход от одного к другому не тривиален. @ Кристиан Ромо: как ты это сделал? Я имею в виду, вы можете просто использовать бинарный поиск, но это будет ужасно медленно (во всяком случае, для того, что я пытаюсь сделать).
CromTheDestroyer 19.11.2010 04:18:21

Это называется параметризацией "длина дуги". Я написал статью об этом несколько лет назад:

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

Идея состоит в том, чтобы предварительно вычислить кривую «параметризации» и оценить ее через нее.

9
12.05.2009 22:23:58
Еще не полностью прочитал газету. Но я хотел бы спросить, есть ли лучший способ определить кривые, которые не нужно было бы сначала «преобразовывать». Например, знаете ли вы, если бы я использовал NURBS для определения всех путей / кривых, будет ли он поддерживать более быструю параметризацию длины эквидистантной дуги? Или как-то иначе? Изменить: быстрее я имею в виду использование процессора или графического процессора.
Ciantic 11.05.2013 12:49:50
Использование NURB не поможет, основная проблема та же. В конце статьи показан метод составления кривой повторной параметризации с оригиналом. В результате получается новая кривая с параметризацией длины дуги, но в порядке, если кривая выше, поэтому ее оценка медленнее.
J. Peterson 17.05.2013 01:00:56

Я знаю, что это старый вопрос, но недавно я столкнулся с этой проблемой и создал UIBezierPathрасширение для решения для Xкоординаты, заданной Yкоординатой, и наоборот. Написано по-быстрому.

https://github.com/rkotzy/RKBezierMath

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)
}

}
2
15.01.2016 18:23:31