C++によるKD treeの最近傍探索の実装方法

KD Treeの最近傍探索を実装

現在、KDTree(2次元)の最近傍探索(Nearest Neighbor Search)を実装しようとしているのですが、
泥沼にはまってしまい、ただ最近傍探索を実装するためだけに丸3日を消費してしまっています。
どなたかお助けいただければと思います。

泥沼にハマっている箇所

item(2次元データ:(x,y))の最近傍ノードを探索したいと仮定します。

最近傍探索の原理は、私の理解として、
https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search
で理解しております。
(日本語版ではこちらですが、英語の方が親切に説明してくれています。)
https://ja.wikipedia.org/wiki/Kd%E6%9C%A8#kd%E6%9C%A8%E3%81%A7%E3%81%AE%E6%9C%80%E8%BF%91%E5%82%8D

ここで、まず、葉ノードに行くのはいいのですが、
親ノードに行って、そこで必要があれば兄弟ノードも確認して、確認したら、そのまた親ノードに行って...というふうに繰り返すところがうまく再帰で作れませんでした。(該当コードは後述)

実装済KDTreeの概要(あくまで参考ですので読み飛ばしていただいても結構です。)

KDTreeの構築は終わっております。
ノードは、left,right,parent,data,levelのメンバを持っており、
left,right,parentはポインタ、data,levelは値です。
left,right,parentはそれぞれ自分の左の子ノード、右の子ノード、親ノードへのポインタで、
dataは2次元データ(x,y)が入っています((ex) node->dataは(3.6,9.5)で、node->data.xで3.6,node->data.yで9.5が参照できます。(型はxもyもdouble))
levelはそのノードの深さがintで入っています(rootを1としている。(ちなみに、rootはKDTクラスのメンバ変数であるため、どこからでも参照可能))

仮に何かノードをKDTreeに挿入するとしたら、奇数層から偶数層においてはxを、偶数層から奇数層においてはyを比較対象として、左右に振り分けます。なので、何かノードを挿入するとして、まずroot(第1層)と比較するときはお互いのx軸の値を見て、左右を決めます。その下の層(第2層)では挿入したいノードと現在いる第2層のノードのy軸の値を比較して左右を決めて行きます。その下の層ではまたx軸で比較する、というように繰り返します。

つまりやっていただきたいこと。

KDTreeの最近傍探索をC++で書いていただきたいです。
つまり、以下のアルゴリズムをC++で書いていただきたいです。
(原理の共有のためURLを載せます。上記と同じ。)
https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

(日本語版ではこちらですが、英語の方が親切に説明してくれています。)
https://ja.wikipedia.org/wiki/Kd%E6%9C%A8#kd%E6%9C%A8%E3%81%A7%E3%81%AE%E6%9C%80%E8%BF%91%E5%82%8D

該当のソースコード

参考までに私の書いたコードを載せますが、あくまで参考(しかも失敗している)です。

対象のポイント(item)に一番近いノードをKDTreeから探してきます。

C++
1   virtual iterator findNearestNeighbor(const Point& item) const {
2      BSTNode<Point>* tempNode = root;
3      double diff =9999999.9;
4      double* smallestSquareDistance= &diff;
5      BSTNode<Point>** closestPoint = &tempNode;
6
7      findNNHelper(tempNode, item, smallestSquareDistance, closestPoint,1);
8
9      BST<Point>::iterator itr=this->begin();
10      BST<Point>::iterator end=this->end();
11      for(;itr!=end;itr++){
12	if(*itr==(**closestPoint).data){
13	  break;
14	}
15      }
16      return itr;
17   }

