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

Question

У меня есть заданная S точка (красная на графике) и n других точек (черная на графике). Я хочу найти точку P на расстоянии 1 от S , которая является самой удаленной из всех черных точек (в данном случае - сумма расстояний между P и каждая точка должна быть самой высокой).

Поскольку P равно 1 от S , мы можем сказать, что y = √(1 - x^2).

Аналитическим способом, которым я бы лично воспользовался, было бы:

1. Рассчитать сумму расстояний
   • Q - P = √((Qx - Sx - x)^2 + (Qy - Sy - √(1 - x^2))^2) (повтор всех n точек и суммирование),
2. Рассчитать производную полученного выражения,
3. Рассчитать корни производной и найти максимумы (в области),
4. Рассчитать значения на концах интервалов в домене,
5. Выберите правильный X.

Какой самый эффективный способ сделать это на Java и какие библиотеки можно использовать? Я слышал о библиотеках, позволяющих проводить эту аналитику, но это звучит сложно и медленно, поэтому я искал любые числовые идеи, но не мог их найти.

Answer 1

Следуйте по пути круга в МАЛЫХ инкрементах. Рассчитайте сумму расстояний для каждой точки на окружности. Найдите положение, где сумма расстояний максимальна. Готово. Математика достаточно для этого. Нет необходимости в дополнительных библиотеках. Посмотрите тригонометрию.

Угол сегмента SP - фи. Вы идете от 0 до 2 * пи (помните, что он использует радианы). Увеличьте фи с небольшим числом в вашей петле.

Что-то вроде:

• фи = 0,0;
• maxSumDistance = 0,0;
• phiAtMaxValue = 0.0;
• сделать цикл: phi изменяется от 0.0 до 2 * pi, добавляя небольшое число к phi каждый раз
• Внутри цикла: если (currentSumDistance> maxSumDistance), тогда maxSumDistance = currentSumDistance; а также phiAtMaxValue = текущее значение phi (переменная цикла);

В конце цикла у вас будет значение угла фи, где сумма расстояний была наибольшей. Затем вы пересчитываете координаты P из фи и расстояние SP.

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

Answer 2

РЕДАКТИРОВАТЬ : Алгоритм ниже не работает, как объяснено в комментариях.Я оставлю это здесь для справки.

Это может быть немного наивно, но как насчет:

• Найти среднее значение всех черных точек.Это может быть так же просто, как сумма (х-координата) / n и сумма (у-координата) / n.Эта «средняя» точка, скорее всего, НЕ будет на круге.Давайте назовем эту точку «A»
• Нарисуйте линию от этой средней точки в направлении S = ​​| AS |
• Продолжайте эту линию вдоль того же угла, пока не достигнете круга по другую сторону от S. Давайте назовем эту точку O (противоположной).Теперь у вас есть строка | ASO |.
• O можно рассчитать, потому что вы знаете, что радиус круга равен 1, и по определению эта точка является самой дальней точкой на красном круге от средней точки A, и отсюда она не следует за другой точкой накруг будет дальше от всех черных точек.

Угловой случай: если все черные точки симметричны относительно точки начала координат (например, одна точка в -2, -2 и одна точкана 2,2, тогда решение выше не будет иметь ответа, потому что A (средняя точка) будет равна S (начало 0,0). Вы можете сделать дополнительную проверку для A равным S, а затем выбросить исключение.

Answer 3

Прежде всего, кажется, что O (N ^ 2) не так уж и плох в худшем случае для этой проблемы. Потому что каждый вызов функции затрат стоит O (N). Рассмотрим следующую ситуацию: N черных точек, которые лежат на другом круге (R> 1, центр в S) и разбивают этот новый круг на N равных дуг. В этом симметричном случае мы имеем N максимумов. Просто чтобы проверить их, требуется O (N ^ 2) - вычислить функцию стоимости в каждой точке. Поэтому я думаю, что любой алгоритм, который проверяет все локальные экстремумы, будет иметь по крайней мере O (N ^ 2) в худшем случае.

Вот мой эскиз решения для общего случая:

• Если {Q_j} черные точки, давайте определим {O_j} так, чтобы каждый O_j был ближайшей точкой к Q_j, лежащему на красном круге вокруг S. Точки {O_j} разбивают круг на n дуг , Мы можем легко рассчитать каждую координату O_j.

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

• В целом, мы должны проверить O (NlogN) точек, каждая проверка стоит O (N). По крайней мере, этот метод более удобен, чем проверка каждой точки на окружности с небольшим эпсилоном.