Nearest neighborS search by Binary Partition Tree

There are a lot of excellent references on Internet, one of them is:

• en.wikipedia.org/wiki/K-d_tree

The missing part: some code to play around. Let's try to make something generic. What to we need to make a class partitionable ?

    public interface IIsPartionableByBT {
        Int32 Id { get; }

        float BTX { get; }
        float BTY { get; }
        float BTZ { get; }

        float DistTo(IIsPartionableByBT c);
    }

    public delegate float BTCooProjector(IIsPartionableByBT coo);

We also need Cells/Nodes for the tree:

    public class MbtBSPNode<T> where T :  IIsPartionableByBT {
        public MbtBSPNode<T> Parent { get; set; }
        public T Cell { get; set; }
        public MbtBSPNode<T> Left { get; set; }
        public MbtBSPNode<T> Right { get; set; }

        public ICollection<MbtBSPNode<T>> Cells { get; set; }

        public UInt32 Depth { get { if (Parent == null) return 0; return Parent.Depth + 1; } }
    }

And the tree himself:

    public class MbtBSPTree<T> where T : class, IIsPartionableByBT {
        public MbtBSPNode<T> Root { get; private set; }

        public UInt16 SplitDepthBy { get; private set; }

        public UInt16 LimitDepthTo { get; private set; }

        public MbtBSPTree(IEnumerable<T> l, UInt16 splitDepthBy = 0, UInt16 limitDepthTo = 0) {
            if (SplitDepthBy == 0) {
                if (l.Min(x => x.BTZ) == l.Max(x => x.BTZ)) {
                    SplitDepthBy = 2;
                } else {
                    SplitDepthBy = 3;
                }
            } else {
                SplitDepthBy = splitDepthBy;
            }
            LimitDepthTo = limitDepthTo;

            Root = BuildBSPTree(l, 0);
        }

        public BTCooProjector DefProjector(UInt16 axis) {
            switch (axis) {
                case 0:
                    return (n) => n.BTX;
                case 1:
                    return (n) => n.BTY;
                case 2:
                    return (n) => n.BTZ;
                default:
                    throw new Exception("valeur de split de profondeur non gérée");
            }
        }

        public MbtBSPNode<T> BuildBSPTree(IEnumerable<T> l, UInt16 depth, MbtBSPNode<T> p = null) {
            if (l.Count() == 0)
                return null;
            UInt16 axis = (UInt16)(depth % SplitDepthBy);

            MbtBSPNode<T> n = new MbtBSPNode<T>();
            n.Parent = p;

            if (LimitDepthTo > 0 && depth == LimitDepthTo) {
                n.Cells = new List<MbtBSPNode<T>>();
                foreach (T cc in l) {
                    n.Cells.Add(new MbtBSPNode<T> { Cell = cc });
                }
            } else {
                Double med = Double.MinValue;
                List<T> ll = new List<T>();
                List<T> lr = new List<T>();

                BTCooProjector proj = DefProjector((UInt16)(depth % SplitDepthBy));
                med = l.Median(x => proj(x));
                foreach (T c in l) {
                    if (proj(c) < med) {
                        ll.Add(c);
                    } else {
                        if (proj(c) == med) {
                            if (n.Cell == null)
                                n.Cell = c;
                            else
                                ll.Add(c);
                        } else {
                            lr.Add(c);
                        }
                    }
                }

                if (depth <= 2) {
                    //this will lead to 8 threads
                    Task<MbtBSPNode<T>> tl = Task<MbtBSPNode<T>>.Factory.StartNew(() =>
                        BuildBSPTree(ll, (UInt16)(depth + 1), n));
                    n.Right = BuildBSPTree(lr, (UInt16)(depth + 1), n);
                    //synchro thread
                    n.Left = tl.Result;
                } else {
                    n.Left = BuildBSPTree(ll, (UInt16)(depth + 1), n);
                    n.Right = BuildBSPTree(lr, (UInt16)(depth + 1), n);
                }
            }

            return n;
        }

#if DEBUG
        public Int32 ScannedNodeNumber { get; set; }
#endif

        public IEnumerable<MbtBSPNode<T>> GetNearestNodes(T cel, float radius) {
#if DEBUG
            ScannedNodeNumber = 0;
#endif
            MbtBSPNode<T> current;
            Queue<MbtBSPNode<T>> q = new Queue<MbtBSPNode<T>>();
            q.Enqueue(Root);

            while (q.Count > 0) {
                current = q.Dequeue();
                BTCooProjector proj;

                if (current.Cell != null) {
#if DEBUG
                    ScannedNodeNumber++;
#endif
                    if (cel.DistTo(current.Cell) <= radius && cel.Id != current.Cell.Id) {
                        yield return current;
                    }

                    proj = DefProjector((UInt16)(current.Depth % SplitDepthBy));

                    if (proj(cel) - radius <= proj(current.Cell)) {
                        if (current.Left != null)
                            q.Enqueue(current.Left);
                    }
                    if (proj(cel) + radius > proj(current.Cell)) {
                        if (current.Right != null)
                            q.Enqueue(current.Right);
                    }
                }

                if (current.Cells != null) {
                    foreach (MbtBSPNode<T> cc in current.Cells) {
#if DEBUG
                        ScannedNodeNumber++;
#endif
                        if (cel.Id != cc.Cell.Id && cel.DistTo(cc.Cell) <= radius)
                            yield return cc;
                    }
                }

            }
        }

One can find a median algorithm in here:

• stackoverflow.com/questions/4140719/calculate-median-in-c-sharp