Enhanced C#
Language of your choice: library documentation
Static Public Member Functions | List of all members
Loyc.Geometry.LineMath Class Reference

Contains algorithms that operate on lines. More...


Source files:

Remarks

Contains algorithms that operate on lines.

Static Public Member Functions

static T Length< T > (this LineSegment< T > seg)
 
static int SimplifyPolyline< List > (List points, ICollection< Point< float >> output, float tolerance)
 Simplifies a polyline using the Douglas-Peucker line simplification algorithm. This algorithm removes points that are deemed unimportant; the output is a subset of the input. More...
 
static List< Point< float > > SimplifyPolyline< List > (List points, float tolerance)
 
static int SimplifyPolyline< List > (List points, ICollection< Point< double >> output, double tolerance)
 
static List< Point< double > > SimplifyPolyline< List > (List points, double tolerance)
 
static int SimplifyPolyline< List, Point, T > (List points, ICollection< Point > output, T tolerance, Func< Point, Point, Point, T > distanceToLine, bool inRecursion=false)
 
static Point ProjectOnto (this Point p, LineSegment seg, LineType type=LineType.Segment)
 Performs projection, which finds the point on a line segment or infinite line that is nearest to a specified point. More...
 
static Point ProjectOnto (this Point p, LineSegment seg, LineType type, out int?end)
 
static Point ProjectOntoInfiniteLine (this Point p, LineSegment seg)
 
static Point ProjectOnto (this Point p, LineSegment seg)
 
static T GetFractionAlong (this Point p, LineSegment seg, LineType type=LineType.Segment)
 Gets the projection of a point onto a line, expressed as a fraction where 0 represents the start of the line and 1 represents the end of the line. More...
 
static T GetFractionAlong (this Point p, LineSegment seg, LineType type, out int?end)
 
static Point PointAlong (this LineSegment seg, T frac)
 Given a fraction between zero and one, calculates a point between two points (0=point A, 1=point B, 0.5=midpoint). More...
 
static Point Midpoint (this LineSegment seg)
 Returns the midpoint, (A + B) >> 1. More...
 
static T QuadranceTo (this Point p, LineSegment seg)
 
static T QuadranceTo (this Point p, LineSegment seg, LineType type)
 
static T DistanceTo (this Point p, LineSegment seg, LineType type=LineType.Segment)
 
static T Length (this LineSegment seg)
 
static bool ComputeIntersection (this LineSegment P, LineType pType, out T pFrac, LineSegment Q, LineType qType, out T qFrac)
 Computes the location that lines, rays or line segments intersect, expressed as a fraction of the distance along each LineSegment. More...
 
static bool ComputeIntersection (this LineSegment P, LineSegment Q, out T pFrac, LineType type=LineType.Segment)
 
static Point ComputeIntersection (this LineSegment P, LineType pType, LineSegment Q, LineType qType)
 Computes the intersection point between two lines, rays or line segments. More...
 
static Point ComputeIntersection (this LineSegment P, LineSegment Q, LineType type=LineType.Segment)
 
static LineSegment ClipTo (this LineSegment seg, BoundingBox< T > bbox)
 Quickly clips a line to a bounding box. More...
 
static Point ProjectOnto (this Point p, LineSegment seg, LineType type=LineType.Segment)
 Performs projection, which finds the point on a line segment or infinite line that is nearest to a specified point. More...
 
static Point ProjectOnto (this Point p, LineSegment seg, LineType type, out int?end)
 
static Point ProjectOntoInfiniteLine (this Point p, LineSegment seg)
 
static Point ProjectOnto (this Point p, LineSegment seg)
 
static T GetFractionAlong (this Point p, LineSegment seg, LineType type=LineType.Segment)
 Gets the projection of a point onto a line, expressed as a fraction where 0 represents the start of the line and 1 represents the end of the line. More...
 
static T GetFractionAlong (this Point p, LineSegment seg, LineType type, out int?end)
 
static Point PointAlong (this LineSegment seg, T frac)
 Given a fraction between zero and one, calculates a point between two points (0=point A, 1=point B, 0.5=midpoint). More...
 
static Point Midpoint (this LineSegment seg)
 Returns the midpoint, (A + B) >> 1. More...
 
static T QuadranceTo (this Point p, LineSegment seg)
 
static T QuadranceTo (this Point p, LineSegment seg, LineType type)
 
static T DistanceTo (this Point p, LineSegment seg, LineType type=LineType.Segment)
 
static T Length (this LineSegment seg)
 
static bool ComputeIntersection (this LineSegment P, LineType pType, out T pFrac, LineSegment Q, LineType qType, out T qFrac)
 Computes the location that lines, rays or line segments intersect, expressed as a fraction of the distance along each LineSegment. More...
 
static bool ComputeIntersection (this LineSegment P, LineSegment Q, out T pFrac, LineType type=LineType.Segment)
 
static Point ComputeIntersection (this LineSegment P, LineType pType, LineSegment Q, LineType qType)
 Computes the intersection point between two lines, rays or line segments. More...
 
static Point ComputeIntersection (this LineSegment P, LineSegment Q, LineType type=LineType.Segment)
 
static LineSegment ClipTo (this LineSegment seg, BoundingBox< T > bbox)
 Quickly clips a line to a bounding box. More...
 

Member Function Documentation

static LineSegment Loyc.Geometry.LineMath.ClipTo ( this LineSegment  seg,
BoundingBox< T >  bbox 
)
inlinestatic

Quickly clips a line to a bounding box.

Returns
A clipped line, or null if the line was outside the bounding box.

If the bounding box is not normalized (min > max), the result is undefined.

static LineSegment Loyc.Geometry.LineMath.ClipTo ( this LineSegment  seg,
BoundingBox< T >  bbox 
)
inlinestatic

Quickly clips a line to a bounding box.

Returns
A clipped line, or null if the line was outside the bounding box.

If the bounding box is not normalized (min > max), the result is undefined.

static bool Loyc.Geometry.LineMath.ComputeIntersection ( this LineSegment  P,
LineType  pType,
out T  pFrac,
LineSegment  Q,
LineType  qType,
out T  qFrac 
)
inlinestatic

Computes the location that lines, rays or line segments intersect, expressed as a fraction of the distance along each LineSegment.

Parameters
PFirst line segment
pTypeType of line P (Segment, Ray, Infinite)
pFracFraction along P of the intersection point. If this method returns false, pFrac is still computed. If the hypothetical intersection point of the infinite extension of P and Q is beyond the P.A side of the line, pFrac is set to an appropriate negative value if pType is Infinite and 0 otherwise. If the hypothetical intersection is on the P.B side of the line, pFrac is set to 1 if pType is Segment and a value above 1 otherwise.
QSecond line segment
qTypeType of line Q (Segment, Ray, Infinite)
qFracFraction along Q of the intersection point. If this method returns false, qFrac may be NaN if the analysis of line P already determined that pFrac is beyond the range of line P. In other words, if Q is assumed to be an infinite line and P still does not intersect with Q, qFrac is set to NaN because the method aborts analysis to avoid wasting CPU time. On the other hand, if this method determines that P might intersect with Q, but a full analysis shows that it does not, the method returns false and sets qFrac to a real number. qFrac is set to 0 if the intersection point of the infinite extension of Q is on the Q.A side of the line, and 1 if the intersection point is on the Q.B side of the line.
Returns
True if the lines intersect, false otherwise.

This method does not do a bounding-box check. If you are doing calculations with line segments and you expect the majority of your intersection calculations to return false, you may save time by testing whether the bounding boxes of the lines overlap before calling this method.

If the input segments contain NaNs, the result is false and pFrac/qFrac will be NaN.

If the either of the line segments are degenerate (single points), overlap can still be detected and the LineType of the degenerate line has no effect; the degenerate line is always treated as a point. If both lines are points, the method will return true iff they are the same point, and if true is returned, pFrac will be 0.5f

The output fractions pFrac and qFrac will be infinite if the magnitude of the result overflows.

If the two line segments are parallel but do not overlap, this method returns false; pFrac and qFrac are both set to NaN. If the two lines are parallel and overlap, a region of overlap is detected and pFrac and qFrac refer to the center of this region of overlap. If, in this case, P and/or Q are rays or infinite lines, this method behaves as though P and/or Q are extended to cover each other. For instance, suppose that P and Q are lines on the X axis, P.A.X=0, P.B.X=6, Q.A.X=10, Q.B.X=16:

       P.A---------------P.B         Q.B---------------------Q.A
-2  -1  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17

If P and Q are both line segments, there is no overlap and this method will return false. However, if Q is a Ray or an infinite line, it extends toward negative infinity and the minimum overlap between the lines is 0..6. In this case, the region of overlap is considered to be 0..6 if P is a line segment, and 0..16 if P is a ray or an infinite line. If P is a line segment, the midpoint is 3, and pFrac will be set to 0.5, halfway along the line, while qFrac will be 2.333. If P is a ray or an infinite line, the midpoint is 8, pFrac will be 1.333, and qFrac will be 1.333.

static Point Loyc.Geometry.LineMath.ComputeIntersection ( this LineSegment  P,
LineType  pType,
LineSegment  Q,
LineType  qType 
)
inlinestatic

Computes the intersection point between two lines, rays or line segments.

This method is implemented based on the other overload, ComputeIntersection(LineSegment, LineType, out T, LineSegment, LineType, out T).

static bool Loyc.Geometry.LineMath.ComputeIntersection ( this LineSegment  P,
LineType  pType,
out T  pFrac,
LineSegment  Q,
LineType  qType,
out T  qFrac 
)
inlinestatic

Computes the location that lines, rays or line segments intersect, expressed as a fraction of the distance along each LineSegment.

Parameters
PFirst line segment
pTypeType of line P (Segment, Ray, Infinite)
pFracFraction along P of the intersection point. If this method returns false, pFrac is still computed. If the hypothetical intersection point of the infinite extension of P and Q is beyond the P.A side of the line, pFrac is set to an appropriate negative value if pType is Infinite and 0 otherwise. If the hypothetical intersection is on the P.B side of the line, pFrac is set to 1 if pType is Segment and a value above 1 otherwise.
QSecond line segment
qTypeType of line Q (Segment, Ray, Infinite)
qFracFraction along Q of the intersection point. If this method returns false, qFrac may be NaN if the analysis of line P already determined that pFrac is beyond the range of line P. In other words, if Q is assumed to be an infinite line and P still does not intersect with Q, qFrac is set to NaN because the method aborts analysis to avoid wasting CPU time. On the other hand, if this method determines that P might intersect with Q, but a full analysis shows that it does not, the method returns false and sets qFrac to a real number. qFrac is set to 0 if the intersection point of the infinite extension of Q is on the Q.A side of the line, and 1 if the intersection point is on the Q.B side of the line.
Returns
True if the lines intersect, false otherwise.

This method does not do a bounding-box check. If you are doing calculations with line segments and you expect the majority of your intersection calculations to return false, you may save time by testing whether the bounding boxes of the lines overlap before calling this method.

If the input segments contain NaNs, the result is false and pFrac/qFrac will be NaN.

If the either of the line segments are degenerate (single points), overlap can still be detected and the LineType of the degenerate line has no effect; the degenerate line is always treated as a point. If both lines are points, the method will return true iff they are the same point, and if true is returned, pFrac will be 0.5f

The output fractions pFrac and qFrac will be infinite if the magnitude of the result overflows.

If the two line segments are parallel but do not overlap, this method returns false; pFrac and qFrac are both set to NaN. If the two lines are parallel and overlap, a region of overlap is detected and pFrac and qFrac refer to the center of this region of overlap. If, in this case, P and/or Q are rays or infinite lines, this method behaves as though P and/or Q are extended to cover each other. For instance, suppose that P and Q are lines on the X axis, P.A.X=0, P.B.X=6, Q.A.X=10, Q.B.X=16:

       P.A---------------P.B         Q.B---------------------Q.A
-2  -1  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17

If P and Q are both line segments, there is no overlap and this method will return false. However, if Q is a Ray or an infinite line, it extends toward negative infinity and the minimum overlap between the lines is 0..6. In this case, the region of overlap is considered to be 0..6 if P is a line segment, and 0..16 if P is a ray or an infinite line. If P is a line segment, the midpoint is 3, and pFrac will be set to 0.5, halfway along the line, while qFrac will be 2.333. If P is a ray or an infinite line, the midpoint is 8, pFrac will be 1.333, and qFrac will be 1.333.

static Point Loyc.Geometry.LineMath.ComputeIntersection ( this LineSegment  P,
LineType  pType,
LineSegment  Q,
LineType  qType 
)
inlinestatic

Computes the intersection point between two lines, rays or line segments.

This method is implemented based on the other overload, ComputeIntersection(LineSegment, LineType, out T, LineSegment, LineType, out T).

static T Loyc.Geometry.LineMath.GetFractionAlong ( this Point  p,
LineSegment  seg,
LineType  type = LineType.Segment 
)
inlinestatic

Gets the projection of a point onto a line, expressed as a fraction where 0 represents the start of the line and 1 represents the end of the line.

Parameters
infiniteLineWhether to return numbers outside the range (0, 1) if the projection is outside the line segment. If this is false, the result is clamped to (0, 1)
endSame as for ProjectOnto.
Returns
The fraction of p along seg, as explained already. If seg is zero-length, the result is always 0.

