识别带有噪声的 3D 点网格中的 4 个连接点模式

Question

我在 3D 空间中有一组点，由以下 NumPy 数组表示：

import numpy as np
points = np.array([4.5403791090466825, -6.474122845743137, 1.720865155131852
                   4.544710813420152, -6.224218513611945, 1.7088861199877527
                   4.537233620491136, -5.98484530658863, 1.699488873354222
                   4.521937968342778, -5.721674150789189, 1.6849114580360904
                   4.4999241714099405, -5.4938430240669724, 1.679752942910385
                   4.830182546259025, -5.657936979701614, 1.6888307295378522
                   5.121468843368871, -5.803097135994744, 1.6954809688529893
                   5.439088364842268, -5.965512825953125, 1.6981638740242355
                   5.704276912211997, -6.100013441509505, 1.69575210534024
                   5.674604213881624, -6.316464211693753, 1.696360866592035
                   5.6375373276155125, -6.568875993817544, 1.7173100480278745
                   5.601324312047108, -6.791416283459123, 1.7222351265798983
                   5.556256817028301, -7.025669295257478, 1.7240530742321507
                   5.3173007670429975, -6.898939280431394, 1.7278595480033725
                   5.046628449981028, -6.753703318879904, 1.725804884872875
                   4.803244289601083, -6.620716409453152, 1.726377963879765
                   4.822340852273528, -6.379078541501187, 1.7032476446943
                   4.830532452723338, -6.144069893351172, 1.7047976672875338
                   4.834760563421453, -5.884305796074045, 1.6876475718597206
                   5.110719812888194, -6.028142616316405, 1.687525680260671
                   5.417740311618597, -6.184558989903391, 1.7124527178431916
                   5.385270875729216, -6.438008203433672, 1.712366908533943
                   5.355507693509876, -6.661093026054448, 1.729038450873722
                   5.07348022798482, -6.513010696655368, 1.726279452092121
                   5.090180621637709, -6.283446799878667, 1.7091940453643182])

这些点（及其标签）在 3D 空间中的绘图如下图所示。

在此图中，某些点用红色圈出，称为与感兴趣点的 4 个连接点。然而，我试图通过找到距兴趣点最近的 4 个点（欧几里得距离）来解决这个问题，但这种尝试并不在所有情况下都有效（用蓝色绘制的点）。

需要注意的是，3D点包含在平面或曲面中。然而，数据读数中存在噪声意味着虽然我们可以将点近似位于表面上或表面附近，但它们并不精确地位于表面之上。

此外，点网格有时会轻微变形，不会形成直线，如点云（原始数据）所示。

对于如何确定 3D 空间中的这 4 个连通点，您有什么建议吗？

Answer 1

解决该问题的第一种方法是执行降维，然后检索 4 个最近的点：

import matplotlib.pyplot as plt
import numpy as np
from sklearn.manifold import LocallyLinearEmbedding
from sklearn.neighbors import NearestNeighbors

points = np.array([[4.5403791090466825, -6.474122845743137, 1.720865155131852],
                   [4.544710813420152, -6.224218513611945, 1.7088861199877527],
                   [4.537233620491136, -5.98484530658863, 1.699488873354222],
                   [4.521937968342778, -5.721674150789189, 1.6849114580360904],
                   [4.4999241714099405, -5.4938430240669724, 1.679752942910385],
                   [4.830182546259025, -5.657936979701614, 1.6888307295378522],
                   [5.121468843368871, -5.803097135994744, 1.6954809688529893],
                   [5.439088364842268, -5.965512825953125, 1.6981638740242355],
                   [5.704276912211997, -6.100013441509505, 1.69575210534024],
                   [5.674604213881624, -6.316464211693753, 1.696360866592035],
                   [5.6375373276155125, -6.568875993817544, 1.7173100480278745],
                   [5.601324312047108, -6.791416283459123, 1.7222351265798983],
                   [5.556256817028301, -7.025669295257478, 1.7240530742321507],
                   [5.3173007670429975, -6.898939280431394, 1.7278595480033725],
                   [5.046628449981028, -6.753703318879904, 1.725804884872875],
                   [4.803244289601083, -6.620716409453152, 1.726377963879765],
                   [4.822340852273528, -6.379078541501187, 1.7032476446943],
                   [4.830532452723338, -6.144069893351172, 1.7047976672875338],
                   [4.834760563421453, -5.884305796074045, 1.6876475718597206],
                   [5.110719812888194, -6.028142616316405, 1.687525680260671],
                   [5.417740311618597, -6.184558989903391, 1.7124527178431916],
                   [5.385270875729216, -6.438008203433672, 1.712366908533943],
                   [5.355507693509876, -6.661093026054448, 1.729038450873722],
                   [5.07348022798482, -6.513010696655368, 1.726279452092121],
                   [5.090180621637709, -6.283446799878667, 1.7091940453643182]])


Xt = LocallyLinearEmbedding().fit_transform(points)
plt.scatter(Xt[:, 0], Xt[:, 1])
plt.show()

nn = NearestNeighbors().fit(Xt)
distance, index = nn.kneighbors(n_neighbors=4)
for k, ix in enumerate(index):
    plt.figure(figsize=(4, 4))
    plt.scatter(Xt[ix, 0], Xt[ix, 1])
    plt.scatter(Xt[k, 0], Xt[k, 1])
    plt.show()

这种方法不会产生完美的结果，特别是对于底层网格边缘的点。并且不会保证其他内部点。