рабочий код. (Вы можете найти кубические корневые искатели довольно легко)
/*
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;
}
Вы можете быть более конкретным? Вы имеете в виду, что у вас есть две кривые (например, набор координат), и вы хотите увидеть, является ли одно из них (приблизительным) подмножеством другого? О чем вы думали до сих пор? Почему вы думаете, что это будет или не будет работать? Вы реализовали это, чтобы проверить свою идею? и т. д. –
Скажем, мы возьмем кривую Безье и разделим ее с помощью алгоритма Кастеляу. Очевидно, что результатом является множество подкривых исходной кривой. Вопрос заключается в том, как вернуться и восстановить значения t, а также то, что кривые являются частью одной и той же кривой, учитывая только их 4 контрольные точки. –
Итак, какой из двух вас интересует? «Посмотрите, является ли кривая B субквервой на кривой A» или «попытайтесь восстановить неизвестную кривую при известных кривых A, B, C и т. Д.»?Потому что это очень разные вещи, и ваш комментарий подсказывает вам, что вы действительно хотите найти неизвестную «большую» кривую, учитывая несколько известных «маленьких» кривых. Это другой вопрос, о котором спрашивает ваш пост. –