解析エンジニアの自動化 blog

コツコツと自動化した方法を残す blog

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");
        }
    }
}



結果


図1 結果



コメント

ソートを使った k-d tree の構築はバランスの良い tree が出来ますが、ソートをするため計算コストが高いです。



以上