broken-optimized-locator.cs

using System;
using System.Collections;
using System.Collections.Generic;

using GeoAPI.Geometries;
using NetTopologySuite.Geometries.Utilities;

namespace NetTopologySuite.Algorithm.Locate
{
    public class OptimizedIndexedPointInAreaLocator : IPointOnGeometryLocator
    {
        private readonly CustomIntervalRTree tree;

        public OptimizedIndexedPointInAreaLocator(IGeometry g)
        {
            if (!(g is IPolygonal))
            {
                throw new ArgumentException("Argument must be Polygonal");
            }

            this.tree = new CustomIntervalRTree(g);
        }

        public Location Locate(Coordinate p)
        {
            RayCrossingCounter rcc = new RayCrossingCounter(p);
            this.tree.Count(p.Y, rcc);
            /*
            Coordinate p0 = new Coordinate();
            Coordinate p1 = new Coordinate();
            foreach (var ln in this.tree.leafNodes)
            {
                if (!ln.Range.Contains(p.Y))
                {
                    continue;
                }

                p0.Y = ln.Range.MinY;
                p0.X = ln.ForMinY;

                p1.Y = ln.Range.MaxY;
                p1.X = ln.ForMaxY;
                rcc.CountSegment(p0, p1);
            }*/

            return rcc.Location;
        }

        private sealed class CustomIntervalRTree
        {
            internal readonly LeafNode[] leafNodes;

            private readonly BranchNode[] branchNodes;

            public CustomIntervalRTree(IGeometry geometry)
            {
                List<LeafNode> leafNodes = new List<LeafNode>();
                foreach (ILineString line in LinearComponentExtracter.GetLines(geometry))
                {
                    Coordinate[] pts = line.Coordinates;
                    for (int i = 1; i < pts.Length; i++)
                    {
                        Coordinate p0 = pts[i - 1];
                        Coordinate p1 = pts[i];

                        LeafNode leafNode;
                        if (p0.Y <= p1.Y)
                        {
                            leafNode = new LeafNode
                                       {
                                           Range =
                                           {
                                               MinY = p0.Y,
                                               MaxY = p1.Y
                                           },
                                           ForMinY = p0.X,
                                           ForMaxY = p1.X
                                       };
                        }
                        else
                        {
                            leafNode = new LeafNode
                                       {
                                           Range =
                                           {
                                               MinY = p1.Y,
                                               MaxY = p0.Y
                                           },
                                           ForMinY = p1.X,
                                           ForMaxY = p0.X
                                       };
                        }

                        leafNodes.Add(leafNode);
                    }
                }

                if (leafNodes.Count % 2 > 0)
                {
                    leafNodes.Add(new LeafNode
                                  {
                                      Range =
                                      {
                                          MaxY = Double.NegativeInfinity,
                                          MinY = Double.PositiveInfinity
                                      }
                                  });
                }

                this.leafNodes = leafNodes.ToArray();
                Array.Sort(this.leafNodes, LeafNodeComparer.Instance);

                // Optimal would be leafNodes.Count - 1.
                // Current implementation is up to ceil(log2(leafNodes.Count)) higher than optimal.
                List<BranchNode> branchNodes = new List<BranchNode>();
                int savedB = 0;
                for (int i = 0; i < leafNodes.Count; i += 2)
                {
                    BranchNode branchNode = new BranchNode
                                            {
                                                LeftChildIndex = ~(i),
                                                RightChildIndex = ~(i + 1),
                                                Range =
                                                {
                                                    MinY = Math.Min(leafNodes[i].Range.MinY, leafNodes[i + 1].Range.MinY),
                                                    MaxY = Math.Max(leafNodes[i].Range.MaxY, leafNodes[i + 1].Range.MaxY)
                                                }
                                            };

                    branchNodes.Add(branchNode);
                }

                BranchNode[] lastRound = branchNodes.ToArray();
                while (true)
                {
                    int endRange = branchNodes.Count;

                    for (int i = savedB; i < endRange; i += 2)
                    {
                        BranchNode branchNode = new BranchNode
                                                {
                                                    LeftChildIndex = i,
                                                    RightChildIndex = i + 1,
                                                    Range =
                                                    {
                                                        MinY = Math.Min(branchNodes[i].Range.MinY, branchNodes[i + 1].Range.MinY),
                                                        MaxY = Math.Max(branchNodes[i].Range.MaxY, branchNodes[i + 1].Range.MaxY)
                                                    }
                                                };

                        branchNodes.Add(branchNode);
                    }

                    if (lastRound.Length == 2)
                    {
                        break;
                    }

                    if (branchNodes.Count % 2 > 0)
                    {
                        BranchNode branchNode = new BranchNode
                        {
                            Range =
                            {
                                MaxY = Double.NegativeInfinity,
                                MinY = Double.PositiveInfinity
                            }
                        };

                        branchNodes.Add(branchNode);
                    }

                    lastRound = branchNodes.GetRange(savedB, (endRange - savedB + 1) / 2).ToArray();
                    savedB = endRange;
                }

                this.branchNodes = branchNodes.ToArray();
            }

            public void Count(double y, RayCrossingCounter c)
            {
                this.Count(y, c, this.branchNodes.Length - 1, new Coordinate(), new Coordinate());
            }

            private void Count(double y, RayCrossingCounter c, int i, Coordinate p0, Coordinate p1)
            {
                if (i < 0)
                {
                    LeafNode l = this.leafNodes[~i];
                    if (!l.Range.Contains(y))
                    {
                        return;
                    }

                    p0.Y = l.Range.MinY;
                    p0.X = l.ForMinY;

                    p1.Y = l.Range.MaxY;
                    p1.X = l.ForMaxY;

                    c.CountSegment(p0, p1);
                }
                else
                {
                    BranchNode b = this.branchNodes[i];
                    if (!b.Range.Contains(y))
                    {
                        return;
                    }

                    this.Count(y, c, b.LeftChildIndex, p0, p1);
                    this.Count(y, c, b.RightChildIndex, p0, p1);
                }
            }
        }

        private sealed class LeafNodeComparer : Comparer<LeafNode>
        {
            internal static readonly LeafNodeComparer Instance = new LeafNodeComparer();

            public override int Compare(LeafNode x, LeafNode y)
            {
                double xRange = x.Range.MinY + x.Range.MaxY;
                double yRange = y.Range.MinY + y.Range.MaxY;
                return xRange.CompareTo(yRange);
            }
        }

        private struct BranchNode
        {
            internal Range Range;

            internal int LeftChildIndex;

            internal int RightChildIndex;

            public override string ToString()
            {
                return "Range: [" + Range + "], L: " + LeftChildIndex + ", R: " + RightChildIndex;
            }
        }

        private struct LeafNode
        {
            internal Range Range;

            internal double ForMinY;

            internal double ForMaxY;

            public override string ToString()
            {
                return "P0: (x = " + ForMinY + ", y = " + Range.MinY + "), P1: (x = " + ForMaxY + ", y = " + Range.MaxY + ")";
            }
        }

        private struct Range
        {
            internal double MinY;

            internal double MaxY;

            internal bool Contains(double y)
            {
                return y >= MinY &&
                       y <= MaxY;
            }

            public override string ToString()
            {
                return "MinY: " + MinY + ", MaxY: " + MaxY;
            }
        }
    }
}