This method uses the same technique as ProjectOnto.

static T Loyc.Geometry.LineMath.GetFractionAlong ( this Point  p,
LineSegment  seg,
LineType  type = LineType.Segment 
)
inlinestatic

Gets the projection of a point onto a line, expressed as a fraction where 0 represents the start of the line and 1 represents the end of the line.

Parameters
infiniteLineWhether to return numbers outside the range (0, 1) if the projection is outside the line segment. If this is false, the result is clamped to (0, 1)
endSame as for ProjectOnto.
Returns
The fraction of p along seg, as explained already. If seg is zero-length, the result is always 0.

This method uses the same technique as ProjectOnto.

static Point Loyc.Geometry.LineMath.Midpoint ( this LineSegment  seg)
inlinestatic

Returns the midpoint, (A + B) >> 1.

static Point Loyc.Geometry.LineMath.Midpoint ( this LineSegment  seg)
inlinestatic

Returns the midpoint, (A + B) >> 1.

static Point Loyc.Geometry.LineMath.PointAlong ( this LineSegment  seg,
frac 
)
inlinestatic

Given a fraction between zero and one, calculates a point between two points (0=point A, 1=point B, 0.5=midpoint).

If you just want the midpoint, call Midpoint() which is faster. If the fraction is outside the range [0,1], the result will be along the infinite extension of the line. If the two points are the same, this method always returns the same point as long as the math doesn't overflow, possibly with slight deviations caused by floating-point rounding.

static Point Loyc.Geometry.LineMath.PointAlong ( this LineSegment  seg,
frac 
)
inlinestatic

Given a fraction between zero and one, calculates a point between two points (0=point A, 1=point B, 0.5=midpoint).

If you just want the midpoint, call Midpoint() which is faster. If the fraction is outside the range [0,1], the result will be along the infinite extension of the line. If the two points are the same, this method always returns the same point as long as the math doesn't overflow, possibly with slight deviations caused by floating-point rounding.

static Point Loyc.Geometry.LineMath.ProjectOnto ( this Point  p,
LineSegment  seg,
LineType  type = LineType.Segment 
)
inlinestatic

Performs projection, which finds the point on a line segment or infinite line that is nearest to a specified point.

Parameters
segThe line segment
pThe test point to be projected
infiniteLineWhether to extend the line infinitely.
endSet to 0 if the point is on the line segment (including one of the endpoints), -1 if the point is before seg.A, 1 if the point is after seg.B, and null if the line segment is degenerate (seg.A==seg.B)
Returns
The projected point.

This algorithm is fast and accurate, and can be easily adapted to 3D. A special advantage of this approach is that it runs fastest when the point is projected onto one of the endpoints (when infiniteLine is false).

Algorithm comes from: http://geomalgorithms.com/a02-_lines.html See section "Distance of a Point to a Ray or Segment"

static Point Loyc.Geometry.LineMath.ProjectOnto ( this Point  p,
LineSegment  seg,
LineType  type = LineType.Segment 
)
inlinestatic

Performs projection, which finds the point on a line segment or infinite line that is nearest to a specified point.

Parameters
segThe line segment
pThe test point to be projected
infiniteLineWhether to extend the line infinitely.
endSet to 0 if the point is on the line segment (including one of the endpoints), -1 if the point is before seg.A, 1 if the point is after seg.B, and null if the line segment is degenerate (seg.A==seg.B)
Returns
The projected point.

This algorithm is fast and accurate, and can be easily adapted to 3D. A special advantage of this approach is that it runs fastest when the point is projected onto one of the endpoints (when infiniteLine is false).

Algorithm comes from: http://geomalgorithms.com/a02-_lines.html See section "Distance of a Point to a Ray or Segment"

static int Loyc.Geometry.LineMath.SimplifyPolyline< List > ( List  points,
ICollection< Point< float >>  output,
float  tolerance 
)
inlinestatic

Simplifies a polyline using the Douglas-Peucker line simplification algorithm. This algorithm removes points that are deemed unimportant; the output is a subset of the input.

Template Parameters
ListOriginal unsimplified polyline
Parameters
outputThe output polyline is added in order to this collection
toleranceThe distance between the input polyline and the output polyline will never exceed this distance. Increase this value to simplify more aggressively.
Returns
The number of output points.

The average time complexity of this algorithm is O(N log N). The worst-case time complexity is O(N^2).

Type Constraints
List :IListSource 
List :Point<float>