c++ - 通过凹多边形计算位置聚类中心约束的最快方法是什么

Question

我有一个加权 2D 姿态估计分布(位置 + 方向)，它们是系统姿态的未知 PDF 样本。所有估计和潜在的实际位置都受凹多边形的约束。

图片显示了一个示例性分布。洋红色圆圈是估计值，半径线表示估计方向。权重由圆直径表示。红点是加权均值，黄色圆圈表示方差和方向，但对以下问题不重要:

我想从所有估计中得出系统最可能的位置。

到目前为止，我已经评估了以下方法:

1. 使用权重最高的估计值:给出较差的结果，因为一个权重较高的估计值优于几个权重稍低的一致估计值。
2. 加权平均值:不适用，因为平均值可能位于多边形之外，如图所示(带黄色圆圈的红点)。
3. 加权中位数:会起作用，但会忽略潜在的聚类。例如。在下图中，两个集群很突出，其中一个比另一个更有可能。

此外，我还研究了 K-Means 和 K-Medoids。对于 K-Means，我不知道将中心约束到多边形的最有效方法。 K-Medoids 似乎有效，但性能不佳 (O(n^2))，这很重要，因为我有大量估计(与解释性图片相反)

• 解决此类问题的理想算法是什么？
• 可以实现什么复杂度？
• C++ 中是否有现成可用的算法来解决这个问题，或者可以很容易地进行调整以解决这个问题？

Answer 1

k-means 也可能在您的多边形之外产生估计值。 此类约束超出了集群用例。但没有什么能阻止您设计一种方法来事后更正估计值。

对于非凸数据，DBSCAN 可能值得一试。您甚至可以轻松地将视线合并到通用 DBSCAN 中。但我不相信集群将有助于实现您的总体目标。