KDTree近邻匹配中坐标匹配次数超输入重复行数问题咨询

为什么匹配次数会超过重复次数 #

你对coords做重复的操作本身逻辑不成立，spatial.cKDTree的最近邻查询仅根据坐标距离返回结果，和同一个坐标在KDTree中存储的次数没有关联：

• 同一个(X Rotate,Y Rotate)坐标重复31次存入KDTree，仅会生成31个位置完全相同的点，查询时只要该坐标是距离查询点最近的，不管重复多少次，返回的匹配结果都是这个坐标，不会因为你设置了重复次数就限制它的被匹配次数。
• 空间分布上覆盖更多map点的coords坐标，自然会被更多map点匹配到，出现次数远高于31次是正常现象，和你是否重复coords完全无关。

如何实现带配额的匹配 #

你需要的是带配额约束的最近邻分配，可以按以下逻辑实现：

• 第一步先初始化配额：总待匹配map点共83150个，coords共2702个，先给每个coords点设置30的基础配额，剩余未分配的83150 - 2702*30 = 2090个配额，随机分配给2090个coords点，最终2090个点配额为31、其余为30，刚好覆盖总匹配量。如果你要求所有点匹配次数都固定为30次，可随机丢弃2090个map点即可。
• 第二步构建KDTree查询候选：基于原始无重复的coords构建cKDTree，对所有map点一次性查询Top 5~10个最近邻的coords索引，保留距离排序结果。
• 第三步按配额分配：遍历所有map点（可先随机打乱map顺序避免区域集中导致的分配不均），为每个点匹配排序最靠前、且还有剩余配额的coords点，匹配完成后对应coords点的配额减1，直到所有map点都分配完成。

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