Кривые Безье
Исходные данные: набор кривых Безье (шаблонов), произвольный набор координат точек образующих фигуру ("проверяемую").
Задача: определить степень похожести проверяемой фигуры заданной набором точек и шаблона заданного кривой Безье.
Для начала рассмотрим очень упрощенно, и лишь для одного куска кривой Безье. Например для кривой Безье, заданной тремя контрольными точками A, B, C:
![X(a) = Xa*a^2 + Xb*2*a*b + Xc*b^2 X(a) = Xa*a^2 + Xb*2*a*b + Xc*b^2](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQjsIrdYldys9MzQSY4doqHSoWu0TXji7EWDMoyrP0ub-09GUsp3rmC6wbHwKcUOCjVih-5tFzMDjD1fCBc223c_TEdMEhBZuN-4k-ZGdyeV6kJ23EoVkWSpeQRjB6MmEqgTiKExhqGNiE/s800/Xa.png)
![Y(a) = Ya*a^2 + Yb*2*a*b + Yc*b^2 Y(a) = Ya*a^2 + Yb*2*a*b + Yc*b^2](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjFYOY7E5VQ1S75_vKaTbTYvytNtBwAA-R5Eb9k-8p1NG4lwN6bF3OTZpXtUIldxUs0z0t_W28q4k5QkCgLxGtvp_R2k0Y-bmR5RPyJqbv5LCjGFXBo2QopxvHBSvfsldmLmBJeau2xuw-V/s800/Ya.png)
XA, YA, ZA, XB, YB, ZB, XC, YC,ZC - координаты x, y, z исходных узлов A, B, C соответственно.
Тогда, если подставлять вместо X(a), Y(a), Z(a) координаты точки из проверяемой фигуры, можно находить для каждого уравнения значение коэффициента а:
![ax= (±sqrt((Xc-2*Xb+Xa)*X-Xa*Xc+Xb^2)+Xc-Xb)/(Xc-2*Xb+Xa) ax= (±sqrt((Xc-2*Xb+Xa)*X-Xa*Xc+Xb^2)+Xc-Xb)/(Xc-2*Xb+Xa)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh83VWLpqbxbtvzvRoF2pdYpj2l2RU277oQJAnKEixx5j7md-Z-yYTrW_xVFfA0BXxxlLf2sMeKgA55Ybuab-FJSPoJ00bRXTD_yci-E7CHoEkJ2RADqM7x6D5ygNE2he6UhRftQI9173Ln/s800/ax.png)
![ay= (±sqrt((Yc-2*Yb+Ya)*Y-Ya*Yc+Yb^2)+Yc-Yb)/(Yc-2*Yb+Ya) ay= (±sqrt((Yc-2*Yb+Ya)*Y-Ya*Yc+Yb^2)+Yc-Yb)/(Yc-2*Yb+Ya)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9xaabL3b3Ec5oF5v6dQReCFPn2Da_zBMU1wKJ0AqqwR-IQl07YtwKsMKkPCJ55e0wKIR5NPKc3S40rmNx_WbU6rOwJTyWMnQSTY25UeFPcN0gt1BPdcpFla34Jva_WgwnveKWiAdeJJ6c/s800/ay.png)
![az= (±sqrt((Zc-2*Zb+Za)*Z-Za*Zc+Zb^2)+Zc-Zb)/(Zc-2*Zb+Za) az= (±sqrt((Zc-2*Zb+Za)*Z-Za*Zc+Zb^2)+Zc-Zb)/(Zc-2*Zb+Za)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRzzQZC5plCreO5HXGw2V4ALUX_f11FewrHF1Wyf-tHA_WuL9dc0cXg4bnyRT7ksFj22o02rZnh6E3xzY5pPQ09sZhPUetmLJxS8YXzXt1r3H6zsjuXEg90nm5mNPYb3d_4OIZYBh36D-Y/s800/az.png)
Берём только те а, которые положительны, тогда "точность" попадания точки в шаблон, можно будет определять по тому, как точно совпадают эти три значения. Например можно оценивать это в относительных единицах, используя среднюю квадратическую сумму "коэффициентов похожести":
![Delta=sqrt((k1^2+k2^2+k3^2)/3) Delta=sqrt((k1^2+k2^2+k3^2)/3)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgRnHJI92EKcLrluo7Z5M3e8oP7jiErOZpI-jKbdR-EgWjpU8fw3ShcIf68_GjlIiBNEqujkBaEOcbnyYPQi2FAsxMl6ytNcC05OClSdaI6m6ANbPfBMGCBAVhyphenhyphen3VDY6zmAKhQSG6DvA23a/s800/De.png)
где "коэффициент похожести" определяется как:
![k1=ax/ay k1=ax/ay](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgC2o__PzAxQ-8Ccj4kMCIx-PWQBGCkIBDEmJ_SVwRGPzNbs5VYKYIKZiiWD-qc_2_TbfXaZfsspOIBDo851fQ7qcDcagIBmJ3zRBtCZ4nByDwFh9ayOVR5cwxm21ZXEZR06CZkQqpxbEYd/s800/k1.png)
![k2=ax/az k2=ax/az](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR5MWyyJba2mKRApPtG69XgEZyR15wVorS8mXtW83Z14TkgBNmN4i9s8JvBT7VIS0b4MbHlG0_zBhyRYKfM_J1hJOOMyQavaguMvyYbkFSNdu5wJvB28yoYpzdk7Fq9RSbdckknw_pN2pI/s800/k2.png)
(FIXME: yx should be ay)
Чем ближе полученное значение Δ к 1, тем точнее попадание.
Или, для ускорения обсчетов, можно рассчитывать среднее арифметическое:
![delta=(k1+k2+k3) delta=(k1+k2+k3)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_IbEePL-GXMfYf4Nc3Gnn4LetnTD7pclM4mlUo2ETF2DeOmguAsBswUik5E8v_dK3OXODLWPuuPMp6Cj1Zne63SDE5EHhDaHazD4mrG8zUjuuyCs-L1s7nn-AUvMfBclDN4pC_4YtpaiX/s800/d.png)
В итоге становится понятно, как определить степень попадания одной точки в область линии. А дальше идёт рутинная работа, вроде определения степени попадания каждой из точек, определения весового коэффициента для них (в простейшем случае — 1/N для каждой, однако при неравномерных расстояниях между точками такой подход уже не годится), и определение "общей" степени попадания набора точек в заданную кривую. При использовании шаблона сложенного из нескольких кривых Безье ситуация немного усложняется тем, что неизвестно с какого момента нужно сравнивать точки со следующей кривой.
В качестве альтернативы, из набора точек можно генерировать новую кривую Безье и пытаться сравнивать её уравнения с уравнением исходной кривой. Самый первый "недостаток" этого метода в том, что точки должны быть упорядочены. Кроме того, либо узлов в этой кривой будет столько же сколько было точек, либо "отрезков" кривых Безье будет примерно столько же (каждый из отрезков лежит между двумя соседними точками), а это может быть в разы больше чем количество кривых шаблона. И равномерность расстояний между точками проверяемой фигуры тоже начинает влиять на результат. Существуют алгоритмы упрощения кривых Безье, благодаря которым можно уменьшить количество полученных кривых, а также уменьшить влияние равномерности расстояний между точками. Я оценил работу одного из таких алгоритмов на примере буквы греческого алфавита гамма:
Статьи в интернете для лучшего понимания, что такое кривые Безье: статья c Gamedev, статья Википедии, интересная статья о упрощении кривых Безье с www.rsdn.ru (archived)
Задача: определить степень похожести проверяемой фигуры заданной набором точек и шаблона заданного кривой Безье.
Для начала рассмотрим очень упрощенно, и лишь для одного куска кривой Безье. Например для кривой Безье, заданной тремя контрольными точками A, B, C:
![X(a) = Xa*a^2 + Xb*2*a*b + Xc*b^2 X(a) = Xa*a^2 + Xb*2*a*b + Xc*b^2](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQjsIrdYldys9MzQSY4doqHSoWu0TXji7EWDMoyrP0ub-09GUsp3rmC6wbHwKcUOCjVih-5tFzMDjD1fCBc223c_TEdMEhBZuN-4k-ZGdyeV6kJ23EoVkWSpeQRjB6MmEqgTiKExhqGNiE/s800/Xa.png)
![Y(a) = Ya*a^2 + Yb*2*a*b + Yc*b^2 Y(a) = Ya*a^2 + Yb*2*a*b + Yc*b^2](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjFYOY7E5VQ1S75_vKaTbTYvytNtBwAA-R5Eb9k-8p1NG4lwN6bF3OTZpXtUIldxUs0z0t_W28q4k5QkCgLxGtvp_R2k0Y-bmR5RPyJqbv5LCjGFXBo2QopxvHBSvfsldmLmBJeau2xuw-V/s800/Ya.png)
![Z(a) = Za*a^2 + Zb*2*a*b + Zc*b^2 Z(a) = Za*a^2 + Zb*2*a*b + Zc*b^2](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5F95mgYEt6Sc4J3MbwaBC5uW9zy0WtQGU4StwyHaFKFm108NzFhrVU4OXvumAK70s2Z0LQ4257reow6tbI0BtEa7ili_pu6NOc1Dwrx3ItJZm3WNyZw-k60Zn-IGqa5lyAddql9_SNEiX/s800/Za.png)
![а = 0..1 а = 0..1](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiVJ3iqhi61qo4NOx76GEdqScjFRv79pgSBjRJ1MOcMDcJGOTDXAHcXuy6AZSQ-NpUGw5Frt2mhVnJ_uu6cZmUuBWu-sLybdjn6gWUkKvOdnYHaxtqBPfMU1MIGwShyphenhyphenTFhARNvvhiE9q8qT/s800/ae.png)
![b = 1-a b = 1-a](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0qlobmZ5TTfCiQqCFN-axU0bIXKTKA3Knc4m5ZDyb1JQtSorEf8OpGOB6ej6RNSnsn5t2DC8lcGkthZLn973C_2M7wUbC-fONlTZARExXKDwqz5MtKr9_VXi5xd0oM5REsZGEmYGi9aQm/s800/b.png)
XA, YA, ZA, XB, YB, ZB, XC, YC,ZC - координаты x, y, z исходных узлов A, B, C соответственно.
Тогда, если подставлять вместо X(a), Y(a), Z(a) координаты точки из проверяемой фигуры, можно находить для каждого уравнения значение коэффициента а:
![ax= (±sqrt((Xc-2*Xb+Xa)*X-Xa*Xc+Xb^2)+Xc-Xb)/(Xc-2*Xb+Xa) ax= (±sqrt((Xc-2*Xb+Xa)*X-Xa*Xc+Xb^2)+Xc-Xb)/(Xc-2*Xb+Xa)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh83VWLpqbxbtvzvRoF2pdYpj2l2RU277oQJAnKEixx5j7md-Z-yYTrW_xVFfA0BXxxlLf2sMeKgA55Ybuab-FJSPoJ00bRXTD_yci-E7CHoEkJ2RADqM7x6D5ygNE2he6UhRftQI9173Ln/s800/ax.png)
![ay= (±sqrt((Yc-2*Yb+Ya)*Y-Ya*Yc+Yb^2)+Yc-Yb)/(Yc-2*Yb+Ya) ay= (±sqrt((Yc-2*Yb+Ya)*Y-Ya*Yc+Yb^2)+Yc-Yb)/(Yc-2*Yb+Ya)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9xaabL3b3Ec5oF5v6dQReCFPn2Da_zBMU1wKJ0AqqwR-IQl07YtwKsMKkPCJ55e0wKIR5NPKc3S40rmNx_WbU6rOwJTyWMnQSTY25UeFPcN0gt1BPdcpFla34Jva_WgwnveKWiAdeJJ6c/s800/ay.png)
![az= (±sqrt((Zc-2*Zb+Za)*Z-Za*Zc+Zb^2)+Zc-Zb)/(Zc-2*Zb+Za) az= (±sqrt((Zc-2*Zb+Za)*Z-Za*Zc+Zb^2)+Zc-Zb)/(Zc-2*Zb+Za)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRzzQZC5plCreO5HXGw2V4ALUX_f11FewrHF1Wyf-tHA_WuL9dc0cXg4bnyRT7ksFj22o02rZnh6E3xzY5pPQ09sZhPUetmLJxS8YXzXt1r3H6zsjuXEg90nm5mNPYb3d_4OIZYBh36D-Y/s800/az.png)
Берём только те а, которые положительны, тогда "точность" попадания точки в шаблон, можно будет определять по тому, как точно совпадают эти три значения. Например можно оценивать это в относительных единицах, используя среднюю квадратическую сумму "коэффициентов похожести":
![Delta=sqrt((k1^2+k2^2+k3^2)/3) Delta=sqrt((k1^2+k2^2+k3^2)/3)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgRnHJI92EKcLrluo7Z5M3e8oP7jiErOZpI-jKbdR-EgWjpU8fw3ShcIf68_GjlIiBNEqujkBaEOcbnyYPQi2FAsxMl6ytNcC05OClSdaI6m6ANbPfBMGCBAVhyphenhyphen3VDY6zmAKhQSG6DvA23a/s800/De.png)
где "коэффициент похожести" определяется как:
![k1=ax/ay k1=ax/ay](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgC2o__PzAxQ-8Ccj4kMCIx-PWQBGCkIBDEmJ_SVwRGPzNbs5VYKYIKZiiWD-qc_2_TbfXaZfsspOIBDo851fQ7qcDcagIBmJ3zRBtCZ4nByDwFh9ayOVR5cwxm21ZXEZR06CZkQqpxbEYd/s800/k1.png)
![k2=ax/az k2=ax/az](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR5MWyyJba2mKRApPtG69XgEZyR15wVorS8mXtW83Z14TkgBNmN4i9s8JvBT7VIS0b4MbHlG0_zBhyRYKfM_J1hJOOMyQavaguMvyYbkFSNdu5wJvB28yoYpzdk7Fq9RSbdckknw_pN2pI/s800/k2.png)
![k3=ay/az k3=ay/az](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipCv1PIFBBn2rYG6SCvsJ8fYWY_txEdBO3y83z3Alu-84TetdN0uuS1aJuOdszx-7baE83bkHWue8ERGPByYkM_WJ7KrFVZACDQ_AOK9MgJhe-zl1vBzqiWA8klHo8D1rHcM7zoLUuRiDn/s800/k3.png)
Или, для ускорения обсчетов, можно рассчитывать среднее арифметическое:
![delta=(k1+k2+k3) delta=(k1+k2+k3)](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_IbEePL-GXMfYf4Nc3Gnn4LetnTD7pclM4mlUo2ETF2DeOmguAsBswUik5E8v_dK3OXODLWPuuPMp6Cj1Zne63SDE5EHhDaHazD4mrG8zUjuuyCs-L1s7nn-AUvMfBclDN4pC_4YtpaiX/s800/d.png)
В итоге становится понятно, как определить степень попадания одной точки в область линии. А дальше идёт рутинная работа, вроде определения степени попадания каждой из точек, определения весового коэффициента для них (в простейшем случае — 1/N для каждой, однако при неравномерных расстояниях между точками такой подход уже не годится), и определение "общей" степени попадания набора точек в заданную кривую. При использовании шаблона сложенного из нескольких кривых Безье ситуация немного усложняется тем, что неизвестно с какого момента нужно сравнивать точки со следующей кривой.
В качестве альтернативы, из набора точек можно генерировать новую кривую Безье и пытаться сравнивать её уравнения с уравнением исходной кривой. Самый первый "недостаток" этого метода в том, что точки должны быть упорядочены. Кроме того, либо узлов в этой кривой будет столько же сколько было точек, либо "отрезков" кривых Безье будет примерно столько же (каждый из отрезков лежит между двумя соседними точками), а это может быть в разы больше чем количество кривых шаблона. И равномерность расстояний между точками проверяемой фигуры тоже начинает влиять на результат. Существуют алгоритмы упрощения кривых Безье, благодаря которым можно уменьшить количество полученных кривых, а также уменьшить влияние равномерности расстояний между точками. Я оценил работу одного из таких алгоритмов на примере буквы греческого алфавита гамма:
- Вручную мне удалось изобразить её с помощью кривых Безье используя 6 узлов (2 кривые).
- Используя "аппроксимацию на глаз" прямыми отрезками было получено 40-70 узлов, которые, после "сглаживания", алгоритм упрощения из Inkscape уменьшал до 10-17 (медиана около 12).
Поэтому, несмотря на первоначальную привлекательность сравнивать с помощью генерирования новых кривых Безье или невозможно, или требует каких-то дополнительных преобразований, до которых я не дошел. Итого: я нашел только один способ которым, при доработке, можно сравнивать шаблон из кривых Безье с дискретным набором координат. Потенциальные особенности такого подхода:
- Может быть реализован так, что не будет зависеть от порядка точек в проверяемой фигуре и от равномерности/неравномерности расстояний между ними. Однако в этом случае "весомость" каждой точки придется считать одинаковой, либо хотя бы порядок должен быть известен.
- Чувствителен к преобразованиям массива точек (сдвиг, поворот, масштабирование)
- Может игнорировать целостность проверяемой фигуры. Например: все имеющиеся точки могут точно попадать в кривую, однако при этом покрывают лишь малую её часть, или не покрывают важные характерные изгибы. Может быть решено с помощью анализа того как рассчитанные значения коэффициента a покрывают диапазон 0 .. 1
- Может быть слишком чувствительным к некоторым аномалиям проверяемой фигуры (неравномерные расстояния между точками, "шум" и т.п.)
- Данный метод может быть неудобен, если надо сравнивать поочередно со многими шаблонами.
Возможно самый "простой" подход будет более эффективным: кривая Безье рендерится в растровое изображение, а затем сравнивается с набором точек используя один из "стандартных" алгоритмов сравнения изображений.
Статьи в интернете для лучшего понимания, что такое кривые Безье: статья c Gamedev, статья Википедии, интересная статья о упрощении кривых Безье с www.rsdn.ru (archived)