Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement