LineSegment.cs

// AForge Math Library
// AForge.NET framework
// http://www.aforgenet.com/framework/
//
// Copyright © AForge.NET, 2007-2011
// contacts@aforgenet.com
//

namespace AForge.Math.Geometry
{
    using System;

    /// <summary>
    /// The class encapsulates 2D line segment and provides some tool methods related to lines.
    /// </summary>
    /// 
    /// <remarks><para>The class provides some methods which are related to line segments:
    /// distance to point, finding intersection point, etc.
    /// </para>
    /// 
    /// <para>A line segment may be converted to a <see cref="Line"/>.</para>
    /// 
    /// <para>Sample usage:</para>
    /// <code>
    /// // create a segment
    /// LineSegment segment = new LineSegment( new Point( 0, 0 ), new Point( 3, 4 ) );
    /// // get segment's length
    /// float length = segment.Length;
    /// 
    /// // get intersection point with a line
    /// Point? intersection = segment.GetIntersectionWith(
    ///     new Line( new Point( -3, 8 ), new Point( 0, 4 ) ) );
    /// </code>
    /// </remarks>
    /// 
    public sealed class LineSegment
    {
        // segment's start/end point
        private readonly Point start;
        private readonly Point end;

        private readonly Line line;

        /// <summary>
        /// Start point of the line segment.
        /// </summary>
        public Point Start
        {
            get { return start; }
        }

        /// <summary>
        /// End point of the line segment.
        /// </summary>
        public Point End
        {
            get { return end; }
        }

