Наименьший замкнутый круг в Python, ошибка в коде

У меня есть набор точек, представляющих вершины (x, y) многоугольника.

Мне нужно найти наименьший круг окружения (площадь, х и у центра и радиуса)

когда я запускаю код, результаты меняются каждый раз, например:

с использованием коммерческого программного обеспечения (то есть ArcGiS) в некоторой точке точек правильный результат:

Ответы

Ответ 1

Не понимая ничего о вашем алгоритме, я заметил одно: соотношение между вашими координатами и вашим радиусом очень велико, около 2e5. Возможно, ваш алгоритм плохо обусловлен, пытаясь найти круг вокруг точек, которые находятся так далеко от начала координат. Особенно в вашей функции _make_circumcircle это приводит к вычитанию больших чисел, что, как правило, плохо для численных ошибок.

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

def numerical_stable_circle(points):
    pts = np.array(points)
    mean_pts = np.mean(pts, 0)
    print 'mean of points:', mean_pts
    pts -= mean_pts  # translate towards origin
    result = make_circle(pts)
    print 'result without mean:', result
    print 'result with mean:', (result[0] + mean_pts[0], 
    result[1] + mean_pts[1], result[2])

Результат:

mean of points: [  421645.83745955  4596388.99204294]
result without mean: (0.9080813432488977, 0.8327111343034483, 24.323287017466253)
result with mean: (421646.74554089626, 4596389.8247540779, 24.323287017466253)

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

Ответ 2

Я являюсь автором самой маленькой реализации окружного круга, которую вы использовали. Примите мои извинения за неисправный код и ответ на 2 года.

В текущей версии библиотеки исправлена проблема, с которой вы столкнулись. Обновите свою копию до последней версии, и я заверяю вас, что алгоритм генерирует стабильные и нормальные результаты для численного случая, который вы дали.

Другой пользователь пришел ко мне с аналогичной проблемой , где алгоритм выводит совершенно разные круги в зависимости от того, как список точек рандомизирован, Его входные данные имеют сходную характеристику - изменение чисел меньше, чем величина чисел; например, 10,000001 против 10,000002. Мне удалось полностью отладить его тестовый пример, потому что он содержал только 5 очков, тогда как у вас 32.

Основная причина заключается в том, что _make_circle() и _make_circumcircle() слепо вычисляют радиус, который является математически корректным, но не учитывают искажения при округлении координат центральной точки. Правильный способ - вычислить центральную точку предлагаемого круга, а затем рассчитать радиус, основанный на максимальном расстоянии от каждой окружной точки от центра.

Например, предположим, что мы хотим найти круг, который охватывает (1,0) и (6,0), но каждая точка округляется до целого числа. Разумеется, истинный круг (3,5, 0, 2,5). Мы вычисляем центр x как (1 + 6) ÷ 2 = 3,5 → 4 (с округлением до половины). Если мы вычисляем радиус отдельно и слепо, то это расстояние между 1 и 6, разделенное на 2, которое равно (6-1) ÷ 2 = 2,5 → 2 (округление до половины равно). Но если вычислить расстояние от искаженного центра (4,0) до (1,0) и (6,0), то мы увидим, что нам действительно нужен радиус 3. Когда радиус окружности слишком мал, он не будет содержать точек, которые он должен был содержать по дизайну, и поэтому алгоритм запутывается и пытается подсчитать новые круги на основе сомнительных данных с сомнительными способами.