kdtree.net库

按指定距离阈值匹配两个X维点数组的高速实现库。using KdTree.Math; using KdTree; using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows.Forms; using System.Diagnostics; namespace WindowsFormsApp_KdTree { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { var tree new KdTreedouble, string(2, new DoubleMath()); var rand new Random(); var setA new ListDefectPoint(); var setB new ListDefectPoint(); for (var i 1; i 30000; i) { setA.Add(new DefectPoint(((float)rand.NextDouble() - 0.5f) * 150, ((float)rand.NextDouble() - 0.5f) * 150, i)); setB.Add(new DefectPoint(((float)rand.NextDouble() - 0.5f) * 150, ((float)rand.NextDouble() - 0.5f) * 150, i)); } // 距离阈值 float threshold 3.0f; var stop new Stopwatch(); stop.Start(); var result DefectMatcher.Match(setA, setB, threshold); stop.Stop(); Console.WriteLine($成功匹配对数: {result.Matched.Count}); Console.WriteLine($A独有缺陷(新增): {result.OnlyA.Count}); Console.WriteLine($B独有缺陷(消失): {result.OnlyB.Count} {stop.ElapsedMilliseconds}ms); } } public static class DefectMatcher { /// summary /// KDTree实现两组二维缺陷点匹配 /// /summary public static MatchResult Match(ListDefectPoint setA, ListDefectPoint setB, float distanceThreshold) { // 1. 基准集合B构建KDTree存储原始索引 var tree new KdTreefloat, int(2, new FloatMath()); for (int i 0; i setB.Count; i) { var p setB[i]; tree.Add(new[] { p.X, p.Y }, i); } // 收集所有候选匹配 (A索引,B索引,距离平方) var candidates new List(int aIdx, int bIdx, double distSq)(); double threshSq distanceThreshold * distanceThreshold; for (int aIdx 0; aIdx setA.Count; aIdx) { var pa setA[aIdx]; var pos new[] { pa.X, pa.Y }; // 半径搜索 var nearList tree.RadialSearch(pos, distanceThreshold); foreach (var near in nearList) { int bIdx near.Value; var pb setB[bIdx]; double dx pa.X - pb.X; double dy pa.Y - pb.Y; double distSq dx * dx dy * dy; if (distSq threshSq) { candidates.Add((aIdx, bIdx, distSq)); } } } // 贪心匹配距离近优先保证一对一防止一对多 var sorted candidates.OrderBy(x x.distSq).ToList(); bool[] usedA new bool[setA.Count]; bool[] usedB new bool[setB.Count]; var matchedPairs new List(DefectPoint A, DefectPoint B)(); foreach (var item in sorted) { if (!usedA[item.aIdx] !usedB[item.bIdx]) { usedA[item.aIdx] true; usedB[item.bIdx] true; matchedPairs.Add((setA[item.aIdx], setB[item.bIdx])); } } // 提取独有点 var onlyA setA.Where((_, i) !usedA[i]).ToList(); var onlyB setB.Where((_, i) !usedB[i]).ToList(); return new MatchResult { Matched matchedPairs, OnlyA onlyA, OnlyB onlyB }; } } public class MatchResult { public List(DefectPoint A, DefectPoint B) Matched { get; set; } public ListDefectPoint OnlyA { get; set; } public ListDefectPoint OnlyB { get; set; } } public struct DefectPoint { public float X { get; set; } public float Y { get; set; } public int Id { get; set; } public DefectPoint(float x, float y, int id) { X x; Y y; Id id; } } }10000vs10000耗时0.23s30000vs30000耗时1.9s50000vs50000耗时5.4s100000vs100000耗时30s不算最高效数据较多需选其他c的库如opencv或FLANN实现