基于距离阈值筛选：求高效删除近邻数据的Python优化方案

Hey there! Let's fix that slow double-loop code and make it way more efficient for large datasets. First, a quick bug note in your original implementation: when calculating the distance's y-component, you have data[i, 1]-data[i, 1]—that should be data[i, 1]-data[j, 1], otherwise the y-difference will always be zero, leading to wrong distance calculations.

Now, onto the performance upgrade. The double loop runs in O(n²) time, which is brutal for big datasets. Below are two optimized approaches, depending on your exact requirement:

Option 1: Filter points too close to their immediate previous neighbor #

If your goal is only to remove points that are within 0.1m of the directly preceding point (e.g., cleaning up a trajectory where consecutive points are redundant), use numpy's vectorized operations—this runs in O(n) time and is lightning fast:

import numpy as np

# Calculate differences between consecutive points
dx = np.diff(data[:, 0])
dy = np.diff(data[:, 1])

# Compute Euclidean distances between adjacent points
distances = np.sqrt(dx**2 + dy**2)

# Create a mask: keep the first point, plus any point where distance > 0.1
mask = np.concatenate([[True], distances > 0.1])

# Apply the mask to get filtered data
filtered_data = data[mask]

This avoids any explicit loops entirely, leveraging numpy's optimized C-backed operations for speed.

Option 2: Filter points too close to any previous point #

If you need to remove a point if it's within 0.1m of any point that came before it (matching your original code's logic), use a cKDTree from scipy to efficiently find nearest neighbors. This runs in O(n log n) time, which is way better than O(n²):

import numpy as np
from scipy.spatial import cKDTree

filtered_points = []
# Initialize an empty KD Tree
kdtree = cKDTree(np.empty((0, 2)))

for point in data:
    # Find the minimum distance to any point already in the tree
    min_distance, _ = kdtree.query(point, k=1)
    
    # Keep the point if it's far enough (or if it's the first point, where min_distance is inf)
    if min_distance > 0.1 or np.isinf(min_distance):
        filtered_points.append(point)
        # Update the tree with the new point
        kdtree = cKDTree(np.vstack([kdtree.data, point]))

filtered_data = np.array(filtered_points)

The KD Tree lets us quickly look up the closest existing point without checking every single previous entry, which cuts down computation time dramatically for large datasets.

内容的提问来源于stack exchange，提问作者user2554925