Учитывая набор точек, как мне найти две точки, которые находятся дальше всего друг от друга? [Дубликат]

Question

  

Возможный дубликат:
   Набор 2-х точек с самым большим линейным измерением

Я мог бы вычислить расстояние между каждой точкой и взять наибольшую, но это не очень эффективный способ сделать это, когда есть большое (> 1000) количество точек.

Примечание. Это для iPhone, поэтому у меня нет тонны вычислительной мощности.

Answer 1

Вы просите вычислить диаметр набора. Стандартный метод состоит в том, чтобы сначала вычислить выпуклую оболочку, что сводит проблему к поиску диаметра выпуклого многоугольника. Даже в том случае, если вы не устраняете какие-либо моменты, эта дополнительная информация - именно то, что нужно для эффективного решения проблемы. Однако нахождение диаметра выпуклого многоугольника не совсем тривиально; несколько опубликованных работ с алгоритмами для этой задачи оказались неверными.

Вот довольно читабельное обсуждение правильного алгоритма O (n) для задачи (где n - количество точек в выпуклой оболочке).

Кроме того, обратите внимание, что iphone не ограничен ; Тщательно написанная реализация даже полностью наивного алгоритма может обрабатывать 1000 точек менее чем за одну десятую секунды. Конечно, использование правильного алгоритма позволит вам идти намного быстрее =)

Answer 2

Почему бы просто не вычислить выпуклый корпус из точек? В зависимости от используемого вами алгоритма , требуется O (n) или O (n log n) и исключает из рассмотрения все внутренние моменты. Затем проверьте только эти крайние точки, чтобы найти те, которые находятся дальше всего.

Answer 3

Начните с точки с самой низкой x-координатой. (Назовите это Пунктом X) Построить набор «граничных точек»;    начиная с точки x и вертикальной линии, проходящей через точку, других точек слева от PointX не должно быть) найдите следующую точку на границе, медленно поворачивая линию по часовой стрелке (или против часовой стрелки), пока линия не коснется какой-либо другой точки (см. ниже). ). Добавьте эту точку в набор и повторите с этой следующей точкой, чтобы получить следующую, пока в конечном итоге вы не вернетесь к исходной точке х. У вас есть множество точек, образующих границу полного набора. Сравните расстояние между каждой парой в этом уменьшенном наборе, чтобы найти самую дальнюю пару.

Чтобы "повернуть линию" (чтобы найти каждую последовательную граничную точку), выберите точку, которая является «самой дальней»; в направлении, перпендикулярном линии, используемой для последней граничной точки, и создайте новую линию между последней граничной точкой и той «следующей»; точка. Затем убедитесь, что в новом перпендикулярном направлении, образованном этой новой линией, нет других точек. Если нет других пунктов, «продолжай» в направлении, перпендикулярном этой или последней линии, это правильный выбор для следующей граничной точки, если такая точка существует, переключитесь на эту точку и повторите тестирование.

Answer 4

Смотрите эти страницы ( и ссылки на страницы, на которые можно перейти, нажав на ссылку «далее»), чтобы вычислить диаметр выпуклой оболочки набора точек.

Мое краткое резюме.

<Ол>

вычисляет множество точек в выпуклой оболочке (= O (n log n), O (n) можно получить только в том случае, если сначала отсортировать список, который в любом случае занимает O (n log n))

заказ вдоль границы (вы получаете это бесплатно, если вы используете сканирование Грэма для # 1)

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