Найти точку, которая максимально увеличивает общее расстояние от набора точек в ограниченной области

Question

Учитывая набор точек p, я хотел бы найти точку в пространстве b, которая ограничивает область p, которая максимально удалена от всех точек в пределах p.

Это касается реализации избегания соседей в симуляции стада согласно Боидам Крейга Рейнольдса - если это не лучший способ избежать соседей, я бы с удовольствием посоветовался.* РЕДАКТИРОВАТЬ: Другими словами, я хотел бы найти произвольную точку, которая находится как можно дальше от других точек в p, оставаясь в пределах ограничивающей рамки вокруг p.

Под ограничивающим квадратом я подразумеваю, что решением должна быть точка, имеющая координату y между верхней и нижней точками и координату x между левой и правой точками.

* 1016Чтобы сформулировать вопрос более абстрактно, я рассматриваю этот алгоритм как способ найти цель для агента, который хочет находиться в пределах M единиц от своих ближайших соседей, не приближаясь к m единицам из них.Решение, возвращаемое этим алгоритмом, должно возвращать точку, которая имеет наибольшее расстояние между ним и ближайшим соседом.

Это в 2D-плоскости.

Answer 1

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

Answer 2

Я думаю, что самая дальняя точка должна быть либо на границе бокса, либо на равном расстоянии между двумя ближайшими точками.Если это не так, то вы должны иметь возможность слегка сместить его, чтобы сделать его дальше от ближе к двум точкам.Это помещает это в линию диаграммы.Одно из направлений вдоль этой линии будет перемещать его дальше от обеих точек, так что вы можете перемещать его, пока эта линия не соединится с другой в точке.Поэтому я ожидаю, что он будет либо на границе, либо на одном из пересечений http://en.wikipedia.org/wiki/Voronoi_diagram.. Вы можете проверить углы границы, где линии диаграммы Вороного пересекают границу, и пересечениядиаграмма Вороного, чтобы найти самую дальнюю точку.Даже если вы не сделаете это таким образом, вы можете найти диаграмму Вороного полезной как способ поиска ближайших соседей для другого подхода - может работать некоторое разнообразие ветвей и границ.