Как найти окружность минимального радиуса, охватывающую все заданные точки?

Предположим, у меня есть около 1000 нечетных точек на плоскости.

Затем, я думаю, можно было бы отбросить точки, которые никаким образом не влияют на радиус круга - точки, через которые выпуклая оболочка не проходит [с использованием одного из несколько алгоритмов]. Это оставляет нам точки, которые действительно имеют значение.

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

Я хочу обобщить это для эллипсов, как только пойму, как это можно сделать для кругов.

Была бы полезна любая ссылка на какой-нибудь "общедоступный исходный код", чтобы я мог изменить его для многоточия.


geometry plane convex-hull minimum-size
person Lazer    schedule 03.10.2009    source источник
comment
В статье Википедии, на которую вы ссылаетесь, упоминается метод вращающихся штангенциркулей для вычисления ширины и диаметра набора точек.   -  person jfs    schedule 03.10.2009

Ответы (2)


arrow_upward
2
arrow_downward

Одним из вариантов является Библиотека алгоритмов вычислительной геометрии CGAL. Это открытый исходный код, но он также большой - я подозреваю, что самая большая проблема, с которой вы столкнетесь, - это найти иголку в стоге сена.

Конечно (и это частично извинения перед Мартином), вы можете легко найти более сфокусированные варианты с помощью Google. Второй элемент списка выглядел нормально, когда я пытался, если вы не возражаете против Prolog, и на первой странице результатов был по крайней мере один пример C и один Javascript. И вряд ли вы можете больше утверждать, что не знаете слов для Google.

person Steve314    schedule 04.10.2009
comment
@Steve спасибо за отличную ссылку. На самом деле я нашел то, что мне нужно, но не могу скомпилировать пример кода по адресу cgal.org/Manual/3.5/examples/Min_circle_2/min_circle_2.cpp Я получаю следующее: imgur.com/h9TYC.jpg как вы можете видеть, я поместил код прямо в каталог include, чтобы он мог найти заголовки (он давал такие же ошибки и в других местах). Что я делаю не так? - person Lazer; 05.10.2009
comment
@eSKay - извините, я мало что знаю о CGAL. Я узнал об этом из просмотра части youtube.com/watch?v=3DLfkWWw_Tg. - нашел в поиске материал по вычислительной геометрии - и все. - person Steve314; 05.10.2009

arrow_upward
4
arrow_downward

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

person Martin v. Löwis    schedule 03.10.2009
comment
Разве незнание правильных слов для Google не является одной из причин возникновения переполнения стека? - person Steve314; 03.10.2009
comment
Кто-нибудь знает какую-то реализацию (я имею в виду код), на которую я могу сослаться? - person Lazer; 03.10.2009
comment
Взгляните на этот вопрос: that-contains-thes/14979145#14979145" title="данные n точек в трехмерном пространстве, как найти наименьшую сферу, содержащую их"> stackoverflow.com/questions/2395178/ - person Hbf; 21.02.2013