Approximation

From

Alex Malashonok (2:4635/1024.64)

To

tim@kti.nsib.ru

Date

2002-08-15T10:57:11Z

Area

RU.ALGORITHMS

Привет tim@kti.nsib.ru!

Среда Авгyст 14 2002 18:33, ROman Ryabko -> tim@kti.nsib.ru:

 t>> Есть проблема. Имеется набор точек (упорядоченный, т.е. ломанная)
 t>> Надо ее аппроксимировать набором дуг окружностей (не эллипсов) и
 t>> прямых. Аппроксимировать гладко (в смысле непрерывности 1
 t>> производной). Вопрос в том как сделать это оптимально и быстро
 t>> ? Наверняка есть готовые алгоритмы. --
Пусть имеется набор точек:
  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)