이 글에서는 KD 트리를 통해 가장 가까운 지점을 찾는 C#을 주로 소개합니다. 관심 있는 친구들은 참고해 보세요.
이 글에서는 먼저 Kd-Tree의 구성 방법을 소개하고 검색 과정을 소개합니다. Kd-Tree의 코드 구현, 그리고 마지막으로 C# 언어를 사용하여 제가 구현한 2차원 KD 트리 코드입니다. 이것은 제가 직접 구현한 최초의 트리 형태의 데이터 구조이기도 합니다. 필연적으로 이해의 차이가 있을 수 있으니 정정해 주시기 바랍니다.
1. KD 트리 소개
K-차원 트리라고도 알려진 Kd-Tree(KD 트리)는 대규모 최근접 이웃 분석을 수행하는 데 자주 사용되는 고차원 인덱스 트리 데이터 구조입니다. -고차원 데이터 공간을 검색하고 가장 가까운 이웃 검색을 근사화합니다. 제가 구현한 KD 트리는 2차원 Kd-트리입니다. 목적은 포인트 세트에서 가장 가까운 포인트를 찾는 것입니다. 참고 자료는 Kd-Tree의 Baidu Encyclopedia입니다. 그리고 코드는 Baidu Encyclopedia의 논리에 따라 구성됩니다.
2. KD 트리의 수학적 설명
3. KD 트리 구성 방법
다음은 Kd-트리 구성에 사용되는 2차원 점 집합입니다. 입체감도 비슷해요.
트리에 있는 각 노드의 데이터 유형:
public class KDTreeNode { /// <summary> /// 分裂点 /// </summary> public Point pisionPoint { get; set; } /// <summary> /// 分裂类型 /// </summary> public EnumpisionType pisionType { get; set; } /// <summary> /// 左子节点 /// </summary> public KDTreeNode LeftChild { get; set; } /// <summary> /// 右子节点 /// </summary> public KDTreeNode RightChild { get; set; } }
3.1 KD 트리 구성 논리 프로세스
모든 점을 집합 a에 넣습니다.
집합에 있는 모든 점의 X 좌표의 분산 xv를 계산합니다. , Y 좌표는 분산 yv
를 찾습니다. xv > yv이면 X 좌표에 따라 집합 a를 정렬합니다. yv > xv이면 집합 a는 y 좌표에 따라 정렬됩니다.
정렬된 집합 a의 중앙값 m을 구합니다. 그런 다음 m을 중단점으로 사용하고 [0,m-2]로 인덱스된 점을 a1 세트에 넣습니다. [m,a.count]로 인덱스된 포인트를 a2 집합에 넣습니다(포인트 m의 인덱스는 m-1입니다).
노드를 구성합니다. 노드의 값은 a[m-1]입니다. 작업 집합의 노드 수가 1보다 크면 왼쪽 노드는 [0, m에 대해 2~5단계를 반복합니다. -2], 오른쪽 노드는 [m,a.count]입니다. 그렇지 않으면 노드는 리프 노드입니다.
3.2 코드 구현
private KDTreeNode CreateTreeNode(List<Point> pointList) { if (pointList.Count > 0) { // 计算方差 double xObtainVariance = ObtainVariance(CreateXList(pointList)); double yObtainVariance = ObtainVariance(CreateYList(pointList)); // 根据方差确定分裂维度 EnumpisionType pisionType = SortListByXOrYVariances(xObtainVariance, yObtainVariance, ref pointList); // 获得中位数 Point medianPoint = ObtainMedian(pointList); int medianIndex = pointList.Count / 2; // 构建节点 KDTreeNode treeNode = new KDTreeNode() { pisionPoint = medianPoint, pisionType = pisionType, LeftChild = CreateTreeNode(pointList.Take(medianIndex).ToList()), RightChild = CreateTreeNode(pointList.Skip(medianIndex + 1).ToList()) }; return treeNode; } else { return null; } }
4. KD 트리 검색 방법
Kd-Tree의 전체 검색 과정은 먼저 일반 검색을 기반으로 가장 가까운 리프 노드를 찾습니다. 하지만 이 리프 노드가 반드시 가장 가까운 지점은 아닙니다. 그런 다음 역추적 작업을 수행하여 가장 가까운 지점을 찾습니다.
4.1 KD 트리 검색 논리 프로세스
포인트 세트를 기반으로 구축된 트리 t와 검색 포인트 p에 대해 루트 노드를 노드 t로 사용하여 다음 작업을 수행합니다.
t가 리프 노드. 그런 다음 가장 가까운 점 n의 값이 t인 분할 점의 값을 얻고, t가 리프 노드가 아니면 3단계로 진행합니다.
그런 다음 t의 분할 방법을 결정합니다. x축을 따라 분할됩니다. 그런 다음 p의 x 값을 노드 분할 지점의 x 값과 비교합니다. 그렇지 않으면 Y 좌표를 비교합니다.
p의 비교 값이 t의 비교 값보다 작으면 t는 t의 왼쪽 자식 노드로 지정됩니다. 그렇지 않으면 t를 t의 오른쪽 하위 노드로 지정하고 2
단계를 수행하여 검색 지점 m을 정의하고 m을 n
으로 설정하고 m과 p 사이의 거리 d1과 n 사이의 거리 d2를 계산합니다. 그리고 m.
d1 >= d2이고 상위 노드가 있는 경우 m의 상위 노드를 m의 값으로 사용하고 상위 노드가 없으면 d1인 경우 실제 가장 가까운 지점 TN을 가져옵니다. < d2는 n을 의미합니다. 해당 지점이 가장 가까운 지점이 아닙니다. n에 형제 노드가 있으면 n = n의 형제 노드이고, n에 형제 노드가 없으면 n = n의 상위 노드입니다. 원래 n개 노드를 삭제합니다. m 값을 새로운 n 노드로 설정합니다. 6단계를 수행합니다.
4.2 코드 구현
public Point FindNearest(Point searchPoint) { // 按照查找方式寻找最近点 Point nearestPoint = DFSSearch(this.rootNode, searchPoint); // 进行回溯 return BacktrcakSearch(searchPoint, nearestPoint); } private Point DFSSearch(KDTreeNode node,Point searchPoint,bool pushStack = true) { if(pushStack == true) { // 利用堆栈记录查询的路径,由于树节点中没有记载父节点的原因 backtrackStack.Push(node); } if (node.pisionType == EnumpisionType.X) { return DFSXsearch(node,searchPoint); } else { return DFSYsearch(node, searchPoint); } } private Point BacktrcakSearch(Point searchPoint,Point nearestPoint) { // 如果记录路径的堆栈为空则表示已经回溯到根节点,则查到的最近点就是真正的最近点 if (backtrackStack.IsEmpty()) { return nearestPoint; } else { KDTreeNode trackNode = backtrackStack.Pop(); // 分别求回溯点与最近点距查找点的距离 double backtrackDistance = ObtainDistanFromTwoPoint(searchPoint, trackNode.pisionPoint); double nearestPointDistance = ObtainDistanFromTwoPoint(searchPoint, nearestPoint); if (backtrackDistance < nearestPointDistance) { // 深拷贝节点的目的是为了避免损坏树 KDTreeNode searchNode = new KDTreeNode() { pisionPoint = trackNode.pisionPoint, pisionType = trackNode.pisionType, LeftChild = trackNode.LeftChild, RightChild = trackNode.RightChild }; nearestPoint = DFSBackTrackingSearch(searchNode, searchPoint); } // 递归到根节点 return BacktrcakSearch(searchPoint, nearestPoint); } }
위 내용은 KD 트리를 통해 가장 가까운 지점을 검색하는 C# 예제 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!