当前位置：文江博客话题详情

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

发布于 2024-10-03 22:20:22 字数 86 浏览 1 评论 0原文

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

对于此类事情有通用的解决方案吗？谢谢！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

︶葆Ⅱㄣ 2024-10-10 22:20:22

这是一个 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} 中绘制它，我们会得到如下内容：

alt text

这就是为什么你需要一个很好的数学包找到最大值。

Mathematica 是一个非常好的软件包，我们可以直接最大化事情的结果：

max = Maximize[{f[x, y], {0 <= x <= 1, 0 <= y <= 1}}, {x, y}];

就是这样。 Maximize 函数返回点以及到其最近边界/点的平方距离。

alt text

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

编辑

虽然我不是 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()

HTH！

Here is a little Mathematica program.

Although it is only two lines of code (!) you'll probably need more in a conventional language, as well as a math library able to find maximum of functions.

I assume you are not fluent in Mathematica, so I'll explain and comment line by line.

First we create a table with 10 random points in {0,1}x{0,1}, and name it p.

p = Table[{RandomReal[], RandomReal[]}, {10}];

Now we create a function to maximize:

f[x_, y_] = Min[ x^2, 
                 y^2, 
                 (1 - x)^2, 
                 (1 -  y)^2, 
                 ((x - #[[1]])^2 + (y - #[[2]])^2) & /@ p];

Ha! Syntax got tricky! Let's explain:

The function gives you for any point in {0,1}x{0,1} the minimum distance from that point to our set p AND the edges. The first four terms are the distances to the edges and the last (difficult to read, I know) is a set containing the distance to all points.

What we will do next is maximizing this function, so we will get THE point where the minimum distance to our targets in maximal.

But first lets take a look at f[]. If you look at it critically, you'll see that it is not really the distance, but the distance squared. I defined it so, because that way the function is much easier to maximize and the results are the same.

Also note that f[] is not a "pretty" function. If we plot it in {0,1}, we get something like:

alt text

That's why you will need a nice math package to find the maximum.

Mathematica is such a nice package, that we can maximize the thing straightforward:

max = Maximize[{f[x, y], {0 <= x <= 1, 0 <= y <= 1}}, {x, y}];

And that is it. The Maximize function returns the point, and the squared distance to its nearest border/point.

alt text

HTH! If you need help translating to another language, leave a comment.

Edit

Although I'm not a C# person, after looking for references in SO and googling, came to this:

One candidate package is DotNumerics

You should follow the following example provided in the package:

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

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

HTH!

回复收藏 0 原文