Проверьте, является ли кривая Безье подкривой другого Безье

Question

Я хочу проверить, является ли кубическая кривая Безье подкривой другого Безье.

Я думаю, что я в основном понимаю, как это сделать, выразить Безье как две кубики, в x и y, а затем проверить, являются ли кубики масштабированием или переводом друг друга. Если масштабирование и сдвиг совпадают, это говорит о том, что кривые являются подсегментами одной и той же кривой и дают нам t0 простое и t1 простое кривой B на кривой As space.

Но я не могу понять, как проверить кубики на эквивалентность.

Answer 1

Ответ основан на следующем комментарии:

Скажем, мы берем кривую Безье и разделяем ее, используя алгоритм де Кастельжау. Очевидно, что результатом является множество подкривусов исходной кривой. Вопрос состоит в том, как вернуться назад и восстановить значения t, а также в том, что кривые являются частью одной кривой, учитывая только их 4 контрольные точки.

Короткий ответ: если у вас нет машины бесконечной точности, вы не можете.

Итак, мы застряли с тестированием на "порог ошибки". Учитывая мастер-кривую A и "надеюсь, подкатегория" кривая B, пробежаться по вещам, которые должны быть истинными, если B был подкатугом A:

1. Если B является истинной подкривой, то ее начальная и конечная точка лежат на кривой A. Поэтому проверьте, верно ли это, в пределах некоторого порога ошибки. Если они этого не делают, то B не является подкатом A.
2. Если B - истинная кривая, то производные в начальной и конечной точках B совпадают с производными для соответствующих координат на A. Поэтому проверьте, верно ли это, в пределах некоторого порога ошибки. Если это не так, B - это не кривая A.
3. Если B - истинная кривая, то вторые производные в начальной и конечной точках B совпадают со вторыми производными для соответствующих координат на A. Поэтому проверьте, верно ли это, в пределах некоторого порога ошибки. Если это не так, B - это не кривая A.

Если все это верно, мы можем быть достаточно уверены, что B является подкатом A.

Кроме того, так как мы должны придумать t значения, чтобы проверить, лежит ли точка на A, и какая производная от A находится в этой точке, мы уже знаем t значения, которые определяют интервал на A, который отображается на полную кривую B.

Answer 2

Вот рабочий код. (Вы можете легко найти кубические искатели корней)

 /*
        A = p3 + 3.0 * p1 - 3.0 * p2 - p0;
        B = 3.0 * p0 - 6.0 * p1 + 3.0 * p2;
        C = 3.0 * p1 - 3.0 * p0;
        D = p0;
    */
        bool CurveIsSubCurve(BezierCurve bez, BezierCurve sub, double epsilon, double *t)
        {
            int Nr;
            double tcand[6];
            int i, ii;
            double ts[6], te[6];
            int Ns = 0;
            int Ne = 0;
            Vector2 p;

            /*
              Take two bites at the cherry. The points may have slight errors, and a small error in x or y could represent a big error in
    t. However with any luck either x or y will be close 
            */
            Nr = cubic_roots(bez.Ax(), bez.Bx(), bez.Cx(), bez.Dx() - sub.P0().x, tcand);
            Nr += cubic_roots(bez.Ay(), bez.By(), bez.Cy(), bez.Dy() - sub.P0().y, tcand + Nr);

            for(i=0;i<Nr;i++)
            {
                p = bez.Eval(tcand[i]);
                if(fabs(p.x - sub.P0().x) < epsilon && fabs(p.y - sub.P0().y) < epsilon)
                {
                    ts[Ns++] = tcand[i];
                }
            }

    /* same thing of sub curve end point */
            Nr = cubic_roots(bez.Ax(), bez.Bx(), bez.Cx(), bez.Dx() - sub.P3().x, tcand);
            Nr += cubic_roots(bez.Ay(), bez.By(), bez.Cy(), bez.Dy() - sub.P3().y, tcand + Nr);
            for(i=0;i<Nr;i++)
            {
                p = bez.Eval(tcand[i]);
                if(fabs(p.x - sub.P3().x) < epsilon && fabs(p.y - sub.P3().y) < epsilon)
                {
                    te[Ne++] = tcand[i];
                }
            }

    /* do an all by all to get matches (Ns, Ne will be small, but if
    we have a degenerate, i.e. a loop, the loop intersection point is
    where the mother curve is quite likely to be cut, so test everything*/

            for(i = 0; i < Ns; i++)
            {
                double s,d;
                double Ax, Bx, Cx, Dx;
                double Ay, By, Cy, Dy;

                for(ii=0;ii<Ne;ii++)
                {
                    s = (te[ii] - ts[i]);
                    d = ts[i];

    /* now substitute back */
                    Ax = bez.Ax() *s*s*s;
                    Bx = bez.Ax() *2*s*s*d + bez.Ax()*s*s*d + bez.Bx()*s*s;
                    Cx = bez.Ax()*s*d*d + bez.Ax()*2*s*d*d + bez.Bx()*2*s*d + bez.Cx() * s;
                    Dx = bez.Ax() *d*d*d + bez.Bx()*d*d + bez.Cx()*d + bez.Dx();

                    Ay = bez.Ay() *s*s*s;
                    By = bez.Ay() *2*s*s*d + bez.Ay()*s*s*d + bez.By()*s*s;
                    Cy = bez.Ay()*s*d*d + bez.Ay()*2*s*d*d + bez.By()*2*s*d + bez.Cy() * s;
                    Dy = bez.Ay() *d*d*d + bez.By()*d*d + bez.Cy()*d + bez.Dy();

                    if(fabs(Ax - sub.Ax()) < epsilon && fabs(Bx - sub.Bx()) < epsilon &&
                       fabs(Cx - sub.Cx()) < epsilon && fabs(Dx - sub.Dx()) < epsilon &&
                       fabs(Ay - sub.Ay()) < epsilon && fabs(By - sub.By()) < epsilon &&
                       fabs(Cy - sub.Cy()) < epsilon && fabs(Dy - sub.Dy()) < epsilon)
                    {
                        if(t)
                        {
                            t[0] = ts[i];
                            t[1] = te[ii];
                        }
                        return true;

                    }

                }
            }

            return false;
        }