Аппроксимация ломанной кривой используя дуги окружностей

Доброго времени суток.

Перехожу сразу к описанию поставленной задачи.
Существует множество точек, с координатами (х,у). При соединении всех точек последовательно, получается ломанная кривая.
Задача заключается в том, чтобы как можно точней заменить подмножества ломанных дугами окружностей. При этом количество дуг должно быть минимальным.

Ищу светлых умов для совместного обдумывания алгоритма. Есть такие?

P.S. На рисунке изображён пример. Чёрная линия - это ломоная. Оранжевая - совокупность дуг.

Изображения

 

0

Сообщение от helper При переборах по подмножествам можно даже параллелизм будет использовать.

Каким образом? Поясните пожалуйста.

Сообщение от helper этот алгоритм простейший.

Может и простейший, то с точки реализации - существует несколько проблемных моментов. К примеру, чтобы построить окружность нужно знать три точки, затем составляется система нелинейных уравнений. И вот решение данной системы - это первая загвоздка реализации.

0

Сообщение от manter Поясните пожалуйста.

Поиск решения для каждого из подмножеств не зависит от элементов каждого другого подмножества для этой задачи, поэтому можно параллельно обрабатывать каждое подмножество.

Сообщение от manter чтобы построить окружность нужно знать три точки

школьная математика.

Сообщение от manter затем составляется система нелинейных уравнени

Ну это как из пушки по воробьям. Можно намного проще - зная уравнение текущей окружности, просто считаем расстояние от её центра до каждой точки подмножества, и считаем, например, матожидание этих расстояний и насколько оно отличается от радиуса.

Извините, конечно, но у меня такое чувство, что Вы вот этими вот своими вопросами (ответы на которые достаточно очевидны для любого более-менее серьёзного программиста) всё же хотите, чтобы я разжевал Вам на 1-2-3 всю последовательность алгоритма. Знаете, в алгоритмах есть базисные вещи и понятия, не понимая которые лучше в такие задачи не лезть, просто очень напрягает по несколько раз затрагивать объяснение очевидных вещей, IMHO.

0

Сообщение от helper Извините, конечно, но у меня такое чувство, что Вы вот этими вот своими вопросами (ответы на которые достаточно очевидны для любого более-менее серьёзного программиста) всё же хотите, чтобы я разжевал Вам на 1-2-3 всю последовательность алгоритма. Знаете, в алгоритмах есть базисные вещи и понятия, не понимая которые лучше в такие задачи не лезть, просто очень напрягает по несколько раз затрагивать объяснение очевидных вещей, IMHO.

Считаю, что форум и придуман для того, чтобы обращаться за помощью к более знающим людям, когда возникают вопросы. Тем более раздел Алгоритмов.
Хорошая у вас позиция - не знаешь, не лезь. А вы как всему, что знаете, научились?
И

0

Сообщение от manter А вы как всему, что знаете, научились?

Самостоятельно, но не считаю, что в данном случае это имеет значение.
Право, есть базисные алгоритмы, лучше Вам начать с них.
Ничего личного, но иначе диалог не продвинется, я ж не могу разжёвывать всё "до байта".

0

Дорогой Сэр manter! Если вопрос еще актуален, посмотрите мой ответ Сэру ReasonX7 в ветви математика - геометрия.

Ваша задача даже ближе по условиям к тем, которые довелось решать когда-то мне. Не поленюсь повторить идею.
Идеология корреляционного анализа. Для Вас это даже не корреляция, а функция.

У Вас имеются наборы координат x, y на плоскости, которые предположительно принадлежат нескольким окружностям или их фрагментам.
Выбираете три произвольные точки из Вашего набора. И строите по ним окружность. Т.е. вычисляете ее центр X, Y и радиус R.
Накапливаете три гистограммы с X-ами, Y-ками и R-ами. Заносите полученные X, Y, R в эти гистограммы.
Берете следующую тройку вообще говоря случайных своих точек. Делаете то-же самое, и заносите новые X, Y и R в те же гистограммы. И так перебираете все ваши точки. Закономерно или случайно Вы их будете выбирать без разницы. Будете ли перебирать все комбинации, или остановитесь по достаточности - тоже зависит от Вас.
Если выбранные три точки принадлежат одной окружности ( фрагменту окружности ), то и в X и в Y и в R в Ваших гистограммах будет расти пик именно этой окружности.
Если точки принадлежат разным окружностям, то расчет по ним X, Y и R даст случайное значение и при занесении их в гистограмму они просто создадут фоновую подложку.
Точки взятые из другой окружности дадут свои X, Y и R и при занесении в гистограмму дадут еще один пик в X-ах, Y-ках и R-ах.
Соотношение высот пиков будет пропорционально обработанных Вами ( имеющихся у Вас ) точкам в каждой из Ваших окружностей. Ширины пиков дадут точность определения положения центров и радиусов.
Геометрическое положение окружностей друг относительно друга может быть любым.

Удачи!

Всегда Ваш - Etien.

0

Сообщение от helper Вопрос, а чем интерполяция сплайнами не подходит?

Вот, с самого начала был задан очень даже деловой вопрос... а ответа все нету.

0

Сообщение от MOHCTP Вот, с самого начала был задан очень даже деловой вопрос... а ответа все нету.

Ответ №4, 9.

Сообщение от manter Выходные данные должны содержать информацию о радиусе дуги.

Сообщение от Etien Не поленюсь повторить идею.

Спасибо за идею!

0

[IMAGE]http://i64.***********/big/2014/0826/76/26aa6b83c1ba56d4f549bfbe78cf9e76.png[/IMAGE]

Хз как тут картинку добавлять

Добавлено через 7 минут

Хз как тут картинку добавлять,

В общем углы можно сглаживать окружностями так чтобы:
1) окружность сглаживала каждый узел ломаной
2) отрезки ломаной были касательными к этой окружности
3) чтобы сглаживающие окружности не пересекались,

0

Сообщение от manter Выходные данные должны содержать информацию о радиусе дуги.

Вообще то дуга - кривая Безье второго порядка.

0