C# で k-d tree を作る
こんにちは。
仕事の自動化にやりがいと達成感を感じるガッくんです。
この記事の目次
背景・目的
せっかく Class のことをおさらいしてきたので、最後(?)に Class を使ってオブジェクト指向な感じで k-d tree を構築するプログラムを書きました。
動作環境
・Windows 7
・Visual Studio 2017
プログラム
ソースコード
using System;
using System.Collections.Generic;
namespace k_d_tree
{
class Program
{
static void Main(string[] args)
{
// ノードリストの作成
List point = new List();
// ノードリストにノード座標を入力していく
point.Add(new Node(1, 2, 3));
point.Add(new Node(2, 5, 4));
point.Add(new Node(3, 9, 6));
point.Add(new Node(4, 4, 7));
point.Add(new Node(5, 8, 1));
point.Add(new Node(6, 7, 2));
// tree クラスのインスタンス作成
tree t = new tree();
// k-d tree の構築
Node ret = t.Build(point, 0);
// k-d tree のコンソール表示
t.Disp(ret, 0, "");
Console.WriteLine("何かキーを押して下さい.");
Console.ReadKey();
}
}
class Node
{
// メンバ
public int ID;
public List Vector = new List();
public Node left_child;
public Node right_child;
// コンストラクタ
public Node(int id, double x, double y)
{
ID = id;
Vector.Add(x);
Vector.Add(y);
}
}
class tree
{
// k-d tree 構築用メソッド
public Node Build(List nodeList, int depth)
{
if (nodeList.Count == 0)
{
return null;
}
int k = nodeList[0].Vector.Count;
int axis = depth % k;
nodeList.Sort(delegate (Node n1, Node n2)
{
if (n1.Vector[axis] > n2.Vector[axis])
{
return 1;
}
else if (n1.Vector[axis] < n2.Vector[axis])
{
return -1;
}
return 0;
});
int median = nodeList.Count / 2;
List leftNodeList = new List();
List rightNodeList = new List();
for (int i = 0; i < median; i++)
{
leftNodeList.Add(nodeList[i]);
}
for (int i = median + 1; i < nodeList.Count; i++)
{
rightNodeList.Add(nodeList[i]);
}
Node node = nodeList[median];
node.left_child = Build(leftNodeList, depth + 1);
node.right_child = Build(rightNodeList, depth + 1);
return node;
}
// コンソール表示用メソッド
public void Disp(Node node, int depth, string LR)
{
if (node == null) return;
Console.WriteLine(new string('-', depth * 2) + "> " + LR + "{0}:({1},{2})", node.ID, node.Vector[0], node.Vector[1]);
Disp(node.left_child, depth + 1, "Left");
Disp(node.right_child, depth + 1, "Right");
}
}
}
コメント
ソートを使った k-d tree の構築はバランスの良い tree が出来ますが、ソートをするため計算コストが高いです。
以上