algorithm - 识别事件数

Question

我有很多条光线，所有光线的起点都在 3D 球体上，并且方向向量指向内部。一些光线指向 A 点，另一些光线指向 B 点等，并带有一些噪声(即光线在对应的 A 点、B 点等处没有完全相交)。

是否有一种算法可以让我确定有多少个点 A、B 等？或者更好的是，这些点位于何处？不知道A、B等点的位置，只知道射线的起点和方向向量。

例如，是一个示例设置，但在 2D 中，我不知道哪些光线指向哪个点(即我不知道哪些光线是红色或蓝色)。我如何找到他们指向的点数(在本例中为两个)或他们指向的点的位置？

我尝试了我的 earlier question 中建议的几种不同算法，但当点彼此靠近时，它们似乎都无法准确识别点的位置。我的首要任务是确定高精度的点数，即使它们靠得很近也是如此。即使我不得不牺牲位置的准确性，这是否可能？

编辑:如果我们让球体的半径为 1000 个单位，则方向向量的误差约为 10-20 个单位，而点之间的最小距离为目前工作的算法大约是 50 个单位。我不认为这似乎是无法克服的，但我很可能是错的。

Answer 1

我建议您将此视为点聚类问题的变化变体。

首先，做一组点。选择接近阈值:在您怀疑两条光线指的是同一点之前，两条光线应该有多近？对于满足此阈值的每一对光线，在它们最接近的线段的中点插入一个点。这是简单的(？)3D 线性代数。

现在，使用您最喜欢的聚类计数算法来确定您在这些点中拥有的聚类数量。您的接近阈值对于区分附近的点非常重要(请参阅我的评论)。

编辑:感谢您更新问题。与 10-20 单位误差相比，数据中 50 单位的间隔应允许您使用密度敏感聚类算法区分“近”质心。也许其中一种谱聚类方法可以为您完成这项工作。

您现在有“k”个已识别的集群。适配k-means聚类算法。

1. 选择每个簇的中点作为质心。
2. 删除您在上一次迭代中创建的所有“最接近”点。保持质心。
3. 确定每条光线所属的簇:您的距离函数是光线最接近每个质心的方法。
4. 在对每条光线进行分类时，将最接近质心的光线点添加到该聚类中。

重复步骤 1-4，直到您根据您拥有的任何 epsilon 标准收敛。质心是您的目标点(A、B 等)

• 如果您有任何异常值，请怀疑您缺少质心。
• 如果质心太近(根据您可以提取的任何接近度标准)，则合并它们。