Пусть на плоскости дано множество из n точек p i = ( x i , y i ) и нужно аппроксимировать его дугой окружности. Рассмотрим несколько подходов к решению этой задачи. В первом подходе координаты центра o = ( x, y ) и радиус r будем искать, как аргументы при которых функция
n
∑
( r 2 — ( x — x i ) 2 — ( y — y i ) 2 ) 2
(1)
i = 1
принимает минимальное значение. Сведём эту задачу к задаче наименьших квадратов. Для этого продифференцируем (1) по r и приравняем производную нулю. Отсюда получим выражение r 2 через x и y:
n
r 2 =
1
∑
( ( x — x i ) 2 + ( y — y i ) 2 )
(2)
i = 1
Подставим это выражение в (1) и приведём подобные члены. Получится задача наименьших квадратов:
n
∑
( 2 ( x i — x ) x + 2 ( y i — y ) y + xx — x i 2 + yy — y i 2 ) 2
(3)
i = 1
где
n
x =
1
∑
x i
i = 1
n
y =
1
∑
y i
i = 1
n
xx =
1
∑
x i 2
i = 1
n
yy =
1
∑
y i 2
i = 1
Следующая программа решает эту задачу:
Основное преимущество рассмотренной задачи — это простота решения, но более интересной для практики является минимизация другой функции отклонений:
n
∑
( | o — p i | 2 — r ) 2
(4)
i = 1
О векторных нормах смотрите здесь. Эту формулу можно переписать так:
n
∑
( c i * ( х — x i ) + s i * ( y — y i ) — r ) 2
(5)
i = 1
где
c i = ( х — x i ) / | o — p i | 2
s i = ( y — y i ) / | o — p i | 2
Если считать в формуле (5) переменные c i и s i известными, то приходим к классической задаче МНК. Отсюда получается следующий итерационный алгоритм: 1) Получаем начальное приближение для x, y и r при помощи функции getCirclePnt22. 2) Вычисляем значения c i и s i . 3) Решая задачу (5) получаем новые значения для x, y и r. Будем повторять шаги 2 и 3 пока алгоритм не сойдётся. В результате получаем программу:
В третьем подходе будем искать минимум суммы абсолютных разностей между радиусом окружности r и расстоянием от точки p i до центра окружности о:
n
∑
| | o — p i | 2 — r |
(6)
i = 1
Эту задачу можно решить перебором троек точек, построении по ним окружностей и выборе среди них оптимальной: Временная сложность такого алгоритма равна O ( n 4 ).
Замечу, что окружности построенными этими тремя алгоритмами могут очень сильно отличаться.
Описание шаблона классов CArrRef находится здесь. Описание шаблона классов Def находится здесь. Описание класса Vector2d находится здесь. Описание класса Circle2d находится здесь.
Динамическое программирование может применяться и для преобразования «цепочки» в проектную линию, состоящую из круговых кривых, сопрягаемых отрезками прямых. Это частный случай более общей задачи аппроксимации плоской кривой, заданной дискретно, кривой соответствующего вида, которая может и не быть графиком однозначной функции.
Такие задачи возникают при проектировании плана трассы. Неоднозначность аппроксимируемых функций создаёт дополнительные сложности.
Рассмотрим такую задачу, в которой элементами аппроксимирующей кривой являются дуги окружностей, сопрягаемые встык или отрезками прямых.
При этом должны быть выполнены следующие ограничения:
1. Отклонения проектной кривой от исходной в заданных точках не должны превосходить заданных величин. В частности, возможно задание фиксированных точек.
2. Кривизна аппроксимирующей кривой во всех точках по абсолютной величине не больше заданной.
3. Длины элементов не должны быть меньше заданных величин.
4. На границах элементы имеют общую касательную.
5. При проектировании продольного профиля дополнительно имеется ограничение по максимальному уклону.
Считаются заданными начальная и конечная точка искомой кривой, а также начальное и конечное направления.
Исходную кривую будем рассматривать как ломаную линию. В точках перелома построим нормали (по направлению к центру окружности, соединяющей три смежные точки). При необходимости нормали могут быть построены и в промежуточных точках (рис.8.8). При проектировании продольного профиля вместо нормалей рассматриваются ординаты.
Ограничения первого типа определяют область поиска, то есть крайние точки на каждой нормали. Эти точки задаются исходя из заданной ширины области поиска и дополнительно из условий проектирования (фиксированные и строго фиксированные точки).
Для каждой нормали задаётся угол у j с осью X и разбивается сетка с шагом А относительно исходной ломаной. Декартовы координаты узлов сетки на каждой нормали вычисляются по формулам
Рис. 8.8. Первый шаг алгоритма
где п/- номер i-ой точки на j -ой нормали ( нумерация начинается с нуля).
При проектировании продольного профиля все yj =я/2 и рассматривается обычная прямоугольная сетка варьирования.
Очередной этап динамического программирования — это переход к следующей нормали, но не к следующему элементу, число которых неизвестно; и к тому же в процессе построения аппроксимирующей кривой в одну точку могут приходить варианты, состоящие из различного числа элементов. Основное понятие в динамическом программировании: “состояние системы”- в данной задаче это точка на нормали и угол касательной к окружности в этой точке с осью X. Другими словами, задача рассматривается как двухпараметрическая. Начальное состояние точка А и угол а, конечное состояние точка В и угол р (рис.8.8) Рассмотрим сначала задачу, в которой допускается сопряжение дуг окружностей без прямых вставок.
Заданную минимальную длину элемента обозначим через Lmjn. Максимальную длину элемента Lmax примем равной 2Lmjn, так как элементы длиной больше, чем 2 Lmjn можно рассматривать как два различных элемента.
Первый шаг алгоритма динамического программирования. Для каждого положения точки D(xd,yd) первой нормали по её декартовым координатам, координатам точки А и углу а строится дуга окружности (рис.8.9).
Рис.8.9. Построение первого элемента
При этом сначала определяются координаты центра окружности хс, ус, а затем её радиус R.
R=AC; При ] на рис. 8.10. Тем самым “состояние системы ” то же, что и ранее (точка +угол), но углы не вычисляются, а назначаются с заданной дискретностью. Фактически изначально разбивается сетка не только по нормали с шагом А, но и по углам с шагом е.
По заданному начальному (хс,ус,ф|) и конечному состоянию (xa,yd, фД однозначно определяются все параметры связки: сначала вершина угла (координаты хь , уь точки В на рис. 8.10) и сам угол поворота со, затем длина ВС и радиус окружности R , затем длина дуги окружности LKp и длина отрезка прямой Ьл.
Приведенные формулы должны быть преобразованы, если cpi или ф j равны ± я/2.
Далее проверяется выполнение всех ограничений. Допустимые соединения оцениваются по критерию оптимальности и для каждой точки и угла в конце связки запоминаются точка и угол наилучшего начала. Задача остаётся двухпараметрической, но число вариантов и сложность оценки вариантов возрастают по сравнению с аппроксимацией только круговыми элементами.
Может показаться, что изложенные алгоритмы требует полного перебора всех возможных комбинаций углов при заданных точках начала и конца элемента при сопряжении встык или при построении связки. Однако это не так. Поскольку перебор упорядочен от меньших значений к большим, то при нарушении ограничений может быть выявлена бессмысленность дальнейшего увеличения варьируемого параметра, так как при этом невязка в ограничении увеличивается. В этом случае требуется перейти к следующему состоянию. Частный случай такой ситуации показан на рис. 8.11.
На рис. 8.11. точки С и D рассматриваются как концы очередной дуги окружности (при сопряжении окружностей встык). Прямая ВС соответствует углу касательной с осью X в точке С, при котором радиус окружности R принимает минимально допустимое значение.
Рис. 8.11. Прекращение перебора при нарушении ограничения
ну, аппроксимация круга многоугольником и история Пифагора могут быть хорошо известны. Но как насчет обратного пути?
У меня есть несколько полигонов, которые должны быть на самом деле круги. Однако из-за погрешностей измерений их нет. Итак, я ищу круг, который лучше всего «аппроксимирует» данный многоугольник.
на следующем рисунке мы видим два разных примера.
мой первый Анзац должен был найти максимальное расстояние точек до центра, а также минимальное. Круг, который мы ищем, может быть где-то посередине.
есть ли алгоритм для этой проблемы?
Видео:Что такое аппроксимация? Душкин объяснитСкачать
5 ответов
Я хотел бы использовать scipy чтобы лучше всего — «вписать» круг в мои точки. Вы можете получить начальную точку для центра и радиуса простым вычислением центра масс. Это хорошо работает, если точки равномерно распределены по окружности. Если их нет, как в приведенном ниже примере, это все равно лучше, чем ничего!
функция подгонки проста, потому что круг прост. Вам нужно только найти радиальное расстояние от вашего круга до ваших точек в качестве касательной (радиальной) поверхности всегда будет лучше всего подходит.
возможно, простым алгоритмом было бы сначала вычислить центроид точек (при условии, что они обычно расположены примерно равномерно). Это центр круга. После того, как у вас есть, что вы можете рассчитать средний радиус точек, давая радиус круга.
более сложным ответом может быть простая минимизация, где вы минимизируете сумму расстояний точек до края круга (или расстояние в квадрате).
существует два разных алгоритма O(n) для определения наименьшего круга, который вы рисуете, который охватывает ряд точек на странице Википедии задача наименьшего круга. Отсюда должно быть довольно легко нарисовать второй круг, просто определить центр круга, который вы нашли ранее, и найти точку, ближайшую к этой точке. Радиус второго круга таков.
Это может быть не совсем то, что вы хотите, но вот как я бы начал.
эта проблема может быть такой же, как задача наименьшего круга.
но поскольку у вас есть ошибки измерения, которые могут включать выбросы, то RANSAC-хороший вариант. См.http://cs.gmu.edu /
kosecka / cs482 / lect-fitting.pdf для обзора метода (а также других основных методов), в http://www.asl.ethz.ch/education/master/info-process-rob/Hough-Ransac.pdf больше информации предназначенной к кругу примерка.
довольно легко найти некоторое приближение:
объяснено: поместите центр круга в среднее значение x и среднее значение y ваших точек. Затем для каждой точки определите расстояние до центра и возьмите среднее значение по всем точкам. Это твой радиус.
Это полный скрипт:
производит этот заговор:
Это будет работать хорошо, так как у вас есть полигоны с ошибками измерения. Если ваши очки не приблизительно равномерно распределены по углам [0,2pi[ , он будет выполнять плохо.
![Как считали число пи? [Veritasium]](https://i.ytimg.com/vi/A3PL61fHzjs/0.jpg)
