algorithm - 如何找到距离给定集合及其边界框最远的点

Question

我有一个边界框，里面有很多点。我想添加另一个点，它的位置距离任何先前添加的点最远，并且距离框的边缘也最远。

这种事情有通用的解决方案吗？谢谢!

Answer 1

这里有点Mathematica程序。

虽然它只有两行代码 (!)，但您可能需要更多的常规语言以及能够找到最多函数的数学库。

我假设您不精通 Mathematica，所以我将逐行解释和评论。

首先我们在 {0,1}x{0,1} 中创建一个包含 10 个随机点的表，并将其命名为 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 函数返回点，以及到它最近的边界/点的平方距离。

喂!如果您需要帮助翻译成另一种语言，请发表评论。

编辑

虽然我不是 C# 的人，但在 SO 和谷歌搜索中寻找引用后，得出了这个:

一个候选包是DotNumerics

您应该遵循包中提供的以下示例:

 file: \DotNumerics Samples\Samples\Optimization.cs
 Example header:

  [Category("Constrained Minimization")]
  [Title("Simplex method")]
  [Description("The Nelder-Mead Simplex method. ")]
  public void OptimizationSimplexConstrained()

喂!