海量二维分布中点分布近似搜索的算法与优化问询

针对第一个问题：适用于该类近似分布搜索任务的经典算法 #

这类任务本质是带旋转、缩放、平移不变性的二维点集模式匹配问题，有成熟的经典算法可以直接复用，不需要从零搭建方案：

• 几何哈希（Geometric Hashing）：这是专门为无先验基准的点集匹配设计的经典算法。核心逻辑是先从手绘星座点集中选取点对构造局部归一化坐标系，将所有点的坐标转换为不受旋转、等比缩放、平移影响的不变量，基于这些不变量构建哈希索引；之后在全量星图中遍历同规模的点对做同样的坐标转换，统计哈希碰撞的匹配点数，快速筛除绝大多数不匹配的候选点集，最后只对通过初筛的候选做Kolmogorov Smirnov检验，判断是否满足相似度阈值即可。
• 形状上下文（Shape Context）匹配：形状上下文是专门描述点集局部分布特征的描述子，对轻度的手绘形变、点的漏绘/多绘有不错的鲁棒性，本身对平移不敏感，做归一化处理后也能支持旋转、缩放不变的匹配。流程上先计算手绘点集和星图局部点簇的形状上下文特征，用特征匹配的成本筛选候选，再通过薄板样条变换对齐两个点集后做KS校验即可。
• 基于点对距离签名的快速检索算法：旋转、等比缩放不会改变点集内部点对的相对距离比例，因此可以先把手绘星座内所有点对的距离做归一化（除以点集内最大点对距离），排序后得到全局距离分布签名；提前给星图中所有符合点数范围的候选点簇预计算同类签名，用简单的分布距离做粗筛，就能快速把候选规模压到可处理的量级。

针对第二个问题：降低求解复杂度的可行思路 #

如果需要针对这个特定的星图匹配场景做优化，核心是绕开「遍历所有旋转、缩放参数」的暴力求解思路，从根源上削减组合爆炸的开销，可落地的思路包括：

• 优先用RST不变量做第一层过滤：所有计算都先转成不受旋转（Rotation）、缩放（Scale）、平移（Translation）影响的特征，比如点集内任意三点构成的三角形内角余弦值、点对距离和点集外接圆直径的比值、点到点集质心的归一化距离分布等，用这些特征做索引过滤，完全不需要遍历旋转角、缩放比例参数，能直接过滤99%以上的无效候选。
• 采用分层匹配的漏斗式流程：不要上来就对全量星图的点集组合跑KS检验。第一层用全局不变量签名做粗筛，保留千分之一量级的候选；第二层用局部点特征做匹配，拟合两个点集之间的变换矩阵，剔除内点率不达标的候选；最后只对剩下的个位数级别候选做KS检验，计算量会呈数量级下降。
• 提前加合理的业务约束剪枝：手绘星座本身有合理的尺度范围，不可能在星图上跨上百度过大的天区，也不可能小到几角秒的极小范围，可以提前按不同尺度把星图切分成网格块，每个网格块只保留和手绘星座点数差在±20%范围内的点簇（留容错空间给手绘漏点、多画点的情况），从根源上减少需要遍历的点集组合数。
• 优化KS检验的计算开销：标准KS检验需要对两个样本做排序，时间复杂度为O(nlogn)，可以提前对每个网格块内恒星的x、y坐标做预排序存储，计算KS统计量时直接复用预排序结果，把单次检验的耗时降到线性级别。

注意：不要尝试用遍历旋转角、缩放步长的暴力思路做匹配，这类方法的时间复杂度会随星图恒星总数呈指数级上升，没有落地可行性。

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