问题标签 [closest-points]

Q) 在给定的一组点中找到最近的一对点。

预期时间复杂度：O(n log2(n)) / O(n log(n))

我正在从这里阅读这个问题。但是我无法理解一些事情：

1. 我们通过 Y 对已经按 X 排序的点进行排序来实现什么？

2. 当我们从其中一个半场中取一个点时，我们不会错过一些案例吗？即，如何取中点确保形成的条带包含所有候选点，其距离小于两个递归调用返回的距离？

3. 即使证明了上述点，我们是否应该取两半的中点，即左半边的m和右半边的(m+1)？

从多个来源，我了解到，在分而治之的最近对算法中，当找到特殊情况（不同一半的点对）时，您最多扫描任何给定点之前的 7 个索引。当我计算出来时，似乎你只能用 6 个甚至 5 个来逃脱。

如果您在绘制边长为 d（递归调用的最小值）的正方形的经典证明中，您只能在 2 个点之间放置 7 个点（或者可能是 6 个？），这意味着您只需要扫描 6 个（或5?) 提前点找到最小值。这是因为您可以“拟合 8 个点”的唯一方法是将点放在角落中，但这是不可能的，因为正方形共享角落，还因为如果您使边界严格（并且不小于或等于） ，也是不可能的。

不好意思说的不清楚，整件事要讲整整一堂课，我这里显然做不到。更清楚地说，有人可以给我一个满足条件的 8 个点的例子，并且最高点和最低点是不同的一半并且是最接近的吗？条件是同一半中的点对至少相距 d。

我正在尝试解决这个练习（幻灯片 40）。

我下载了kitchen-small数据集并执行了以下两个步骤。

第一步：将深度图像从数据集转换为点云。

第二步：执行GICP算法。

现在我希望，由于 GICP 收敛，可视化所有最终或变换的云，我将获得场景的完整重建。但这并没有发生，我得到了一个混乱的场景。

我错过了什么？

我没有得到gic.palign()方法产生的最终云的含义。它应该是相对于目标云对齐的输入云，即根据方法返回的矩阵变换的输入云gicp.getFinalTransformation()吗？

我有一个表面上有点的 3D 球体。这些点以球坐标表示，如方位角、仰角和 r。

例如，我的数据集是一个矩阵，其中包含给定球体上的所有可用点：

注意：我故意省略了完整的数据矩阵，因为它包含大量数据。如果需要/要求使问题完全可重现，我将提供完整数据。

该矩阵表示如下图像：

给定一个任意点，我想计算数据集中“包含”输入点的 3 个最近点。

到目前为止，我的代码如下：

基本上，我从矩阵数据集中的所有点中减去所请求的方位角和仰角self.sourcePositions（

代码工作正常，问题是有时我得到 3 个不包含请求点的最近点。

例子：

错误一：

好一个：

我该如何解决这个问题？我想获得“三角形”（我在球面上，所以它不是真正的三角形）包含我请求的点的 3 个最近点。

我需要使用两个单独表格中的几何图形找到最接近线任一端的点。到目前为止，我能够使用以下方法找到端点的几何形状：

使用它，我想用它ST_ClosestPoint来查找最接近管道端点的结构。到目前为止，这是我想出的：

但是，这会产生以下错误：

我在下面提供了一些示例数据。

sewers.pipes <-- 这些是行

sewers.structures <--这些是要点

我知道选择多个数据点可能会出现错误，例如。more than one row returned by a subquery used as an expression，所以这也可能是一个问题。任何帮助将不胜感激。

我遇到了以下问题，我无法找到一种方法来使用分而治之找到最近的配对距离，有人可以帮忙吗？

L 是 x 坐标为负的所有点之间的最近对距离，R 是 x 坐标为正的所有点之间的最近对距离。

假设至少有 2 个正点和 2 个负 x 坐标点。如果 L<R 并且在区间 (-L/2, R/2) 中没有任何点具有 x 坐标，那么最近对距离是多少？

我有两个数据框df1和df2.

我想找到df2与df1. 一旦从df2与 中的点对应的点中选择了一个点df1，将其从df2数据框中删除（以避免重复中的点df1）并移动到中的下一个点df1。

df1

df2

这个答案非常接近，但为了避免重复值的机会，如何返回最近点的索引以及点本身？

我的代码

但不知何故，这是行不通的

如何解决这个问题？请提出一些解决方案。

我们正在寻找一种有效的算法来解决以下问题：

给定两个越来越排序的数组。在每个数组中查找差异低于用户给定阈值的最接近的对应元素。array1[i] +/- threshold但只应返回最接近的可能候选者（在 的范围内）。第二个最接近的可以匹配到另一个元素，但不允许匹配多个元素。如果两个元素 与第一个（最左边）匹配array1的距离相同，array2[j]则应报告。

数组可以包含重复的值。应该报告第一个（最左边的）匹配项（并且所有其他匹配项都被忽略/不匹配）。

例子：

在比较质谱时，我们使用它来找到两个m/z值（质荷比）之间最接近的匹配值。

目前，我们遍历两个数组并预测下两个元素的差异，如果找到更接近的元素，则更正前一个元素。但这对于连续两个以上的重复元素失败（第二个示例）：

我们当前的实现（作为 R 包一部分的 C 代码）： https ://github.com/rformassspectrometry/MsCoreUtils/blob/master/src/closest.c#L73-L129

下面的评论版本：

有人可以给我们一个更好算法的提示吗？

谁能解释一下这两个函数的作用，以及它们每个函数的简化等效函数是什么？