kdtree.node source code

1 
2 module kdtree.node;
3 
4 import kdtree.point;
5 
6 struct KDNode(size_t k, T) if(k > 0)
7 {
8     KDPoint!(k, T) point;
9 
10     KDNode!(k, T) *left  = null;
11     KDNode!(k, T) *right = null;
12 
13     this(KDPoint!(k, T) point)
14     {
15         this.point = point;
16     }
17 
18     static KDNode!(k, T) *build(T[k][] points...)
19     {
20         return build(KDPoint!(k, T).build(points));
21     }
22 
23     static KDNode!(k, T) *build(KDPoint!(k, T)[] points, size_t depth = 0)
24     {
25         if(points.length > 1)
26         {
27             auto axis = depth % k;
28 
29             auto sorted = points.sortedOn(axis);
30             auto median = sorted[$ / 2];
31 
32             auto node = new KDNode!(k, T)(median);
33 
34             if(sorted.length / 2 > 0)
35             {
36                 node.left = build(sorted[0 .. $ / 2], depth + 1);
37             }
38             if(sorted.length / 2 + 1 < sorted.length)
39             {
40                 node.right = build(sorted[$ / 2 + 1 .. $], depth + 1);
41             }
42 
43             return node;
44         }
45         else if(points.length == 1)
46         {
47             return new KDNode!(k, T)(points[0]);
48         }
49         else
50         {
51             return null;
52         }
53     }
54 
55     @property
56     bool leaf() const
57     {
58         return left is null && right is null;
59     }
60 }