School project - RTree search implementation based on graph

IRTreeEdge.cs

namespace GraphAnalyzer.RTree
{
    public interface IRTreeEdge<out T>
    {
        IRTreePoint FromRTreePoint { get; set; }
        IRTreePoint ToRTreePoint { get; set; }
        T Value { get; }
        bool Contains(double x, double y);
    }
}

IRTreePoint.cs

namespace GraphAnalyzer.RTree
{
    public interface IRTreePoint
    {
        double X { get; }
        double Y { get; }
        bool Contains(double x, double y);
    }
}

RTree.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using GraphAnalyzer.Core.Graph;

namespace GraphAnalyzer.RTree
{
    public class RTree<T>
    {
        private IList<RTreeNode<T>> _nodes;
        private RTreeNode<T> _root;
        private RTreeNode<T> _currentNode;

        private int _currentRectangleIndex;
        private int _currentRectagleCount;
        private bool _specialInclusion;

        public RTree(IEnumerable<IRTreeEdge<T>> rTreeEdges)
        {
            BuildRTreeFromGraph(rTreeEdges);
        }

        private void BuildRTreeFromGraph(IEnumerable<IRTreeEdge<T>> rTreeEdges)
        {
            double minX = double.NaN, maxX = double.NaN, minY = double.NaN, maxY = double.NaN;
            _nodes = new List<RTreeNode<T>>();

            // Zapouzdření objektů minimálními ohraničujícími obdélníky (MOO)
            foreach (var edge in rTreeEdges)
            {
                var area = RTreeArea.CalculateRTreeArea(edge.FromRTreePoint, edge.ToRTreePoint);
                _nodes.Add(new RTreeNode<T>
                {
                    RTreeArea = area,
                    RTreeEdge = edge
                });

                // Hledám největší možnou oblast -> tu pak budu procházek Z-křivkou
                if (double.IsNaN(minX) || minX > area.X) minX = area.X;
                if (double.IsNaN(minY) || minY > area.Y) minY = area.Y;
                if (double.IsNaN(maxX) || maxX < (area.X + area.Width)) maxX = area.X + area.Width;
                if (double.IsNaN(maxY) || maxY < (area.Y + area.Height)) maxY = area.Y + area.Height;
            }

            // Vypočítám si velikost jedné mřížky
            var ratioX = Math.Abs(minX - maxX) / RTreeConfig.Instance.ZOrderGrid;
            var ratioY = Math.Abs(minY - maxY) / RTreeConfig.Instance.ZOrderGrid;

            // Najdu nalezené obdelníky pomocí Z-Křivky a v hledání pokračuji, dokud nenajdu kořen
            var result = ZOrderCurve(_nodes, RTreeConfig.Instance.ZOrderGrid, ratioX, ratioY, minX, minY);
            while (result.Count != 1)
            {
                // postavení dalšího patra
                result = ZOrderCurve(result, RTreeConfig.Instance.ZOrderGrid, ratioX, ratioY, minX, minY);
            }
            // Nastavení kořena
            _root = result.First();
        }