        /// <summary>
        /// Get segment's length - Euclidean distance between its <see cref="Start"/> and <see cref="End"/> points.
        /// </summary>
        public float Length
        {
            get { return start.DistanceTo( end ); }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="LineSegment"/> class.
        /// </summary>
        /// 
        /// <param name="start">Segment's start point.</param>
        /// <param name="end">Segment's end point.</param>
        /// 
        /// <exception cref="ArgumentException">Thrown if the two points are the same.</exception>
        /// 
        public LineSegment( Point start, Point end )
        {
            line = Line.FromPoints( start, end );
            this.start = start;
            this.end = end;
        }

        /// <summary>
        /// Converts this <see cref="LineSegment"/> to a <see cref="Line"/> by discarding
        /// its endpoints and extending it infinitely in both directions.
        /// </summary>
        /// 
        /// <param name="segment">The segment to convert to a <see cref="Line"/>.</param>
        /// 
        /// <returns>Returns a <see cref="Line"/> that contains this <paramref name="segment"/>.</returns>
        /// 
        public static explicit operator Line( LineSegment segment )
        {
            return segment.line;
        }

        /// <summary>
        /// Calculate Euclidean distance between a point and a finite line segment.
        /// </summary>
        /// 
        /// <param name="point">The point to calculate the distance to.</param>
        /// 
        /// <returns>Returns the Euclidean distance between this line segment and the specified point. Unlike
        /// <see cref="Line.DistanceToPoint"/>, this returns the distance from the finite segment. (0,0) is 5 units
        /// from the segment (0,5)-(0,8), but is 0 units from the line through those points.</returns>
        /// 
        public float DistanceToPoint( Point point )
        {
            float segmentDistance;

            switch ( LocateProjection( point ) )
            {
                case ProjectionLocation.RayA:
                    segmentDistance = point.DistanceTo( start );
                    break;
                case ProjectionLocation.RayB:
                    segmentDistance = point.DistanceTo( end );
                    break;
                default:
                    segmentDistance = line.DistanceToPoint( point );
                    break;
            };

            return segmentDistance;
        }

        /// <summary>
        /// Finds, provided it exists, the intersection point with the specified <see cref="LineSegment"/>.
        /// </summary>
        /// 
        /// <param name="other"><see cref="LineSegment"/> to find intersection with.</param>
        /// 
        /// <returns>Returns intersection point with the specified <see cref="LineSegment"/>, or <see langword="null"/>, if
        /// the two segments do not intersect.</returns>
        /// 
        /// <remarks><para>If the two segments do not intersect, the method returns <see langword="null"/>. If the two
        /// segments share multiple points, this throws an <see cref="InvalidOperationException"/>.
        /// </para></remarks>
        /// 
        /// <exception cref="InvalidOperationException">Thrown if the segments overlap - if they have
        /// multiple points in common.</exception>
        /// 
        public Point? GetIntersectionWith( LineSegment other )
        {
            Point? result = null;

            if ( ( line.Slope == other.line.Slope ) || ( line.IsVertical && other.line.IsVertical ) )
            {
                if ( line.Intercept == other.line.Intercept )
                {
                    // Collinear segments. Inspect and handle.
                    // Consider this segment AB and other as CD. (start/end in both cases)
                    // There are three cases:
                    // 0 shared points: C and D both project onto the same ray of AB
                    // 1 shared point: One of A or B equals one of C or D, and the other of C/D 
                    //      projects on the correct ray.
                    // Many shared points.

                    ProjectionLocation projC = LocateProjection( other.start ), projD = LocateProjection( other.end );

                    if ( ( projC != ProjectionLocation.SegmentAB ) && ( projC == projD ) )
                    {
                        // no shared points
                        result = null;
                    }
                    else if ( ( ( start == other.start ) && ( projD == ProjectionLocation.RayA ) ) ||
                              ( ( start == other.end ) && ( projC == ProjectionLocation.RayA ) ) )
                    {
                        // shared start point
                        result = start;
                    }
                    else if ( ( ( end == other.start ) && ( projD == ProjectionLocation.RayB ) ) ||
                              ( ( end == other.end ) && ( projC == ProjectionLocation.RayB ) ) )
                    {
                        // shared end point
                        result = end;
                    }
                    else
                    {
                        // overlapping
                        throw new InvalidOperationException( "Overlapping segments do not have a single intersection point." );
                    }
                }
            }
            else
            {
                result = GetIntersectionWith( other.line );

                if ( ( result.HasValue ) && ( other.LocateProjection( result.Value ) != ProjectionLocation.SegmentAB ) )
                {
                    // the intersection is on the extended line of this segment
                    result = null;
                }
            }

            return result;
        }

        /// <summary>
        /// Finds, provided it exists, the intersection point with the specified <see cref="Line"/>.
        /// </summary>
        /// 
        /// <param name="other"><see cref="Line"/> to find intersection with.</param>
        /// 
        /// <returns>Returns intersection point with the specified <see cref="Line"/>, or <see langword="null"/>, if
        /// the line does not intersect with this segment.</returns>
        /// 
        /// <remarks><para>If the line and the segment do not intersect, the method returns <see langword="null"/>. If the line
        /// and the segment share multiple points, the method throws an <see cref="InvalidOperationException"/>.
        /// </para></remarks>
        /// 
        /// <exception cref="InvalidOperationException">Thrown if this segment is a portion of
        /// <paramref name="other"/> line.</exception>
        /// 
        public Point? GetIntersectionWith( Line other )
        {
            Point? result;

            if ( ( line.Slope == other.Slope ) || ( line.IsVertical && other.IsVertical ) )
            {
                if ( line.Intercept == other.Intercept ) throw new InvalidOperationException( "Segment is a portion of the specified line." );

                // unlike Line.GetIntersectionWith(Line), this does not throw on parallel distinct lines
                result = null;
            }
            else
            {
                result = line.GetIntersectionWith( other );
            }

            if ( ( result.HasValue ) && ( LocateProjection( result.Value ) != ProjectionLocation.SegmentAB ) )
            {
                // the intersection is on this segment's extended line, but not on the segment itself
                result = null;
            }

            return result;
        }

        // Represents the location of a projection of a point on the line that contains this segment.
        // If the point projects to A,B, or anything between them, it is SegmentAB.
        // If it projects beyond A, it's RayA; if it projects beyond B, it's RayB.
        private enum ProjectionLocation { RayA, SegmentAB, RayB }

        // Get type of point's projections to this line segment
        private ProjectionLocation LocateProjection( Point point )
        {
            // Modified from http://www.codeguru.com/forum/showthread.php?t=194400

            /*  How do I find the distance from a point to a line segment?

                Let the point be C (Cx,Cy) and the line be AB (Ax,Ay) to (Bx,By).
                Let P be the point of perpendicular projection of C on AB.  The parameter
                r, which indicates P's position along AB, is computed by the dot product 
                of AC and AB divided by the square of the length of AB:
                
                (1)     AC dot AB
                    r = ---------  
                        ||AB||^2
                
                r has the following meaning:
                
                    r=0      P = A
                    r=1      P = B
                    r<0      P is on the backward extension of AB (and distance C-AB is distance C-A)
                    r>1      P is on the forward extension of AB (and distance C-AB is distance C-B)
                    0<r<1    P is interior to AB (and distance C-AB(segment) is distance C-AB(line))
                
                The length of the line segment AB is computed by:
                
                    L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 )
                
                and the dot product of two 2D vectors, U dot V, is computed:
                
                    D = (Ux * Vx) + (Uy * Vy) 
                
                So (1) expands to:
                
                        (Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)
                    r = -------------------------------
                             (Bx-Ax)^2 + (By-Ay)^2
            */

            // the above is modified here to compare the numerator and denominator, rather than doing the division
            Point abDelta = end - start;
            Point acDelta = point - start;

            float numerator   = acDelta.X * abDelta.X + acDelta.Y * abDelta.Y;
            float denomenator = abDelta.X * abDelta.X + abDelta.Y * abDelta.Y;

            ProjectionLocation result = ( numerator < 0 ) ? ProjectionLocation.RayA : ( numerator > denomenator ) ? ProjectionLocation.RayB : ProjectionLocation.SegmentAB;

            return result;
        }

        /// <summary>
        /// Equality operator - checks if two line segments have equal parameters.
        /// </summary>
        /// 
        /// <param name="line1">First line segment to check.</param>
        /// <param name="line2">Second line segment to check.</param>
        /// 
        /// <returns>Returns <see langword="true"/> if parameters of specified
        /// line segments are equal.</returns>
        ///
        public static bool operator ==( LineSegment line1, LineSegment line2 )
        {
            if ( System.Object.ReferenceEquals( line1, line2 ) )
            {
                return true;
            }

            if ( ( (object) line1 == null ) || ( (object) line2 == null ) )
            {
                return false;
            }

            return ( ( line1.start == line2.start ) && ( line1.end == line2.end ) );
        }

        /// <summary>
        /// Inequality operator - checks if two lines have different parameters.
        /// </summary>
        /// 
        /// <param name="line1">First line segment to check.</param>
        /// <param name="line2">Second line segment to check.</param>
        /// 
        /// <returns>Returns <see langword="true"/> if parameters of specified
        /// line segments are not equal.</returns>
        ///
        public static bool operator !=( LineSegment line1, LineSegment line2 )
        {
            return !( line1 == line2 );
        }

        /// <summary>
        /// Check if this instance of <see cref="LineSegment"/> equals to the specified one.
        /// </summary>
        /// 
        /// <param name="obj">Another line segment to check equalty to.</param>
        /// 
        /// <returns>Return <see langword="true"/> if objects are equal.</returns>
        /// 
        public override bool Equals( object obj )
        {
            return ( obj is LineSegment ) ? ( this == (LineSegment) obj ) : false;
        }

        /// <summary>
        /// Get hash code for this instance.
        /// </summary>
        /// 
        /// <returns>Returns the hash code for this instance.</returns>
        /// 
        public override int GetHashCode( )
        {
            return start.GetHashCode( ) + end.GetHashCode( );
        }

        /// <summary>
        /// Get string representation of the class.
        /// </summary>
        /// 
        /// <returns>Returns string, which contains values of the like in readable form.</returns>
        ///
        public override string ToString( )
        {
            return string.Format( System.Globalization.CultureInfo.InvariantCulture, "({0}) -> ({1})", start, end );
        }
    }
}