找到到相邻点的平均距离的算法？

Question

给定一组点，我需要能够知道每个点到其他相邻点的平均距离是多少。

我的直觉只是设置一个半径，将点定义为邻居，然后取从目标点到半径内所有其他点的所有距离的平均值。然而，还有一个额外的要求：只应考虑给定方向上最近的点。意思是，如果半径距离内有两个点，并且两个点都在相对于目标点的 30 度范围内，则在计算总体平均值时仅考虑最近的一个。

我想将其实现为一个简单的两步过程：应用半径过滤器，然后应用方向拟合器，并取平均值。

但是，我假设已经有一种算法可以完成此任务，或者可能有一种更聪明的方法来完成此任务。有什么想法吗？

Answer 1

一旦你得到了最近的邻居（这留给读者作为练习，因为你表明你在获取最近的点的背景下熟悉它），你可以简单地过滤掉与你的角度相似的点目标点。在这里，我使用

numpy

数组来表示点并对操作进行矢量化，但您可以将相同的逻辑应用于点的任何表示。假设您的

N

最近邻居位于形状

(N, 2)

的数组中。您的目标点是形状为

(2,)

的数组。

import numpy as np

N = 10
angle_threshold = 30 * np.pi / 180

np.random.seed(1) # So we get the same points from random.random every time 
pts = np.random.random((N, 2))
target_pt = np.array([0.25, 0.25])

您可以使用以下方法计算从目标点到每个邻居点的向量，以及该向量与 X 轴形成的角度：

vec_to_neighbors = pts - target_pt
neighbor_angles = np.arctan2(vec_to_neighbors[:, 1], vec_to_neighbors[:, 0])
neighbor_angles[neighbor_angles < 0] += 2 * np.pi # Convert range of `arctan` from `[-pi pi]` to `[0 2*pi]`

现在，获取按升序对角度进行排序的索引，并将其应用于角度和邻居数组：

angle_sort_ix = np.argsort(neighbor_angles)

angles_sorted = neighbor_angles[angle_sort_ix]
neighbors_sorted = pts[angle_sort_ix, :]

最后，过滤掉与上一个相差30度以内的所有点。您可以使用 numpy 执行此操作，但如果点数量较少，则在 python 中循环应该足够快，

if

语句中的第二个条件检查该点与第一个点的距离是否超过 30 度，以处理点的角度例如为的情况10 度和 350 度：

selected_pts = [neighbors_sorted[0, :]]
last_selected_pt = 0
for i in range(1, pts.shape[0]):
    if abs(angles_sorted[i] - angles_sorted[last_selected_pt]) % (2 * np.pi) > angle_threshold and \
       abs(angles_sorted[i] - angles_sorted[0]) % (2 * np.pi) > angle_threshold:
        selected_pts.append(neighbors_sorted[i, :])
        last_selected_pt = i

selected_pts = np.array(selected_pts)

现在您可以绘制点以确认一切都正确。点旁边的文本是它相对于目标点所成的角度：

from matplotlib import pyplot as plt
fig, ax = plt.subplots()
ax.plot(pts[:, 0], pts[:, 1], 'ok')
ax.plot(selected_pts[:, 0], selected_pts[:, 1], 'o', c='orange')
ax.plot(target_pt[0], target_pt[1], 'or')
ax.axis('equal')
for i in range(len(pts)):
    ax.text(neighbors_sorted[i, 0], neighbors_sorted[i, 1], f"{angles_sorted[i]*180/np.pi:.1f}")