        public IList<RTreeNode<T>> ContinueZOrderCurve(IList<RTreeNode<T>> result, IList<RTreeNode<T>> rectangles, int level, double ratioX, double ratioY, double x, double y, bool two)
        {
            if (level == 0)
                return result;

            // minimální počet prvků v jendom uzlu
            var minimumChildrenCount = RTreeConfig.Instance.MinimumChildren;
            var currentIndex = 0;
            for (var i = 0; i < RTreeConfig.Instance.ZOrderGrid; i = i + 2)
            {
                // Jedno Z (čtyři oblasti)
                var zOrder = new List<RTreeArea>();
                zOrder.Add(new RTreeArea { X = (i * ratioX) + x, Y = y, Width = ratioX, Height = ratioY });
                zOrder.Add(new RTreeArea { X = (i * ratioX) + x + ratioX, Y = y, Width = ratioX, Height = ratioY });
                zOrder.Add(new RTreeArea { X = (i * ratioX) + x, Y = y + ratioY, Width = ratioX, Height = ratioY });
                zOrder.Add(new RTreeArea { X = (i * ratioX) + x + ratioX, Y = y + ratioY, Width = ratioX, Height = ratioY });

                // hledám incidentní obdelníky
                foreach (var rTreeArea in zOrder)
                {
                    var list = new List<RTreeNode<T>>();
                    foreach (var rectangle in rectangles) // Rectangles -> všechny hledané oblasti
                    {
                        // narazil jsem na incidentní obdelníček?
                        if (rTreeArea.Intersection(rectangle.RTreeArea) || rTreeArea.Contains(rectangle.RTreeArea.X, rectangle.RTreeArea.Y, rectangle.RTreeArea.X + rectangle.RTreeArea.Width, rectangle.RTreeArea.Y + rectangle.RTreeArea.Height))
                        {
                            // kontrola, jestli jsem ho už náhodou nenašel dříve
                            if (!result.Contains(rectangle))
                            {
                                // pokud je současný uzel plná, tak vytvořím nový
                                if (_currentNode == null || _currentNode.IsFull())
                                    _currentNode = new RTreeNode<T>();

                                // pokud současný uzel nemá ještě žádné potomky, tak ještě není zařazen
                                if (_currentNode.Children.Count == 0)
                                    result.Add(_currentNode);

                                // přidán nalezenou oblast mezi potomky aktuálního uzlu
                                var leftItems = _currentRectagleCount - _currentRectangleIndex++;

                                // podmínka nevyváženosti (když by do konce zbývali 4 prvky -> 3 a 1)
                                if ((minimumChildrenCount + minimumChildrenCount) >= leftItems)
                                {
                                    // když by měl aktuální uzel 0 potomků, tak by nebyl strom vyvážený (zůstalo by 3 a 1)
                                    if (_currentNode.Children.Count == 0)
                                    {
                                        _specialInclusion = true;
                                    }
                                }

                                // speciální shluk prvků (2 + 2) 
                                if (_specialInclusion)
                                {
                                    // pokud je první uzel naplněn (max 2) -> založím nový
                                    if (_currentNode.Children.Count == minimumChildrenCount)
                                    {
                                        _currentNode = new RTreeNode<T>();
                                        result.Add(_currentNode);
                                    }
                                }

                                // přidám nový list
                                _currentNode.Children.Add(rectangle);
                                // přepočítám oblast
                                _currentNode.CalculateArea();

                                // uložím do pomocné proměnné nalezený obdelníček
                                list.Add(rectangle);
                            }
                        }
                    }

                    // odstraním nalezené oblasti
                    foreach (var rTreeNode in list)
                        rectangles.Remove(rTreeNode);
                }

                // pokud jsem udělal druhé Z, tak skočím na další řádek
                if (++currentIndex == 2)
                {
                    if (two) return result;
                    ContinueZOrderCurve(result, rectangles, level - 2, ratioX, ratioY, zOrder[0].X - (2 * ratioX), y + 2 * ratioY, true);
                    currentIndex = 0;
                }
            }

            // právě jsem dodělal jeden "řádek" Z křivek a posouvám se opět o řádek níže
            if (level > 1)
                ContinueZOrderCurve(result, rectangles, level - 4, ratioX, ratioY, x, y + 4 * ratioY, false);

            return result;
        }

        public IList<RTreeNode<T>> ZOrderCurve(IList<RTreeNode<T>> rectangles, int level, double ratioX, double ratioY, double x, double y)
        {
            // incializace jednoho průchodu 
            _currentNode = null;
            _currentRectangleIndex = 0;
            _currentRectagleCount = rectangles.Count;
            _specialInclusion = false;

            // zahájení průchodu
            return ContinueZOrderCurve(new List<RTreeNode<T>>(), rectangles, level, ratioX, ratioY, x, y, false);
        }

        public IEnumerable<IRTreeEdge<T>> PointSearch(double x, double y)
        {
            // validace vstupu
            if (x < 0 || y < 0) return null;

            // nastartování bodového hledání -> od kořene
            return ContinuePointSearch(x, y, _root.Children, new List<RTreeNode<T>>()).Select(n => n.RTreeEdge); // -> vracím jenom hrany
        }

        private IList<RTreeNode<T>> ContinuePointSearch(double x, double y, IEnumerable<RTreeNode<T>> children, IList<RTreeNode<T>> result)
        {
            // projdu potomky aktuálního uzlu
            foreach (var child in children)
            {
                // obsahuje bod?
                if (child.RTreeArea.Contains(x, y))
                {
                    // je to list?
                    if (!child.HasChildren())
                    {
                        // našel jsem konrétní úsečku a ptám se, jestli je bod na hraně
                        if (child.RTreeEdge.Contains(x, y))
                        {
                            result.Add(child); continue;
                        }
                    }
                    // pokud není list, tak jdu o úroveň níž
                    ContinuePointSearch(x, y, child.Children, result);
                }
            }
            // výsledek 
            return result;
        }