C++
1    void  findNNHelper(BSTNode<Point> * node, const Point& queryPoint,
2                                 double * smallestSquareDistance, 
3                                 BSTNode<Point> ** closestPoint,
4                                 unsigned int flag) const {
5
6      
7      BSTNode<Point>* ptr = node;
8      BSTNode<Point>* parents;
9
10      
11      if(ptr->parent==0){
12	return;
13      }else{
14      if(flag==1){ //1は下まで下がる必要があるとき
15      while(ptr!=0){
16	if((ptr->level)%2==1){//odd //x-axis
17	  if(queryPoint.x>=ptr->data.x){
18	    parents = ptr;
19	    ptr = ptr->right;
20	  }else{
21	    parents = ptr;
22	    ptr = ptr->left;
23	  }
24	}else if((ptr->level)%2==0){//even //y-axis
25	  if(queryPoint.y>=ptr->data.y){
26	    parents = ptr;
27	    ptr = ptr->right;
28	  }else{
29	    parents = ptr;
30	    ptr = ptr->left;
31	  }
32	}
33      }
34    
35      ptr = parents;
36      }
37     }
38      
39      double dst =  Point::squareDistance(queryPoint,ptr->data);
40
41      if(*smallestSquareDistance>dst){
42	*smallestSquareDistance = dst;
43	*closestPoint = ptr;
44      }
45
46      if(ptr->parent!=NULL){
47
48	
49	if((ptr->parent->level)%2==0){
50	  if(fabs(ptr->parent->data.x-queryPoint.x)<*smallestSquareDistance){
51	    if(ptr==ptr->parent->left){
52	      findNNHelper(ptr->parent->right,queryPoint,smallestSquareDistance,closestPoint,1);
53	    }else{
54	      findNNHelper(ptr->parent->left,queryPoint,smallestSquareDistance,closestPoint,1);
55	    }
56	  }else{
57	    //cout<<"go to a parent"<<endl;
58	    findNNHelper(ptr->parent,queryPoint,smallestSquareDistance,closestPoint,0);
59
60	  }
61	}
62	  
63	else if((ptr->parent->level%2!=0)){
64	  if(fabs(ptr->parent->data.y-queryPoint.y)<*smallestSquareDistance){
65	    if(ptr==ptr->parent->left){
66	      findNNHelper(ptr->parent->right,queryPoint,smallestSquareDistance,closestPoint,1);
67	    }else{
68	      findNNHelper(ptr->parent->left,queryPoint,smallestSquareDistance,closestPoint,1);
69	   }
70	  }else{
71	    //cout<<"go to a parent"<<endl;
72	    findNNHelper(ptr->parent,queryPoint,smallestSquareDistance,closestPoint,0);
73
74	  }
75	}
76      }else{
77	return;
78      }
79      return;
80    }

試したこと

全ノードに対して、対象のitemとのユークリッド距離を計算する方法はもちろん1つの手としてありますが、
それではKDTreeである意味がありません(KDTreeの特徴を完全無視している)ので、上述したURLに記載されているやり方でよろしくお願いします。

お手数ですが、よろしくお願いいたします。

行動規範の内容に同意します

回答1件

ベストアンサー

http://techtipshoge.blogspot.jp/2013/06/ck-d-tree.html
http://pointclouds.org/documentation/tutorials/kdtree_search.php
http://atkg.hatenablog.com/entry/2016/12/18/002353
http://kujira16.hateblo.jp/entry/2016/03/03/215621

すでにネット上に公開されている資料がたくさんありますが、それが参考にならない理由について追記していただけませんか。
どのような情報がほしいのかよくわかりません。
実装をすることが目的であれば、コードもらっても意味ありません。
使いたいだけなら、実装方法がわからないのに、わざわざ自分で実装する必要もありません。

投稿2018/01/31 09:05

mkgrei

総合スコア8560

omiteratail

2018/02/01 10:50 編集

mkgreiさんご回答ありがとうございます。実は学校での課題でKDTreeの実装というものがありまして、丸3日消費してしまったこともあり、かなり行き詰まってしまってここで質問させていただいた次第でした。 mkgreiさんに提示していただいたサイトも、その行き詰まっている際に見ていたのですが、実際には理解しようとせず、もっと「わかりやすいサイト」を探し求めているだけでした。ただ、mkgreiさんに再度それらのサイトを貼っていただき、当たり前のことではあるのですが実際に手を動かしてコードを真似て書いてみたところ、無事求めている通りにコードを動かす事ができました。ありがとうございました！

行動規範の内容に同意します