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

Question

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

algorithmmathpathdistance

7

我有一个边界框和一些在其中的点。我想添加另一个点，它的位置与之前添加的点最远，并且离边框也很远。

对于这种情况是否有常见的解决方案？谢谢！

- Josh Santangelo

1

你能详细说明一下需求吗？离多远？你肯定不想在随机点上加1e6,1e6(,1e6)吧？另外，为什么要检查点和边缘？既然点在盒子里面，为什么不直接使用边缘呢？ - EboMike

这个问题很模糊。没有明确说明“远离盒子边缘”的距离是如何与“远离任何先前添加的点”的距离相比较的。你能写一个函数来最小化吗？ - lijie

@belisarius：这并不真正改变问题仍然非常模糊的事实。你的解释是将最小距离最大化到任何点/边缘。我的最初解释是将距离每个点和边缘的距离之和最大化（但这对边缘来说没有意义）。最好还是用数学形式编写一些客观函数以确保清晰度。 :) - lijie

@lijie 我并没有声称什么。这只是一种可能的解释，即远离其他点和边缘的最远距离。正如我上面所说的“一种方式”。这对于未定义的问题来说是一件好事：它们允许人与人之间的交互 :) - Dr. belisarius

@belisarius：是的，我同意 :) 我并没有声称你声称了什么；这就是为什么我使用了“解释”。问题陈述非常开放。 - lijie

显示剩余3条评论

2个回答

4

您要解决的问题名称为最大空心球问题。

在平面上，可以轻松地用O(n^4)的时间解决。只需考虑所有O(n^3)个点的三元组并计算它们的外接圆心。其中之一是您需要的点。（好吧，在您的情况下，您还必须将“一边”视为您的三个点之一，因此您不仅要找到外接圆心，还要找到略微更一般的点，例如两点和一边距离相等的点。）

正如上面的维基百科链接所示，也可以通过计算Voronoi图来在O(n log n)的时间内解决该问题。更具体地说，那么您需要的点是点集Delaunay三角剖分（Voronoi图的对偶）中的一个三角形的外心，其中只有O(n)个三角形。（同样，要完全适应您的问题，您还必须考虑盒子的边缘效应。）

- A. Rex

1

@A. Rex，我曾经发布并删除了一个基于沃罗诺伊图的答案，因为我无法推广到边缘。你能描述一下如何将沃罗诺伊D算法解决方案推广到边缘吗？ - Dr. belisarius

@belisarius：当然。最大半径可以来自Delaunay三角形的外接圆半径，或者来自凸包上的两个点和一条边，或者一个点和两条边，或者（如果没有点）正方形边长的一半。除第一种情况外，其他情况都可以通过解一些二次方程轻松实现。我很想看看你的Voronoi解决方案。我想发布一个完整的答案，但我不想编写Voronoi代码或查找C#库。 - A. Rex

@A. Rex 感谢您的回答。我对沃罗诺伊图方案并没有取得很大进展，因为我发现在 {0,16}x{0,16} 上存在像这样的配置 {{1, 15}, {15, 1}, {15, 15}, {1, 1}, {8, 8}}，它们的解决方案不容易与沃罗诺伊分解或德劳内三角剖分相关联（至少我是这么认为的）。但也许你是对的，值得深入探讨。顺便说一下，我关于它发布的所有内容都在我的答案的编辑历史记录中（虽然只是一个建议）。 - Dr. belisarius

那么，为了在一个盒子中（3D而不是平面）暴力解决这个问题，您是否考虑计算四个点的所有组合，并计算每个集合的外接球？然后我想您需要确保没有其他点在该球内。 - Nick

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dr. belisarius · Accepted Answer

这里是一个小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}中绘制它，我们会得到类似于：

alt text

因此，您需要一个好的数学包来找到最大值。

Mathematica是这样一个好的包，我们可以直接最大化它：

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

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

alt text

希望对你有所帮助！如果需要翻译成其他语言，请留言。

编辑

虽然我不是C#专业人士，但在Stack Overflow和谷歌上查找参考资料后，得出以下结论：

一个候选的包是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！