        public IEnumerable<T> IntervalSearch(double x1, double y1, double x2, double y2)
        {
            // vytvořím hledánou oblast (dle vstupu)
            var area = new RTreeArea { X = x1, Y = y1, Width = Math.Abs(x1 - x2), Height = Math.Abs(y1 - y2) };
            // nastartuji intervalové hledání -> počátek = kořen
            return ContinueIntervalSearch(area, _root.Children, new List<RTreeNode<T>>()).Select(n => n.RTreeEdge.Value);
        }

        private IList<RTreeNode<T>> ContinueIntervalSearch(RTreeArea area, IEnumerable<RTreeNode<T>> children, IList<RTreeNode<T>> result)
        {
            // projdu potomky aktuálního uzlu
            foreach (var child in children)
            {
                // kontroluji, zda jsem nenarazil na incidenci
                if (area.Intersection(child.RTreeArea) || child.RTreeArea.Contains(area.X, area.Y, area.X + area.Width, area.Y + area.Height))
                {
                    // zkontoluji, jesli se už nejedná o list
                    if (!child.HasChildren())
                    {
                        // pokud je prvek listem, tak zkontroluji, zda hledaná oblast zasahuje přímo úsečku
                        if (ContainsLine(child.RTreeEdge, area))
                        {
                            // pokud ano -> vložím do výsledku a pokračuji v dalším hledání
                            result.Add(child);
                            continue;
                        }
                    }
                    // pokud není prvek listem, tak přejdu o patro níž
                    ContinueIntervalSearch(area, child.Children, result);
                }
            }
            // výsledek
            return result;
        }

        public bool ContainsLine(IRTreeEdge<T> edge, RTreeArea area)
        {
            return
                area.Contains(edge.FromRTreePoint.X, edge.FromRTreePoint.Y, edge.ToRTreePoint.X, edge.ToRTreePoint.Y) ||
                IntersectionLineArea(edge, area);
        }

        public bool IntersectionLineArea(IRTreeEdge<T> edge, RTreeArea area)
        {
            return Intersection(edge, area.X, area.Y, area.X + area.Width, area.Y) ||
                Intersection(edge, area.X + area.Width, area.Y, area.X + area.Width, area.Y + area.Height) ||
                Intersection(edge, area.X, area.Y + area.Height, area.X + area.Width, area.Y + area.Height) ||
                Intersection(edge, area.X, area.Y, area.X, area.Y + area.Height);
        }

        public bool Intersection(IRTreeEdge<T> line1, double x1, double y1, double x2, double y2)
        {
            return Intersection(line1.FromRTreePoint.X, line1.FromRTreePoint.Y, line1.ToRTreePoint.X,
                                line1.ToRTreePoint.Y, x1, y1, x2, y2);
        }

        public bool Intersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
        {
            return ((RelativeCcw(x1, y1, x2, y2, x3, y3) * RelativeCcw(x1, y1, x2, y2, x4, y4) <= 0) && (RelativeCcw(x3, y3, x4, y4, x1, y1) * RelativeCcw(x3, y3, x4, y4, x2, y2) <= 0));
        }

        public static int RelativeCcw(double x1, double y1, double x2, double y2, double px, double py)
        {
            x2 -= x1;
            y2 -= y1;
            px -= x1;
            py -= y1;
            double ccw = px * y2 - py * x2;
            if (ccw == 0.0)
            {
                ccw = px * x2 + py * y2;
                if (ccw > 0.0)
                {
                    px -= x2;
                    py -= y2;
                    ccw = px * x2 + py * y2;
                    if (ccw < 0.0)
                    {
                        ccw = 0.0;
                    }
                }
            }
            return (ccw < 0.0) ? -1 : ((ccw > 0.0) ? 1 : 0);
        }
    }
}

RTreeArea.cs

using System;

namespace GraphAnalyzer.RTree
{
    public class RTreeArea
    {
        public double X { get; set; }
        public double Y { get; set; }
        public double Width { get; set; }
        public double Height { get; set; }

        public static RTreeArea CalculateRTreeArea(IRTreePoint point1, IRTreePoint point2)
        {
            var area = new RTreeArea();
            area.X = Math.Min(point1.X, point2.X);
            area.Y = Math.Min(point1.Y, point2.Y);
            area.Width = Math.Abs(area.X - Math.Max(point1.X, point2.X));
            area.Height = Math.Abs(area.Y - Math.Max(point1.Y, point2.Y));
            return area;
        }

