从一条线串中提取距离给定点最近的点的索引？

Question

让我们将一个线串视为点列表，我把它称为轨迹。我需要检测哪个点足够接近这条轨迹。我有另一个被称为感兴趣点的线串，我需要从轨迹线串返回最接近的索引点。我想提醒一下，这些感兴趣的点不包括在轨迹线串中，因此我将通过给定该感兴趣点来评估该轨迹中的索引点。结果的感兴趣点将获得存在于轨迹列表中的值。

[编辑]：

我将使用纯数字来转换此问题。我发现这很容易。

输入列表 [0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5]。 输入数字：3.30

我可以很容易地看到条件：list[n] < number < list[n+1] 然后我可以检查成本：

cost1 = number - list[n] cost2 = list[n+1] - number.

然后我可以获取N的索引，如果 (cost1 < cost2) return N else return N+1。

[重要提示]：

点对象不能作为数字进行比较，这使我陷入了盲区。

- LXSoft

---

这是一份作业抄袭吗？请先自己尝试解决问题，如果遇到困难再展示你已经尝试过的部分。 - Valentin Ruano

这不是一道作业题，我在对一条折线进行密度化后遇到了这个问题。因此我不知道如何获取离某点最近的索引。 - LXSoft

这太庞大了，我有一个包含约5000个点的JSON对象，以及一个感兴趣点的latang坐标： Linestring trail: [21.20569172506477, 45.74990849754149], [21.2057461355905, 45.749925475832626], [21.20580054611623, 45.74994245412377], [21.20585495664196, 45.74995943241491], [21.205909367167692, 45.749976410706054], [21.205963234865408, 45.750000273823495], [21.206017102563123, 45.75002413694094], ... 感兴趣点： "easyName": "Gara de Nord", "lng": 21.207498 "lat": 45.750287, - LXSoft

他想找到两个点之间的中间点，可能是索引，也可能是一种检测索引的算法。 - Alienware

@higuaro，我想要返回给我3445点的索引，针对给定的输入。 - LXSoft

Answer 1

如果您只需要执行一次，或者速度并不是很重要，且您的跟踪不倾向于回到自身，因此检测最接近的两个点可能与检测它们之间的线段不同，则这很容易。

首先，您需要一个点的距离平方公式（这代替了纯数字之差）：

 def dSq(x0: Double, y0: Double, x1: Double, y1: Double) =
   (x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0)

请注意，使用平方距离而不是距离本身并没有真正的优势，除了你需要计算额外的平方根。(但是可以放心地使用def d(...) = sqrt(dSq(...))代替。)

现在你需要找到从你的轨迹到目标点的距离：

 val ds = trace.map(p => dSq(target.x, target.y, p.x, p.y))

同时，您可以找到一组点之间的距离：

 val pairDs = ds.sliding(2).map(xx => xx(0) + xx(1))

你需要找到这些数中最小值的索引：

 val smallest = pairDs.min
 val index = pairDs.indexWhere(_ == smallest)

在您的原始列表中，这两个点是 index 和 index+1。

或者，您可以找到最接近的单个点，然后通过比较到那些点的距离来决定是否需要下一个或上一个。 （同样，请注意所有这些都是不精确的 - 要真正做到正确，您必须计算点到两个点之间线段的最接近点，这是一个更长的公式。）

如果您需要经常执行此操作，则需要一种更快的方法来忽略不相关的大距离。 一种常见的方法是在您的跟踪上放置网格，然后在每个网格元素内制作子跟踪。 然后，当给出感兴趣的点时，您首先查找其网格位置，然后在网格内部进行相同的搜索技巧。 （根据您如何裁剪网格内的点，您可能还需要搜索8个相邻的邻居。）

- Rex Kerr

---

这个程序可以正常工作，但是像你说的那样速度比较慢。我每2秒迭代一次列表中的5k~10k个点。但是你给我的例子很好用，非常感谢！ - LXSoft

你是说对于一个包含5k到10k个点的列表，与另一个列表比较需要2秒钟？听起来差不多对了；上面的例子中有很多的循环操作。如果你将逻辑转换为对数组进行while循环，速度会更快（而不需要使用网格技巧）。 - Rex Kerr