找到最适合n个球体交点的点 [英] Finding a point that best fits the intersection of n spheres

问题描述

我有一系列距离的点。我希望找到一个最能满足pointArray中的（point_i，distance_i）的条件：

 ：
 abs （point-point_i）= distance_i 
  

我认为这可以用某种回归或最小二乘法来解决，但我在解决问题时遇到了麻烦。

如果任何人都可以提供帮助，将不胜感激

解决方案

您需要定义best才能有一个可回答的问题。

您可能想要做的是定义一些从给定点出发多少错误函数很重要，然后尝试最小化错误总和。要使用的错误函数取决于您的实际问题。例如，也许你想使用（length（point - point_i） - distance） ² 。那将是最小的方格。但是，也许你不关心距离的绝对数量，只是他们距离的距离和你预期的距离之间的比例。所以你可以使用（length（point - point_i）/ distance - 1） ² 。也许你从一堆传感器获得点和距离。在这种情况下，使用适当的误差函数可以反映您测量距离时存在多少不确定性。

一旦您选择了适当的误差函数，您需要找到一种方法来优化它。最简单的方法是为你的误差函数计算一个梯度，并用它来追踪路径寻找算法到最低点。如果你的错误函数表现良好，这应该起作用，尽管不是那么快。如果你雄心勃勃，你可以使用多元Newton-Raphson方法来找到这一点。这对你的错误函数做了更多的假设，并且会有很多工作，但会更快收敛。

I have an array of points with distances. I wish to find a point that best satisfies the condition that

for (point_i, distance_i) in pointArray:
  abs(point - point_i) = distance_i

I think this could be solved with some kind of regression or least squares, but I'm having trouble with the problem formulation.

If anyone could help out, it would be greatly appreciated

解决方案

You need to define "best" to have an answerable question.

What you probably want to do is define some sort of error function for how much being off from a given point matters, and then try to minimize the sum of the errors. The error function to use depends on what your actual problem is. For instance perhaps you want to use (length(point - point_i) - distance)². That would be least squares. But perhaps you don't care so much about the absolute amount the distances are off, just the ratio between how far they are and how far you expected them to be. So you might use (length(point - point_i)/distance - 1)². Perhaps you get the points and distances from a bunch of sensors. In that case the appropriate error function to use reflects how much uncertainty there is in your measurement of the distance.

Once you have an appropriate error function chosen, you then need to find a way to optimize it. The simplest way to do that is to calculate a gradient for your error function, and use that to follow a path finding algorithm to the lowest point. If your error function is well behaved, this should work, though not that fast. If you're ambitious you can use the multivariate Newton-Raphson method to find that point. This makes more assumptions about your error function, and will be a lot of work, but will converge much faster.

这篇关于找到最适合n个球体交点的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！