刚体几何中位数

我需要实现一个适用于刚体的“几何中值”型算法，这意味着它不仅可以找到一个最小化距离一组点的距离的点，而且还会考虑到身体的方向。我还没有找到解决这类问题的办法，而对于几何中位数（或韦伯或费马托里利问题或设施位置问题），有很多信息可用，包括Weiszfeld算法（和现代改进）。我希望有人会提及可能的解决方案。我会认为这是一个相对常见的问题在注册，但也许我只是没有找到合适的词搜索...刚体几何中位数

我的问题可以公式化如下：说我有一个“参考”刚体与3个非共线点（一个三角形），我测量了3次点的坐标（有一些错误，或者物体移动了一点）。我想找到一个好的“中心位置”，这样可以最小化每个测量点与其相应的中心位置对象点之间的距离总和（非平方距离）。这相当于“多设施选址问题”，但是“设施”之间的固定距离有额外的限制，并且每个点预先分配给一个设施（不一定是最近的一个）。

实际上，我在考虑不是最小化所有点的总和，而只是为每次测量保留3点的最大距离。（那就是所谓的“极大极小”？）但我认为这不会对我必须使用的算法类型产生很大的影响。

与几何中位数相比，一个可能的困难可能是随着旋转的自由度增加，要最小化的量不再是凸的（不是100％确定，但我认为）。我希望我仍然可以使用与Weiszfeld（这是次梯度方法）类似的算法，并且希望以前已经对此进行了调查。谢谢你的帮助！

P.S.我将在Matlab中完成这项工作。

来源

2012-06-08 zorgkang

我不知道这是否有帮助，但可以看看“Graphics Gems IV”这本书吗？有一个名为“多边形的质心”的宝石（第1章，第3页）作者描述了一种使用基本力学来找出多边形质心的方法。如果你无法在物理上访问该书，请在谷歌图书上在线查看 – higuaro

谢谢，虽然（最小平方和不涉及旋转），但这是一个完全不同的问题。我可以想到一个足够简单的方法来直接计算，不需要迭代优化算法。为了澄清，我不是在寻找一个身体内的一个点，而是一个身体的中心位置和方向，与其他许多副本相比。 – zorgkang

我在这个问题上找不到任何研究。我要做的第一件事就是使用没有刚度约束的Weiszfeld算法来找到各个点的几何中值，定义对应于对象边缘与期望值偏差的拉格朗日乘子，并使用梯度下降找到约束局部最小值。我无法证明它始终有效，但直观地说，只要偏差足够小，就应该这样做。

来源

2012-06-08 22:56:35 user434507

如果你做第二部分的数字（我认为你必须），请记住这个http://en.wikipedia.org/wiki/Lagrange_multiplier#Example：numerical_optimization – user434507

谢谢，我碰到过这个（拉格朗日倍增维基）本周。如果我这样做，请记住好的事情。 – zorgkang

刚体几何中位数

回答

相关问题