|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Malashonok 2:4635/1024.64 15 Aug 2002 10:57:11
To : tim@kti.nsib.ru
Subject : Approximation
--------------------------------------------------------------------------------
Среда Авгyст 14 2002 18:33, ROman Ryabko -> tim@kti.nsib.ru:
t>> Есть проблема. Имеется набор точек (упорядоченный, т.е. ломанная)
t>> Hадо ее аппроксимировать набором дуг окружностей (не эллипсов) и
t>> прямых. Аппроксимировать гладко (в смысле непрерывности 1
t>> производной). Вопрос в том как сделать это оптимально и быстро
t>> ? Hаверняка есть готовые алгоритмы. --
Пусть имеется набор точек:
P1(x1, y1), P2(x2, y2), P3(x3, y3) ... Pn(xn, yn)
В общем случае задача сводится к поиску центра i-й окружности для i-го отрезка.
Считаем, что центр окружности N1 известен - т.е. задаем его сами, и далее
будем проводить дуги, соединяющие каждые две соседние точки так, чтобы (см.
рис.) радиус-вектор одной окружности был перпендикулярен не только своей
касательной, но и касательной к "следующей" дуге в точке стыка, т.е. чтобы
касательные совпадали.
Р1
o
o C1
o |
o |
o |
o | -> радиус-вектор
oo |
oo |
ooo |
...........oooР2...................
oo ^
o |
o касательная
Р3o
Общее уравнение касательной к окружности в точке (x0,y0) имеет вид:
(x-Cx)*(x0-Cx) + (y-Cy)*(y0-Cy) = R^2, где Сх, Су - координаты центра, R -
радиус.
запишем это в точке P2 для наших двух окружностей:
касат. N1: (x-Cx1)*(x2-Cx1) + (y-Cy1)*(y2-Cy1) = R1^2
касат. N2: (x-Cx2)*(x2-Cx2) + (y-Cy2)*(y2-Cy2) = R2^2
Раскрывая скобки получим:
x*(x2-Cx1) + y*(y2-Cy1) - Cx1*(x2-Cx1) - Cy1*(y2-Cy1) - R1^2 = 0
x*(x2-Cx2) + y*(y2-Cy2) - Cx2*(x2-Cx2) - Cy2*(y2-Cy2) - R2^2 = 0
запишем короче:
x*a1 + y*b1 + c1 = 0
x*a2 + y*b2 + c2 = 0
Условие "одинаковости" прямых:
a1/a2 = b1/b2 = c1/c2
получается системма, которую надо решить и найти Cx2, Cy2 и R2 (Cx1 и Cy1 -
изначально известны, R1 тоже). Вроде 3 ур-я, 3 неизвестных...
зы: напишешь, поделишься графической интерпритацией?
Alex
--- Советую стереть эту строку...
* Origin: 416C6578616E646572204D616C6173686F6E6F6B (2:4635/1024.64)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Approximation