Я объясню, как бы я подошел к проблеме. Я бы предложил подход к восхождению на холм. Сначала вычислите центр тяжести точек в качестве начальной точки и определенным образом выберите два значения для a и b (возможно, подойдут произвольные положительные значения). Вам нужна функция подбора, и я бы посоветовал ей вернуть количество точек (достаточно близко), лежащих на данном эллипсе:
int fit(x, y, a, b)
int res := 0
for point in points
if point_almost_on_ellipse(x, y, a, b, point)
res = res + 1
end_if
end_for
return res
Теперь начнем с некоторого step. Я бы выбрал достаточно большое значение, чтобы быть уверенным, что лучший центр эллипса никогда не будет дальше, чем step от первой точки. Выбирать такое большое значение необязательно, но самая медленная часть алгоритма - это время, которое требуется, чтобы приблизиться к лучшему центру, поэтому большее значение, я думаю, лучше.
Итак, теперь у нас есть некоторая начальная точка ( x , y ), некоторые начальные значения a и b и начальная шаг . Алгоритм итеративно выбирает лучшего из соседей текущей точки, если есть какой-либо соседний лучше, чем он, или уменьшает шаг в два раза в противном случае. Здесь под «лучшим» я подразумеваю использование функции подгонки. А также позиция определяется четырьмя значениями (x, y, a, b) и ее соседями являются 8: (x + -шаг, y, a, b), (x, y + -шаг, a, b), (x , y, a + -шаг, b), (x, y, a, b + -шаг) (если результаты не достаточно хороши, вы можете добавить больше соседей, также перейдя по диагонали - например (x + -step, y + -step, а, б) и так далее). Вот как ты это делаешь
neighbours = [[-1, 0, 0, 0], [1, 0, 0, 0], [0, -1, 0, 0], [0, 1, 0, 0],
[0, 0, -1, 0], [0, 0, 1, 0], [0, 0, 0, -1], [0, 0, 0, 1]]
iterate (cx, cy, ca, cb, step)
current_fit = fit(cx, cy, ca, cb)
best_neighbour = []
best_fit = current_fit
for neighbour in neighbours
tx = cx + neighbour[0]*step
ty = cx + neighbour[1]*step
ta = ca + neighbour[2]*step
tb = cb + neighbour[3]*step
tfit = fit(tx, ty, ta, tb)
if (tfit > best_fit)
best_fit = tfit
best_neighbour = [tx,ty,ta,tb]
endif
end_for
if best_neighbour.size == 4
cx := best_neighbour[0]
cy := best_neighbour[1]
ca := best_neighbour[2]
cb := best_neighbour[3]
else
step = step * 0.5
end_if
И вы продолжаете итерацию, пока значение шага не станет меньше заданного порога (например, 1e-6). Я написал все в псевдокоде, так как я не уверен, какой язык вы хотите использовать.
Не гарантируется, что найденный таким образом ответ будет оптимальным, но я почти уверен, что это будет достаточно хорошее приближение.
Вот статья о восхождении на гору .