        public bool Intersection(RTreeArea area)
        {
            double tx1 = X;
            double ty1 = Y;
            double rx1 = area.X;
            double ry1 = area.Y;
            double tx2 = tx1; tx2 += Width;
            double ty2 = ty1; ty2 += Height;
            double rx2 = rx1; rx2 += area.Width;
            double ry2 = ry1; ry2 += area.Height;
            if (tx1 < rx1) tx1 = rx1;
            if (ty1 < ry1) ty1 = ry1;
            if (tx2 > rx2) tx2 = rx2;
            if (ty2 > ry2) ty2 = ry2;
            tx2 -= tx1;
            ty2 -= ty1;
            if (tx2 < Int32.MinValue) tx2 = Int32.MaxValue;
            if (ty2 < Int32.MinValue) ty2 = Int32.MaxValue;

            if (tx1 > 0 && tx2 > 0 && ty1 > 0 && ty2 > 0)
                return true;
            return false;
        }

        public bool Contains(double x1, double y1, double x2, double y2)
        {
            if (X <= x1 && x1 <= X + Width)
                if (X <= x2 && x2 <= X + Width)
                    if (Y <= y1 && y1 <= Y + Height)
                        if (Y <= y2 && y2 <= Y + Height)
                            return true;
            return false;
        }


        public bool Contains(double x, double y)
        {
            if (X <= x && x <= X + Width)
                if (Y <= y && y <= Y + Height)
                    return true;
            return false;
        }

        public override string ToString()
        {
            return string.Format("AREA: [{0}, {1}]-[{2}, {3}]", X, Y, X + Width, Y + Height);
        }
    }
}

RTreeConfig.cs

namespace GraphAnalyzer.RTree
{
    public class RTreeConfig
    {
        private static RTreeConfig _instance;
        private static readonly object Sync = new object();
        private RTreeConfig() { }

        public static RTreeConfig Instance
        {
            get
            {
                lock (Sync)
                    if (_instance == null)
                        _instance = new RTreeConfig();
                return _instance;
            }
        }

        public int ZOrderGrid { get { return 128; } }
        public int MinimumChildren { get { return (TreeOrder + 1) / 2; } }
        public int TreeOrder { get { return 39; } }
    }
}

RTreeNode.cs

using System;
using System.Collections.Generic;

namespace GraphAnalyzer.RTree
{
    public class RTreeNode<T>
    {
        public RTreeNode<T> Parent;
        public IList<RTreeNode<T>> Children { get; set; }
        public IRTreeEdge<T> RTreeEdge { get; set; }
        private RTreeArea _rTreeArea;

        public RTreeNode()
        {
            Children = new List<RTreeNode<T>>(RTreeConfig.Instance.TreeOrder);
            _rTreeArea = new RTreeArea();
        }

        public bool HasChildren()
        {
            return Children.Count != 0;
        }

        public bool IsFull()
        {
            return Children.Count == RTreeConfig.Instance.TreeOrder;
        }

        public RTreeArea RTreeArea
        {
            get { return _rTreeArea; }
            set { _rTreeArea = value; }
        }

        public void CalculateArea()
        {
            if (Children.Count == 0)
                return;

            double minX = Children[0].RTreeArea.X;
            double minY = Children[0].RTreeArea.Y;
            double maxX = Children[0].RTreeArea.X + Children[0].RTreeArea.Width;
            double maxY = Children[0].RTreeArea.Y + Children[0].RTreeArea.Height;

            foreach (var rTreeNode in Children)
            {
                if (minX > rTreeNode.RTreeArea.X) minX = rTreeNode.RTreeArea.X;
                if (minY > rTreeNode.RTreeArea.Y) minY = rTreeNode.RTreeArea.Y;
                if (maxX < (rTreeNode.RTreeArea.X + rTreeNode.RTreeArea.Width)) maxX = rTreeNode.RTreeArea.X + rTreeNode.RTreeArea.Width;
                if (maxY < (rTreeNode.RTreeArea.Y + rTreeNode.RTreeArea.Height)) maxY = rTreeNode.RTreeArea.Y + rTreeNode.RTreeArea.Height;
            }

            _rTreeArea = new RTreeArea { X = minX, Y = minY, Width = Math.Abs(minX - maxX), Height = Math.Abs(minY - maxY) };
        }

        public override string ToString()
        {
            return string.Format("[{0}, {1}] - {2} - [{3}, {4}] >> {5}",
                                 RTreeEdge.FromRTreePoint.X, RTreeEdge.FromRTreePoint.Y, RTreeEdge.Value, RTreeEdge.ToRTreePoint.X, RTreeEdge.ToRTreePoint.Y, RTreeArea);
        }
    }
}