1. 从两道题看空间查询与轨迹筛查的底层逻辑检测点查询和风险人群筛查这两个词放在一起看特别有意思。前者是典型的最近邻搜索问题后者是典型的轨迹区域判定问题。它们表面上分属两个不同的题目但骨子里都在解决同一类事情给定一堆空间中的点或者一条移动路径如何快速判断谁在范围内哪个最近有没有越界。我第一次接触这类问题时直觉反应是直接算距离不就行了。确实对于小规模数据暴力遍历完全够用。但当你真正去写、去调、去优化的时候会发现里面藏着不少细节距离怎么算才不丢精度时间窗口怎么卡边界算不算命中这些细节不处理好代码跑出来的结果和预期差得离谱。这篇文章适合两类人看一类是正在刷算法题、想把这套空间判定的思路彻底吃透的朋友另一类是在实际项目里做地理围栏、轨迹分析、点位推荐的开发者。我会从最朴素的暴力解法讲起一步步拆到精度处理、边界判定、复杂度优化把每道题背后的为什么讲清楚。你看完之后应该能自己写出稳定、可复现的代码而不是抄一份答案就完事。2. 检测点查询最近邻搜索的完整拆解2.1 问题本质与暴力解法的合理性检测点查询的核心需求很直白给一个参考点在一堆候选点里找出距离最近的那个。如果距离相同按编号小的优先。听起来简单但最近这两个字背后是欧氏距离的计算。假设参考点坐标是 $(x, y)$某个检测点坐标是 $(x_i, y_i)$那么距离的平方是$$d_i^2 (x - x_i)^2 (y - y_i)^2$$这里有个关键决策要不要开平方。很多人第一反应是老老实实算 $\sqrt{(x-x_i)^2 (y-y_i)^2}$然后比大小。但开平方是单调递增函数比较平方值和比较原值是等价的。所以为了效率和精度我们直接比较平方值就行。为什么说精度因为浮点数的平方根运算会引入舍入误差。两个本来距离完全相等的点开平方之后可能一个变成 3.0000001另一个变成 2.9999999排序就乱了。而平方值都是整数运算如果坐标是整数完全精确不会出现这种问题。暴力解法的复杂度是 $O(n)$对于题目给定的数据规模通常 n 在几百到几千这个复杂度绰绰有余。我见过有人上来就想用 KD-Tree 或者四叉树结果代码写了一百多行还引入了构建树的额外开销。在这个规模下暴力遍历就是最优解不要过度设计。2.2 距离比较中的排序陷阱找到最近点之后还要处理距离相同取编号小这个规则。这里有个容易踩的坑如果你用排序来做排序的稳定性、比较函数的写法都会影响结果。我推荐的做法是一次遍历维护当前最优。伪代码逻辑是这样的best_idx -1 best_dist infinity for i in range(n): d (x - xi)**2 (y - yi)**2 if d best_dist or (d best_dist and i best_idx): best_dist d best_idx i注意那个or后面的条件。当距离相等时只有当新点的编号更小才更新。由于我们是从小到大遍历编号的实际上第一次遇到某个距离值时就已经是最小
