У меня есть ограничивающая рамка и несколько точек внутри нее. Я хотел бы добавить еще одну точку, расположение которой находится дальше всего от любых ранее добавленных точек, а также далеко от краев прямоугольника.
Есть ли общее решение для такого рода вещей? Спасибо!
Вот небольшая программа Mathematica.
Хотя это всего две строки кода (!), вам, вероятно, понадобится больше на обычном языке, а также математическая библиотека, способная найти максимум функций.
Я предполагаю, что вы не владеете Mathematica, поэтому я объясню и прокомментирую построчно.
Сначала мы создаем таблицу с 10 случайными точками в {0,1}x{0,1} и называем ее p.
p = Table[{RandomReal[], RandomReal[]}, {10}];
Теперь мы создаем функцию для максимизации:
f[x_, y_] = Min[ x^2,
y^2,
(1 - x)^2,
(1 - y)^2,
((x - #[[1]])^2 + (y - #[[2]])^2) & /@ p];
Ха! Синтаксис стал хитрым! Давайте объясним:
Функция дает вам для любой точки в {0,1}x{0,1} минимальное расстояние от этой точки до нашего набора p И ребер. Первые четыре члена — это расстояния до краев, а последний (трудно читать, я знаю) — это множество, содержащее расстояния до всех точек.
Далее мы будем максимизировать эту функцию, чтобы получить ТОЧКУ, в которой минимальное расстояние до наших целей максимально.
Но сначала давайте посмотрим на f[]. Если вы посмотрите на это критически, вы увидите, что на самом деле это не расстояние, а расстояние в квадрате. Я определил это так, потому что таким образом функцию намного проще максимизировать, а результаты будут такими же.
Также обратите внимание, что f[] не является «красивой» функцией. Если мы построим это в {0,1}, мы получим что-то вроде:
Вот почему вам понадобится хороший математический пакет, чтобы найти максимум.
Mathematica — такой хороший пакет, что мы можем просто максимизировать его:
max = Maximize[{f[x, y], {0 <= x <= 1, 0 <= y <= 1}}, {x, y}];
И это все. Функция Maximize возвращает точку и квадрат расстояния до ее ближайшей границы/точки.
ХТХ! Если вам нужна помощь в переводе на другой язык, оставьте комментарий.
Изменить
Хотя я не человек С#, после поиска ссылок в SO и поиска в Google пришел к следующему:
Одним из пакетов-кандидатов является DotNumerics.
Вы должны следовать следующему примеру, представленному в пакете:
file: \DotNumerics Samples\Samples\Optimization.cs
Example header:
[Category("Constrained Minimization")]
[Title("Simplex method")]
[Description("The Nelder-Mead Simplex method. ")]
public void OptimizationSimplexConstrained()
ХТХ!
python реализацию этого
- person Hassan Baig; 18.05.2019
Задача, которую вы решаете, называется задача о самой большой пустой сфере.
Его можно легко решить за время O (n ^ 4) в плоскости. Просто рассмотрите все O(n^3) троек точек и вычислите их центр описанной окружности. Одна из этих точек является вашей желаемой точкой. (Ну, в вашем случае вы также должны рассматривать «сторону» как одну из ваших трех точек, поэтому вы не только найдете центры описанной окружности, но и немного более общие точки, например, равноудаленные от двух точек и стороны.)
Как видно из приведенной выше ссылки на Википедию, задача также может быть решена за время O(n log n) путем вычисления диаграммы Вороного. Более конкретно, тогда ваша желаемая точка является центром описанной окружности одного из треугольников в триангуляции Делоне ваших точек (которая является двойственной диаграмме Вороного), которых всего O (n). (Опять же, чтобы точно адаптироваться к вашей проблеме, вам придется учитывать влияние сторон коробки.)
