1

我正在尝试解决一个问题，在给定大量线段的情况下，我必须尝试以最佳方式放置一个点，以使每条线到该点的总距离最小（即找到最佳位置）。点线距离可以从一条线上的任何位置到该点，也可以通过其他线段计算距离（比如有两条线，（0,0）到（0,1）和（1,0）到（1,1）我的观点是（2,0.5），我可以计算到第一行“通过”第二行的距离，我希望我足够清楚）。这些线都具有整数坐标作为端点，但该点可以位于平面上的任何位置。

我对此进行了很多思考，但无法提出一般策略。有人可以指点我一些阅读材料或为此解释算法吗？我在其他地方看到过类似的事情，所以这是某种一般性的问题吗？

谢谢。

4

2 回答 2

0

根据您的描述，最短线距离需要根据线段定义的区域单独讨论。例如，如果线段是 (0,0) 到 (0,1)，那么我们必须将空间分割成三个子空间（d 表示最小距离函数）：

  • y < 0: d = sqrt(x^2 + y^2)
  • 0 < y < 1：d = |x| （由该线段定义的区域）
  • 1 < y: d = sqrt(x^2 + (y-1)^2)

函数 d 具有凸属性，因此您可以通过运行一些标准的凸优化软件来解决优化问题，cvx 软件包是一个不错的选择。有关凸优化理论的更多信息，凸优化是一本值得参考的好书。

如果您不费心通过一些优化求解器来获得结果，那么基于启发式求解替代版本可能会简单得多。

请注意，如果线段在两端无限延伸，问题将是微不足道的。所以我能想到的是将线段视为线，但在端点处添加惩罚距离。话虽如此，以下指标满足需求：

L = [(ax + by - c)^2] + [(x-x1)^2 + (x-y1)^2] + [(x-x2)^2 + (y-y2)^2]

这里 (x, y) 是你需要决定的点，ax* + by* = c 定义线，(x1,y1), (x2,y2) 是两个端点。因此，第一项 [...] 是到线的平方距离；第二和第三 [...] 项是到两个端点的平方距离。

最小化 L 意味着：

  • 更喜欢依赖或靠近线；
  • 更喜欢驻留在段定义的区域中；

它属于最小二乘距离问题，因此您可以通过简单地求解一组线性方程来获得解决方案。这也是我在 L 中坚持二次形式的原因。

当然，这只是一种启发式方法，可以导致更简单的解决方案。就视觉认知而言，术语 L 的其他表述可能会导致更好的结果。您可以考虑使用不同的 L，然后根据视觉结果选择最佳的。

于 2012-06-28T15:57:58.170 回答
0

我有一个有效的算法，（我在谷歌上找到了它），它似乎很疯狂。有人可以解释一下为什么会这样吗？谢谢..

 To solve this, we start by placing the point at any random location and moving 
 it around in various directions, decreasing the amount that we move it by.To begin
 place the point at any location. Next move it in large increments (20) about
 10 times.Now we decrease the amount by which we move by an amount to 1/10;Running 
 the whole placement process about 5   times, decreasing the amount by
 which we move the power source each time, will give us the best location 
 for the point.
于 2012-06-29T00:38:44.380 回答