Как восстановить окружность по массиву точек?

Question

[Burk7589]

Подскажите алгоритм для восстановления окружности по массиву точек и определение центра этой окружности и диаметра или радиуса.

Comments

[Wataru]

Для начала нужно определиться - окружность должна точно проходить через точки? Или, как на картинке, точки зашумлены?

Во втором случае возникает вопрос, а какая окружность будет для вас наилучшим приближением. Можно вводить разыне метрики ошибки. Например сумма квадратов разностей квадратов расстояний от центра до точек и квадрата радиуса. Или можно минимизировать максимальный такой квадрат разности.

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

Answer 1

[twobomb]

Ну как вариант, находим крайние точки: левую верхнюю, правую верхнюю, правую нижнюю и левую нижнюю.
В итоге получаем прямоугольник и вписываем окружность в этот прямоугольник

Comments

[Burk7589]

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

[twobomb]

Burk7589, Еще как вариант приходит в голову находим центр, тоесть берем точку с самым меньшим и самым большим x и у. Тоесть центр у нас xCenter = xMax - (xMax - xMin)/2, yCenter = yMax - (yMax - yMin)/2
Далее от этой точки, тоесть от центра собираем массив расстояния до каждой из точек, из этого массива находим точку до которой наибольшее расстояние и наименьшее расстояние берем среднее или среднее по массиву и это будет радиус нашей окружности

[Burk7589]

twobomb, xCenter, yCenter - это координаты центра восстанавливаемой окружности?

[twobomb]

Burk7589, да

[Burk7589]

twobomb, а как теперь при найденном радиусе и центре построить окружность?
Думал что вот так: x = r*cos(fi) , y = r*sin(fi). Но тут нужно знать угол.

[twobomb]

Burk7589, Всмысле как? Где построить и при чем тут угол? У вас есть радиус и центр все что нужно знать

[Burk7589]

twobomb, построить программно в qt c++. мне же нужно набрать точки чтобы построить окружность.

[Burk7589]

twobomb, я же могу таким образом в цикле меняя угол набрать массив точек для построения окружности?

[twobomb]

Burk7589, Жесть там что нельзя рисовать окружности? Ну если по точкам с определенным шагом то типа

for(float i = 0; i <= M_PI*2; i+= 0.1){
 cx = xCenter + cos(i) * radius;
 cy = yCenter + sin(i) * radius;
}

[twobomb]

Burk7589, Посмотрел вроде можно, есть метод drawEllipse, пример.
По идее нам нужно написать что-то типа

painter.drawEllipse(xCenter - radius, yCenter -radius, radius*2, radius*2);

[Burk7589]

twobomb, на тестовых данных нормально определяет центр окружности (рис.1), а на реальных нет (рис.2). В чем может быть причина?

[twobomb]

Burk7589, хех , это же очевидно, что нам нижнем рисунке нет ни одной точки слева и куча справа, но если центр синяя это синяя точка, то странно почему он там он должен быть выше примерно на отметке y - 25, а вот по иксу вроде бы правильно. Ну неважно, очевидно что окружность там будет примерно такой по моему алгоритму, в зависимости от алгоритма вычисления радиуса который вы сделали
А я так понимаю вы ожидаете нечто типа такого

Ну для такого нужен какой-то куда более сложный алгоритм, сразу так в голову ничего не приходит.
Вот если бы слева была бы хотя бы одна точка уже бы все было отлично.
P.S. Если все такие данные что точки только справа, можно написать костыль чтобы x смещался влево на (xMax-xMin)/2, тогда итог будет как на втором рисунке

[twobomb]

Burk7589, Еще один костыль в голову приходит, сравнивать разницу между (xMax-xMin) и (yMax-yMin) если эта разница больше допустим чем 75% на какой-то оси то смешаем по этой оси... вот только в какую сторону смещать это вопрос, тут нужно еще один костыль писать допустим брать условные центры сторон условного прямоугольника в который вписаны наши точки, получится 4 точки и проверять расстояние от каждого из центров до каждой точки и суммировать, получится 4 значения из них то которое наименьшее в ту сторону и делать смещение. Ну это такой колхоз что ну его, может быть если уже какие нибудь готовые алгоритмы предугадывания..

Answer 2

[dollar]

А как они распределены? Если равномерно, или хотя бы симметрично, то сначала ищем центр масс (среднее арифметическое всех координат по X и Y отдельно, ибо "массы" равны), а затем считаем среднее удаление точек от этого центра - это будет радиус. Центром и радиусом задаётся окружность.

Но если не равномерно и не симметрично, то сложно сказать. Например, такой случай:

spoiler

Comments

[Burk7589]

Точки распределены более менее равномерно. Где можно почитать про такой алгоритм дельнее?

[dollar]

Burk7589, в смысле? Я же его полностью расписал. Он же простой. Дальше нужно лишь перевести этот алгоритм на тот язык программирования, которым вы владеете. В любом случае я его только что сам придумал на ходу. Точнее, из всех, что пришли на ум, этот показался мне наиболее оптимальным. И не зная нюансов (где на практике решение будет применяться), не вижу смысла усложнять.

[Burk7589]

dollar, а как действовать в случае если точки не равномерно распределены по окружности?

[dollar]

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

Для лучшего понимания, сформулирую ту же мысль другими словами. Каков бы ни был в итоге ваш алгоритм, найдётся способ его обмануть, скормив ему исходные данные, на которых он сильно ошибётся. И чем проще алгоритм, тем сильнее можно его подставить.

[Burk7589]

dollar, набор точек части окружности, как на рисунке приходит от сенсора, и по ним нужно рассчитать центр и радиус восстановленной окружности.

[dollar]

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

В таком случае я бы предложил такой алгоритм (навскидку). Берём произвольные 3 точки и описываем вокруг них окружность. И так делаем 10000 раз. Многие окружности должны примерно совпадать. Смотрим, какие из них близки друг к другу и учитываем только их. Выбросы игнорируем. Где провести границу между "хорошей" окружностью и выбросом - решаете вы. Все хорошие окружности усредняем (координаты центра и радиус), и получается максимально точный прогноз.

Answer 3

[Армянское Радио]

Почитайте про преобразование Хафа для окружностей

Answer 4

[AnT]

Используйте алгоритм Эмо Велла (Emo Welzl) для построения минимальной охватывающей окружности

https://www.cyberforum.ru/geometry/thread1926478.h...
www.stsci.edu/~RAB/Backup%20Oct%2022%202011/f_3_Ca...

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

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

Comments

[Burk7589]

а какую проверку нужно делать чтобы при уменьшении окружности так чтобы количество точек внутри и снаружи стало примерно одинаковым.