Возможный дубликат:
Двумерный набор наибольшего линейного измерения баллов
Я мог бы вычислить расстояние между каждой точкой и взять самое большое, но это не звучит как очень эффективный способ сделать это при большом (> 1000) количестве точек.
Примечание. Это для iPhone, поэтому у меня не так много вычислительной мощности.
Вы просите вычислить диаметр набора. Стандартный метод состоит в том, чтобы сначала вычислить выпуклую оболочку, что сводит задачу к нахождению диаметра выпуклого многоугольника. Даже в том случае, если вы не устраняете какие-либо точки, эта дополнительная информация - именно то, что необходимо для эффективного решения проблемы. Однако определение диаметра выпуклого многоугольника не совсем тривиально; несколько опубликованных статей с алгоритмами решения этой задачи оказались некорректными.
Вот довольно читаемое обсуждение правильного O (n) алгоритма для задачи (где n - количество точек в выпуклой оболочке).
Также обратите внимание, что iphone не это ограничено; Тщательно написанная реализация даже совершенно наивного алгоритма может обработать 1000 точек менее чем за десятую долю секунды. Конечно, использование правильного алгоритма позволит вам работать намного быстрее =)
Почему бы просто не вычислить выпуклую оболочку точек? В зависимости от используемого алгоритма, который вы используете, он требует O(n) или O(n log n) времени и устраняет все внутренние точки. из соображений. Затем проверяйте только эти крайние точки, чтобы найти две самые дальние.
O(log n), поэтому ожидаемое время работы для проверки этих точек O(log^2 n).
- person Jesse Beder; 25.10.2009
Начните с точки с наименьшей x-координатой. (Назовите это Точкой X) Постройте набор «граничных точек», начиная с точки x, и вертикальной линии, проходящей через точку. Не должно быть других точек слева от PointX) найдите следующую точку на границе, медленно вращая линию по часовой стрелке (Или против часовой стрелки), пока линия не коснется другой точки (см. ниже). Добавьте эту точку в набор и повторите с этой следующей точкой, чтобы получить следующую, пока вы в конечном итоге не вернетесь к исходной точке x. У вас npw есть набор точек, образующих границу полного набора. Сравните расстояние между каждой парой в этом сокращенном наборе, чтобы найти пару, которая находится дальше всего друг от друга.
Чтобы «повернуть линию» (чтобы найти каждую последующую граничную точку), возьмите точку, которая является «самой дальней» в направлении, перпендикулярном линии, использованной для последней граничной точки, и постройте новую линию между последней граничной точкой и этой точкой » следующий "пункт. Затем убедитесь, что в новом перпендикулярном направлении, образованном этой новой линией, нет других точек. Если в направлении, перпендикулярном этой или последней линии, нет других точек, «выходящих наружу», то это правильный выбор для следующей граничной точки, если такая точка есть, переключитесь на эту и повторите проверку.
См. эти страницы (та, на которую есть ссылки и страницы, на которые можно попасть, щелкнув ссылку «далее») при вычислении диаметра выпуклой оболочки набора точек.
Мое краткое резюме:
