Index: src/Common/NetTopologySuite/Algorithm/LineIntersector.cs
===================================================================
diff -u -r8f6ae890fed8e8eae3a32f9c0498a10f82e0ddf9 -r5fc71a385897af92ccb092f2f969b5709afab85a
--- src/Common/NetTopologySuite/Algorithm/LineIntersector.cs (.../LineIntersector.cs) (revision 8f6ae890fed8e8eae3a32f9c0498a10f82e0ddf9)
+++ src/Common/NetTopologySuite/Algorithm/LineIntersector.cs (.../LineIntersector.cs) (revision 5fc71a385897af92ccb092f2f969b5709afab85a)
@@ -15,95 +15,33 @@
/// that the input coordinates have been made precise by scaling them to
/// an integer grid.)
///
- public abstract class LineIntersector
+ public abstract class LineIntersector
{
///
///
///
public const int DontIntersect = 0;
-
+
///
///
///
public const int DoIntersect = 1;
-
+
///
///
///
public const int Collinear = 2;
- ///
- /// Computes the "edge distance" of an intersection point p along a segment.
- /// The edge distance is a metric of the point along the edge.
- /// The metric used is a robust and easy to compute metric function.
- /// It is not equivalent to the usual Euclidean metric.
- /// It relies on the fact that either the x or the y ordinates of the
- /// points in the edge are unique, depending on whether the edge is longer in
- /// the horizontal or vertical direction.
- /// NOTE: This function may produce incorrect distances
- /// for inputs where p is not precisely on p1-p2
- /// (E.g. p = (139,9) p1 = (139,10), p2 = (280,1) produces distanct 0.0, which is incorrect.
- /// My hypothesis is that the function is safe to use for points which are the
- /// result of rounding points which lie on the line, but not safe to use for truncated points.
- ///
- public static double ComputeEdgeDistance(ICoordinate p, ICoordinate p0, ICoordinate p1)
- {
- double dx = Math.Abs(p1.X - p0.X);
- double dy = Math.Abs(p1.Y - p0.Y);
-
- double dist = -1.0; // sentinel value
- if (p.Equals(p0))
- dist = 0.0;
- else if (p.Equals(p1))
- {
- if (dx > dy)
- dist = dx;
- else dist = dy;
- }
- else
- {
- double pdx = Math.Abs(p.X - p0.X);
- double pdy = Math.Abs(p.Y - p0.Y);
- if (dx > dy)
- dist = pdx;
- else dist = pdy;
-
- // : hack to ensure that non-endpoints always have a non-zero distance
- if (dist == 0.0 && ! p.Equals(p0))
- dist = Math.Max(pdx, pdy);
-
- }
- Assert.IsTrue(!(dist == 0.0 && ! p.Equals(p0)), "Bad distance calculation");
- return dist;
- }
-
///
- /// This function is non-robust, since it may compute the square of large numbers.
- /// Currently not sure how to improve this.
- ///
- ///
- ///
- ///
- ///
- public static double NonRobustComputeEdgeDistance(ICoordinate p, ICoordinate p1, ICoordinate p2)
- {
- double dx = p.X - p1.X;
- double dy = p.Y - p1.Y;
- double dist = Math.Sqrt(dx * dx + dy * dy); // dummy value
- Assert.IsTrue(! (dist == 0.0 && ! p.Equals(p1)), "Invalid distance calculation");
- return dist;
- }
-
- ///
///
///
protected int result;
-
+
///
///
///
protected ICoordinate[,] inputLines = new ICoordinate[2, 2];
-
+
///
///
///
@@ -119,12 +57,12 @@
///
///
protected bool isProper;
-
+
///
///
///
protected ICoordinate pa;
-
+
///
///
///
@@ -139,7 +77,7 @@
///
///
///
- public LineIntersector()
+ public LineIntersector()
{
intPt[0] = new Coordinate();
intPt[1] = new Coordinate();
@@ -154,7 +92,7 @@
///
[Obsolete("Use PrecisionModel instead")]
public IPrecisionModel MakePrecise
- {
+ {
set
{
precisionModel = value;
@@ -166,130 +104,168 @@
/// No getter is provided, because the precision model is not required to be specified.
///
public IPrecisionModel PrecisionModel
- {
+ {
set
{
- this.precisionModel = value;
+ precisionModel = value;
}
}
///
- /// Compute the intersection of a point p and the line p1-p2.
- /// This function computes the bool value of the hasIntersection test.
- /// The actual value of the intersection (if there is one)
- /// is equal to the value of p.
+ /// Tests whether the input geometries intersect.
///
- public abstract void ComputeIntersection(ICoordinate p, ICoordinate p1, ICoordinate p2);
-
- ///
- ///
- ///
- protected bool IsCollinear
+ /// true if the input geometries intersect.
+ public bool HasIntersection
{
get
{
- return result == Collinear;
+ return result != DontIntersect;
}
}
///
- /// Computes the intersection of the lines p1-p2 and p3-p4.
- /// This function computes both the bool value of the hasIntersection test
- /// and the (approximate) value of the intersection point itself (if there is one).
+ /// Returns the number of intersection points found. This will be either 0, 1 or 2.
///
- public void ComputeIntersection(ICoordinate p1, ICoordinate p2, ICoordinate p3, ICoordinate p4)
+ public int IntersectionNum
{
- inputLines[0,0] = p1;
- inputLines[0,1] = p2;
- inputLines[1,0] = p3;
- inputLines[1,1] = p4;
- result = ComputeIntersect(p1, p2, p3, p4);
+ get
+ {
+ return result;
+ }
}
///
- ///
+ /// Tests whether an intersection is proper.
+ /// The intersection between two line segments is considered proper if
+ /// they intersect in a single point in the interior of both segments
+ /// (e.g. the intersection is a single point and is not equal to any of the endpoints).
+ /// The intersection between a point and a line segment is considered proper
+ /// if the point lies in the interior of the segment (e.g. is not equal to either of the endpoints).
///
- ///
- ///
- ///
- ///
- ///
- public abstract int ComputeIntersect(ICoordinate p1, ICoordinate p2, ICoordinate q1, ICoordinate q2);
-
- ///
- ///
- ///
- ///
- public override string ToString()
+ /// true if the intersection is proper.
+ public bool IsProper
{
- StringBuilder sb = new StringBuilder();
- sb.Append(inputLines[0, 0]).Append("-");
- sb.Append(inputLines[0, 1]).Append(" ");
- sb.Append(inputLines[1, 0]).Append("-");
- sb.Append(inputLines[1, 1]).Append(" : ");
-
- if (IsEndPoint) sb.Append(" endpoint");
- if (isProper) sb.Append(" proper");
- if (IsCollinear) sb.Append(" collinear");
-
- return sb.ToString();
- }
-
- ///
- ///
- ///
- protected bool IsEndPoint
- {
get
{
- return HasIntersection && !isProper;
+ return HasIntersection && isProper;
}
}
///
- /// Tests whether the input geometries intersect.
+ /// Computes the "edge distance" of an intersection point p along a segment.
+ /// The edge distance is a metric of the point along the edge.
+ /// The metric used is a robust and easy to compute metric function.
+ /// It is not equivalent to the usual Euclidean metric.
+ /// It relies on the fact that either the x or the y ordinates of the
+ /// points in the edge are unique, depending on whether the edge is longer in
+ /// the horizontal or vertical direction.
+ /// NOTE: This function may produce incorrect distances
+ /// for inputs where p is not precisely on p1-p2
+ /// (E.g. p = (139,9) p1 = (139,10), p2 = (280,1) produces distanct 0.0, which is incorrect.
+ /// My hypothesis is that the function is safe to use for points which are the
+ /// result of rounding points which lie on the line, but not safe to use for truncated points.
///
- /// true if the input geometries intersect.
- public bool HasIntersection
+ public static double ComputeEdgeDistance(ICoordinate p, ICoordinate p0, ICoordinate p1)
{
- get
+ double dx = Math.Abs(p1.X - p0.X);
+ double dy = Math.Abs(p1.Y - p0.Y);
+
+ double dist = -1.0; // sentinel value
+ if (p.Equals(p0))
{
- return result != DontIntersect;
+ dist = 0.0;
}
+ else if (p.Equals(p1))
+ {
+ if (dx > dy)
+ {
+ dist = dx;
+ }
+ else
+ {
+ dist = dy;
+ }
+ }
+ else
+ {
+ double pdx = Math.Abs(p.X - p0.X);
+ double pdy = Math.Abs(p.Y - p0.Y);
+ if (dx > dy)
+ {
+ dist = pdx;
+ }
+ else
+ {
+ dist = pdy;
+ }
+
+ // : hack to ensure that non-endpoints always have a non-zero distance
+ if (dist == 0.0 && !p.Equals(p0))
+ {
+ dist = Math.Max(pdx, pdy);
+ }
+ }
+ Assert.IsTrue(!(dist == 0.0 && !p.Equals(p0)), "Bad distance calculation");
+ return dist;
}
///
- /// Returns the number of intersection points found. This will be either 0, 1 or 2.
+ /// This function is non-robust, since it may compute the square of large numbers.
+ /// Currently not sure how to improve this.
///
- public int IntersectionNum
+ ///
+ ///
+ ///
+ ///
+ public static double NonRobustComputeEdgeDistance(ICoordinate p, ICoordinate p1, ICoordinate p2)
{
- get
- {
- return result;
- }
+ double dx = p.X - p1.X;
+ double dy = p.Y - p1.Y;
+ double dist = Math.Sqrt(dx*dx + dy*dy); // dummy value
+ Assert.IsTrue(!(dist == 0.0 && !p.Equals(p1)), "Invalid distance calculation");
+ return dist;
}
///
- /// Returns the intIndex'th intersection point.
+ /// Compute the intersection of a point p and the line p1-p2.
+ /// This function computes the bool value of the hasIntersection test.
+ /// The actual value of the intersection (if there is one)
+ /// is equal to the value of p.
///
- /// is 0 or 1.
- /// The intIndex'th intersection point.
- public ICoordinate GetIntersection(int intIndex)
- {
- return intPt[intIndex];
+ public abstract void ComputeIntersection(ICoordinate p, ICoordinate p1, ICoordinate p2);
+
+ ///
+ /// Computes the intersection of the lines p1-p2 and p3-p4.
+ /// This function computes both the bool value of the hasIntersection test
+ /// and the (approximate) value of the intersection point itself (if there is one).
+ ///
+ public void ComputeIntersection(ICoordinate p1, ICoordinate p2, ICoordinate p3, ICoordinate p4)
+ {
+ inputLines[0, 0] = p1;
+ inputLines[0, 1] = p2;
+ inputLines[1, 0] = p3;
+ inputLines[1, 1] = p4;
+ result = ComputeIntersect(p1, p2, p3, p4);
}
///
///
///
- protected void ComputeIntLineIndex()
+ ///
+ ///
+ ///
+ ///
+ ///
+ public abstract int ComputeIntersect(ICoordinate p1, ICoordinate p2, ICoordinate q1, ICoordinate q2);
+
+ ///
+ /// Returns the intIndex'th intersection point.
+ ///
+ /// is 0 or 1.
+ /// The intIndex'th intersection point.
+ public ICoordinate GetIntersection(int intIndex)
{
- if (intLineIndex == null)
- {
- intLineIndex = new int[2, 2];
- ComputeIntLineIndex(0);
- ComputeIntLineIndex(1);
- }
+ return intPt[intIndex];
}
///
@@ -299,11 +275,15 @@
/// It does not return true if the input point is internal to the intersection segment.
///
/// true if the input point is one of the intersection points.
- public bool IsIntersection(ICoordinate pt)
+ public bool IsIntersection(ICoordinate pt)
{
- for (int i = 0; i < result; i++)
- if (intPt[i].Equals2D(pt))
- return true;
+ for (int i = 0; i < result; i++)
+ {
+ if (intPt[i].Equals2D(pt))
+ {
+ return true;
+ }
+ }
return false;
}
@@ -315,10 +295,14 @@
///
public bool IsInteriorIntersection()
{
- if (IsInteriorIntersection(0))
+ if (IsInteriorIntersection(0))
+ {
return true;
- if (IsInteriorIntersection(1))
+ }
+ if (IsInteriorIntersection(1))
+ {
return true;
+ }
return false;
}
@@ -331,27 +315,14 @@
public bool IsInteriorIntersection(int inputLineIndex)
{
for (int i = 0; i < result; i++)
- if (!(intPt[i].Equals2D(inputLines[inputLineIndex, 0]) ||
- intPt[i].Equals2D(inputLines[inputLineIndex, 1])))
- return true;
- return false;
- }
-
- ///
- /// Tests whether an intersection is proper.
- /// The intersection between two line segments is considered proper if
- /// they intersect in a single point in the interior of both segments
- /// (e.g. the intersection is a single point and is not equal to any of the endpoints).
- /// The intersection between a point and a line segment is considered proper
- /// if the point lies in the interior of the segment (e.g. is not equal to either of the endpoints).
- ///
- /// true if the intersection is proper.
- public bool IsProper
- {
- get
{
- return HasIntersection && isProper;
+ if (!(intPt[i].Equals2D(inputLines[inputLineIndex, 0]) ||
+ intPt[i].Equals2D(inputLines[inputLineIndex, 1])))
+ {
+ return true;
+ }
}
+ return false;
}
///
@@ -363,7 +334,7 @@
///
/// The intIndex'th intersection point in the direction of the specified input line segment.
///
- public ICoordinate GetIntersectionAlongSegment(int segmentIndex, int intIndex)
+ public ICoordinate GetIntersectionAlongSegment(int segmentIndex, int intIndex)
{
// lazily compute int line array
ComputeIntLineIndex();
@@ -379,21 +350,96 @@
///
/// The index of the intersection point along the segment (0 or 1).
///
- public int GetIndexAlongSegment(int segmentIndex, int intIndex)
+ public int GetIndexAlongSegment(int segmentIndex, int intIndex)
{
ComputeIntLineIndex();
return intLineIndex[segmentIndex, intIndex];
}
+ ///
+ /// Computes the "edge distance" of an intersection point along the specified input line segment.
+ ///
+ /// is 0 or 1.
+ /// is 0 or 1.
+ /// The edge distance of the intersection point.
+ public double GetEdgeDistance(int segmentIndex, int intIndex)
+ {
+ double dist = ComputeEdgeDistance(intPt[intIndex], inputLines[segmentIndex, 0], inputLines[segmentIndex, 1]);
+ return dist;
+ }
+
///
///
///
+ ///
+ public override string ToString()
+ {
+ StringBuilder sb = new StringBuilder();
+ sb.Append(inputLines[0, 0]).Append("-");
+ sb.Append(inputLines[0, 1]).Append(" ");
+ sb.Append(inputLines[1, 0]).Append("-");
+ sb.Append(inputLines[1, 1]).Append(" : ");
+
+ if (IsEndPoint)
+ {
+ sb.Append(" endpoint");
+ }
+ if (isProper)
+ {
+ sb.Append(" proper");
+ }
+ if (IsCollinear)
+ {
+ sb.Append(" collinear");
+ }
+
+ return sb.ToString();
+ }
+
+ ///
+ ///
+ ///
+ protected bool IsCollinear
+ {
+ get
+ {
+ return result == Collinear;
+ }
+ }
+
+ ///
+ ///
+ ///
+ protected bool IsEndPoint
+ {
+ get
+ {
+ return HasIntersection && !isProper;
+ }
+ }
+
+ ///
+ ///
+ ///
+ protected void ComputeIntLineIndex()
+ {
+ if (intLineIndex == null)
+ {
+ intLineIndex = new int[2, 2];
+ ComputeIntLineIndex(0);
+ ComputeIntLineIndex(1);
+ }
+ }
+
+ ///
+ ///
+ ///
///
- protected void ComputeIntLineIndex(int segmentIndex)
+ protected void ComputeIntLineIndex(int segmentIndex)
{
double dist0 = GetEdgeDistance(segmentIndex, 0);
double dist1 = GetEdgeDistance(segmentIndex, 1);
- if (dist0 > dist1)
+ if (dist0 > dist1)
{
intLineIndex[segmentIndex, 0] = 0;
intLineIndex[segmentIndex, 1] = 1;
@@ -404,17 +450,5 @@
intLineIndex[segmentIndex, 1] = 0;
}
}
-
- ///
- /// Computes the "edge distance" of an intersection point along the specified input line segment.
- ///
- /// is 0 or 1.
- /// is 0 or 1.
- /// The edge distance of the intersection point.
- public double GetEdgeDistance(int segmentIndex, int intIndex)
- {
- double dist = ComputeEdgeDistance(intPt[intIndex], inputLines[segmentIndex, 0], inputLines[segmentIndex, 1]);
- return dist;
- }
}
}
\ No newline at end of file