python - 在 3D 数据中寻找多条路径

Question

问题

我有一组分散的数据点的 3d 集。我正在寻找尽可能多的路径来寻找满足几个约束条件的方法。

1. 从一点到另一点应该通过最近的邻居发生，即我想保持路径点之间的距离最小。
2. 路径可以共享点，但我也想保持最少的共享。
3. 散乱数据中有一个平面，我希望所有路径都从该平面开始。它们结束的位置并不重要，但我希望路径的总体方向远离平面，因此路径应该只包含平面的一个点。
4. 所有点都应该是至少一条路径的成员。

方法

scikit 中的 NearestNeighbors 似乎适合生成可以逐点查询最近邻居的树。

Q1:我如何包含一个加权方案，该方案将采用欧几里德意义上的接近度和从 $p_{n}$ 到 $p_ 的路径向量意义上的接近度{n+1}$ 与平面的法向量接近平行？这是为了优先考虑将导致路径远离平面的点。我知道我将用来测试向量的接近度的计算，但不知道如何将结果与欧几里得距离一起包含在权重中。

问题 2: 是否有一种简单的方法可以使 $p_{0}$ 始终位于平面内？

基本算法

1. 对所有点进行编号，并根据点编号组成一组。
2. 使用上述加权标准生成路径。
3. 从编号的点集中删除路径中的点。
4. 如果一条路径没有从集合中移除至少一个编号点，则丢弃该路径。
5. 重复 2 - 4 直到编号组为空。

对这个想法有什么想法吗？

Answer 1

这听起来像是图算法案例。

似乎解决它的方法是创建一个有向图，其中节点是您拥有的点，对于每个节点，取 M 个最近的(选择您自己的)邻居并从该节点创建一条边到边的权重应该是您所有偏好的组合的邻居。

例如权重可以是:

   || Vi-Vj ||^2 * k
w=-----------------
      (Vj-Vi)N

其中Vi是当前节点，Vj是下一个节点。 k 是最近邻列表中的顺序(从 1 开始)。 N为平面法线。

思路是高欧几里德距离加罚分，不是最近的节点也加罚分，如果方向不垂直于平面，分母中的点积加罚分。

显然，这只是一个示例，应该根据您的需要进行调整。

当您有一个现成的图时，您可以在其上运行路径查找算法(例如 Dijkstra、Floyd 等)

当您选择一条路径，并希望影响下一条路径的选择时，您可以获取所有使用过的节点，并增加通向这些节点的所有边的权重。