Учитывая ряд точек, как я нахожу две точки, которые являются самыми дальними друг от друга? [дубликат]
Пользовательский интерфейс Yahoo (YUI) имеет CSS Сброс реализация, которая стремится сформировать общую базовую линию через все браузеры. Это должно получить Вас достаточно близкий.
4 ответа
Вы просите вычислить диаметр набора. Стандартный метод состоит в том, чтобы сначала вычислить выпуклую оболочку, что сводит задачу к нахождению диаметра выпуклого многоугольника. Даже в том случае, если вы не устраняете никаких точек, эта дополнительная информация - именно то, что необходимо для эффективного решения проблемы. Однако определение диаметра выпуклого многоугольника не совсем тривиально; несколько опубликованных статей с алгоритмами для этой задачи оказались неверными.
Вот довольно читаемое обсуждение правильного O (n) алгоритма для задачи (где n - количество точек в выпуклом
Также обратите внимание, что iphone не , который ограничен; Тщательно написанная реализация даже совершенно наивного алгоритма может обработать 1000 точек менее чем за десятую долю секунды. Конечно, использование правильного алгоритма позволит вам работать намного быстрее =)
Начать с точки с наименьшей x-координатой. (Назовите это точкой X) Построить множество «граничных точек» начиная с точки x и вертикальной линии через точку, слева от PointX не должно быть других точек) найдите следующую точку на границе, медленно вращая линию по часовой стрелке (или против часовой стрелки), пока линия не коснется какой-либо другой точки (см. ниже ). Добавьте эту точку в набор и повторите с этой следующей точкой, чтобы получить следующую, пока вы в конечном итоге не вернетесь к исходной точке x. У вас npw есть набор точек, образующих границу полного набора. Сравните расстояние между каждой парой в этом сокращенном наборе, чтобы найти пару, которая находится дальше всего друг от друга.
Чтобы «повернуть линию» (чтобы найти каждую последовательную граничную точку), возьмите точку, которая является «самой дальней» в направлении, перпендикулярном линии, используемой для последней граничной точки, и постройте новую линию между последней граничной точкой. и эта «следующая» точка. Затем убедитесь, что в новом перпендикулярном направлении, образованном этой новой линией, нет других точек. Если в направлении, перпендикулярном этой или последней линии, нет других точек, «выходящих наружу», то это правильный выбор для следующей граничной точки, если такая точка есть, переключитесь на эту и повторите проверку.
Почему бы просто не вычислить выпуклую оболочку точек? В зависимости от используемого алгоритма , он занимает либо O (n) , либо O (n log n) времени и исключает все внутренние точки из рассмотрения. Затем проверяйте только эти крайние точки, чтобы найти две самые дальние.
См. эти страницы (страница, на которую есть ссылка, и страницы, доступные при нажатии на ссылки «далее») по вычислению диаметра выпуклой оболочки набора точек. .
Краткое резюме:
- вычислить набор точек в выпуклой оболочке (= O (n log n), единственный раз, когда вы получите O (n), это если вы сначала отсортируете список, который займет O (n log n) ) в любом случае)
- порядок вдоль границы (вы получаете это бесплатно, если используете сканирование Грэма для № 1)
- используйте один из алгоритмов диаметра O (n) для сканирования на предмет противоположных точек с наибольший диаметр. Алгоритм Шамоса мне нравится, поскольку это один из алгоритмов вращающихся суппортов .