Monogame-Extended/source/MonoGame.Extended/Math/LineSegment.cs

using System;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.Serialization;
using Microsoft.Xna.Framework;

namespace MonoGame.Extended;

/// <summary>
/// Represents a line segment defined by two endpoints.
/// </summary>
[DataContract]
[DebuggerDisplay("{DebugDisplayString,nq}")]
public struct LineSegment : IEquatable<LineSegment>
{
    #region Fields

    private static readonly LineSegment s_empty = new LineSegment(Vector2.Zero, Vector2.Zero);

    /// <summary>
    /// The starting point of the line segment.
    /// </summary>
    [DataMember]
    public Vector2 Start;

    /// <summary>
    /// The ending point of the line segment.
    /// </summary>
    [DataMember]
    public Vector2 End;

    #endregion

    #region Properties

    /// <summary>
    /// Gets an empty line segment representing a degenerate case with both endpoints at the same position.
    /// </summary>
    public static LineSegment Empty => s_empty;

    /// <summary>
    /// Gets a value indicating whether this line segment represents a degenerate case with no length,
    /// having both endpoints at the same position.
    /// </summary>
    public readonly bool IsEmpty => Start == End;

    /// <summary>
    /// Gets the direction vector from start to end point with magnitude equal to segment length.
    /// </summary>
    public readonly Vector2 Direction => End - Start;

    /// <summary>
    /// Gets the direction vector from start to end point normalized to unit length.
    /// </summary>
    public readonly Vector2 DirectionNormalized => Vector2.Normalize(Direction);

    /// <summary>
    /// Gets the length of the line segment.
    /// </summary>
    public readonly float Length => Vector2.Distance(Start, End);

    /// <summary>
    /// Gets the squared length of the line segment, avoiding square root calculation.
    /// </summary>
    /// <remarks>
    /// This property avoids the expensive square root operation, making it more efficient
    /// for length comparisons when the actual distance value is not needed.
    /// </remarks>
    public readonly float LengthSquared => Vector2.DistanceSquared(Start, End);

    /// <summary>
    /// Gets the midpoint of the line segment.
    /// </summary>
    public readonly Vector2 Center => (Start + End) * 0.5f;

    #endregion

    #region Constructors

    /// <summary>
    /// Initializes a new line segment with the specified endpoints.
    /// </summary>
    /// <param name="start">The starting point of the segment.</param>
    /// <param name="end">The ending point of the segment.</param>
    public LineSegment(Vector2 start, Vector2 end)
    {
        Start = start;
        End = end;
    }

    #endregion

    #region Create From Methods

    /// <summary>
    /// Creates a line segment from a starting point, direction, and length.
    /// </summary>
    /// <param name="start">The starting point of the segment.</param>
    /// <param name="direction">The direction vector (will be normalized if non-zero).</param>
    /// <param name="length">The length of the segment.</param>
    /// <returns>A new line segment with the specified properties.</returns>
    public static LineSegment FromDirection(Vector2 start, Vector2 direction, float length)
    {
        Vector2 normalizedDir = direction;
        if (direction != Vector2.Zero)
        {
            normalizedDir.Normalize();
        }

        return new LineSegment(start, start + normalizedDir * length);
    }

    #endregion

    #region Intersection Methods

    /// <summary>
    /// Determines whether this line segment intersects with another line segment.
    /// </summary>
    /// <param name="other">The other line segment to test for intersection.</param>
    /// <returns>
    /// <see langword="true"/> if this line segment intersects the other; otherwise, <see langword="false"/>.
    /// </returns>
    public readonly bool Intersects(LineSegment other) => IntersectionTests.LineSegmentLineSegment(in this, in other);

    /// <summary>
    /// Determines whether this line segment intersects with a circle
    /// </summary>
    /// <param name="circle">The circle to test for intersection.</param>
    /// <returns>
    /// <see langword="true"/> if this line segment intersects the circle; otherwise, <see langword="false"/>.
    /// </returns>
    public readonly bool Intersects(Circle circle) => IntersectionTests.CirceLineSegment(in circle, in this);

    /// <summary>
    /// Determines whether this line segment intersects with an ellipse
    /// </summary>
    /// <param name="ellipse">The ellipse to test for intersection.</param>
    /// <returns>
    /// <see langword="true"/> if this line segment intersects the ellipse; otherwise, <see langword="false"/>.
    /// </returns>
    public readonly bool Intersects(Ellipse ellipse) => IntersectionTests.EllipseLineSegment(in ellipse, in this);

    /// <summary>
    /// Determines whether this line segment intersects with a rectangle
    /// </summary>
    /// <param name="rectangle">The rectangle to test for intersection.</param>
    /// <returns>
    /// <see langword="true"/> if this line segment intersects the rectangle; otherwise, <see langword="false"/>.
    /// </returns>
    public readonly bool Intersects(RectangleF rectangle) => IntersectionTests.RectangleFLineSegment(in rectangle, in this);

    /// <summary>
    /// Determines whether this line segment intersects with a ray
    /// </summary>
    /// <param name="ray">The ray to test for intersection.</param>
    /// <returns>
    /// <see langword="true"/> if this line segment intersects the ray; otherwise, <see langword="false"/>.
    /// </returns>
    public readonly bool Intersects(Ray ray) => IntersectionTests.RayLineSegment(in ray, in this);

    #endregion

    #region Closest Point To Methods

    /// <summary>
    /// Computes the closest point on the line segment to the specified point.
    /// </summary>
    /// <param name="point">The query point for closest-point computation.</param>
    /// <returns>The point on the segment closest to the query point.</returns>
    /// <remarks>
    /// This method projects the point onto the line defined by the segment, then clamps
    /// the result to the segment endpoints if necessary.
    /// </remarks>
    public readonly Vector2 ClosestPointTo(Vector2 point)
    {
        Vector2 ab = End - Start;
        float t = Vector2.Dot(point - Start, ab);

        if (t <= 0.0f)
        {
            // Point projects outside segment on the start side
            return Start;
        }

        float denom = Vector2.Dot(ab, ab);
        if (t >= denom)
        {
            // Point project outside segment on the end side
            return End;
        }

        // Point project inside segment
        return Start + ab * (t / denom);
    }

    /// <summary>
    /// Computes the closest point on the line segment to the specified point with parametric position.
    /// </summary>
    /// <param name="point">The query point for closest-point computation.</param>
    /// <param name="t">
    /// When this method returns, contains the parametric position (0 to 1) of the closest point along the segment,
    /// where 0 corresponds to the start point and 1 corresponds to the end point.
    /// </param>
    /// <returns>The point on the segment closest to the query point.</returns>
    public readonly Vector2 ClosestPointTo(Vector2 point, out float t)
    {
        Vector2 ab = End - Start;
        t = Vector2.Dot(point - Start, ab);

        if (t <= 0.0f)
        {
            // Point projects outside segment on the start side
            t = 0.0f;
            return Start;
        }

        float denom = Vector2.Dot(ab, ab);
        if (t >= denom)
        {
            // Point projects outside segment on the End side
            t = 1.0f;
            return End;
        }

        // Point projects inside segment
        t = t / denom;
        return Start + t * ab;
    }

    /// <summary>
    /// Computes the closest points between this segment and another segment.
    /// </summary>
    /// <param name="other">The other line segment to test against.</param>
    /// <param name="pointOnThis">When this method returns, contains the closest point on this segment.</param>
    /// <param name="pointOnOther">When this method returns, contains the closest point on the other segment.</param>
    /// <returns>The distance between the two closest points.</returns>
    public readonly float ClosestPoints(LineSegment other, out Vector2 pointOnThis, out Vector2 pointOnOther)
    {
        return ClosestPointsSegmentSegment(Start, End, other.Start, other.End, out _, out _, out pointOnThis, out pointOnOther);
    }

    /// <summary>
    /// Computes the closest points between two line segments.
    /// </summary>
    /// <param name="p1">The start point of the first segment.</param>
    /// <param name="q1">The end point of the first segment.</param>
    /// <param name="p2">The start point of the second segment.</param>
    /// <param name="q2">The end point of the second segment.</param>
    /// <param name="s">When this method returns, contains the parametric position on the first segment.</param>
    /// <param name="t">When this method returns, contains the parametric position on the second segment.</param>
    /// <param name="c1">When this method returns, contains the closest point on the first segment.</param>
    /// <param name="c2">When this method returns, contains the closest point on the second segment.</param>
    /// <returns>The distance between the closest points.</returns>
    private static float ClosestPointsSegmentSegment(Vector2 p1, Vector2 q1, Vector2 p2, Vector2 q2, out float s, out float t, out Vector2 c1, out Vector2 c2)
    {
        // Direction vector of segment S1
        Vector2 d1 = q1 - p1;

        // Direction vector of segment S2
        Vector2 d2 = q2 - p2;

        Vector2 r = p1 - p2;

        // Squared length of segment S1
        float a = Vector2.Dot(d1, d1);

        // Squared length of segment S2
        float e = Vector2.Dot(d2, d2);

        float f = Vector2.Dot(d2, r);

        // Check if either or both segments degenerate into points
        if (a <= 0.001f && e <= 0.001f)
        {
            // Both segments degenerate into points
            s = t = 0.0f;
            c1 = p1;
            c2 = p2;
            return Vector2.Distance(c1, c2);
        }

        if (a <= 0.001f)
        {
            // First segment degenerates into a point
            s = 0.0f;
            t = f / e;
            t = Math.Clamp(t, 0.0f, 1.0f);
        }
        else
        {
            float c = Vector2.Dot(d1, r);

            if (e <= 0.001f)
            {
                // second segment degenerates into a point
                t = 0.0f;
                s = Math.Clamp(-c / a, 0.0f, 1.0f);
            }
            else
            {
                // The general non-degenerate case starts here
                float b = Vector2.Dot(d1, d2);
                float denom = a * e - b * b;

                // If segments not parallel, compute closest point on L1 to L2
                if (denom != 0.0f)
                {
                    s = Math.Clamp((b * f - c * e) / denom, 0.0f, 1.0f);
                }
                else
                {
                    // Parallel segments - pick arbitrary s
                    s = 0.0f;
                }

                // Compute point on L2 closest to S1(s)
                t = (b * s + f) / e;

                // If t in [0,1] done. Else clamp t, recompute s
                if (t < 0.0f)
                {
                    t = 0.0f;
                    s = Math.Clamp(-c / a, 0.0f, 1.0f);
                }
                else if (t > 1.0f)
                {
                    t = 1.0f;
                    s = Math.Clamp((b - c) / a, 0.0f, 1.0f);
                }
            }
        }

        c1 = p1 + d1 * s;
        c2 = p2 + d2 * t;
        return Vector2.Distance(c1, c2);
    }

    /// <summary>
    /// Computes the point on the segment at the specified parametric position.
    /// </summary>
    /// <param name="t">
    /// The parametric position along the segment, where 0 returns <see cref="Start"/>
    /// and 1 returns <see cref="End"/>. Values outside [0,1] extrapolate beyond the segment.
    /// </param>
    /// <returns>The point at position t along the segment.</returns>
    public readonly Vector2 GetPointAt(float t)
    {
        return Start + t * (End - Start);
    }

    #endregion

    #region Distance Methods

    /// <summary>
    /// Computes the shortest distance from the line segment to the specified point.
    /// </summary>
    /// <param name="point">The point to measure distance to.</param>
    /// <returns>The shortest distance from the segment to the point.</returns>
    public readonly float DistanceTo(Vector2 point)
    {
        return MathF.Sqrt(DistanceSquaredTo(point));
    }

    /// <summary>
    /// Computes the squared shortest distance from the line segment to the specified point.
    /// </summary>
    /// <param name="point">The point to measure distance to.</param>
    /// <returns>The squared shortest distance from the segment to the point.</returns>
    /// <remarks>
    /// This method is more efficient than <see cref="DistanceTo(Vector2)"/> as it avoids the expensive square root
    /// operation.
    /// </remarks>
    public readonly float DistanceSquaredTo(Vector2 point)
    {
        Vector2 ab = End - Start;
        Vector2 ac = point - Start;
        Vector2 bc = point - End;

        float e = Vector2.Dot(ac, ab);

        // Point projects outside the segment on the start side
        if (e <= 0.0f)
        {
            return Vector2.Dot(ac, ac);
        }

        float f = Vector2.Dot(ab, ab);

        // Point projects outside the segment on the end side
        if (e >= f)
        {
            return Vector2.Dot(bc, bc);
        }

        // Point projects inside the segment
        return Vector2.Dot(ac, ac) - e * e / f;
    }

    #endregion

    #region Offset Methods

    /// <summary>
    /// Translates the line segment by moving both endpoints, preserving direction and length.
    /// </summary>
    /// <param name="offset">The translation vector to apply to both endpoints.</param>
    public void Offset(Vector2 offset)
    {
        Start += offset;
        End += offset;
    }

    /// <summary>
    /// Creates a new line segment translated by the specified offset vector.
    /// </summary>
    /// <param name="lineSegment">The line segment to translate.</param>
    /// <param name="offset">The translation vector to apply.</param>
    /// <returns>A new line segment with both endpoints translated.</returns>
    public static LineSegment Offset(LineSegment lineSegment, Vector2 offset)
    {
        return lineSegment with { Start = lineSegment.Start + offset, End = lineSegment.End + offset };
    }

    #endregion

    #region Transform Methods

    /// <summary>
    /// Applies a 2D transformation matrix to the line segment, transforming both endpoints.
    /// </summary>
    /// <param name="matrix">The transformation matrix to apply.</param>
    public void Transform(Matrix3x2 matrix)
    {
        Transform(ref matrix);
    }

    /// <summary>
    /// Applies a 2D transformation matrix to the line segment, transforming both endpoints.
    /// </summary>
    /// <param name="matrix">The transformation matrix to apply.</param>
    public void Transform(ref Matrix3x2 matrix)
    {
        Start = Vector2.Transform(Start, matrix);
        End = Vector2.Transform(End, matrix);
    }

    /// <summary>
    /// Creates a new line segment by applying a 2D transformation matrix.
    /// </summary>
    /// <param name="lineSegment">The line segment to transform.</param>
    /// <param name="matrix">The transformation matrix to apply.</param>
    /// <returns>A new transformed line segment.</returns>
    public static LineSegment Transform(LineSegment lineSegment, Matrix3x2 matrix)
    {
        return Transform(lineSegment, ref matrix);
    }

    /// <summary>
    /// Computes a transformed line segment using reference parameters for performance.
    /// </summary>
    /// <param name="lineSegment">The line segment to transform.</param>
    /// <param name="matrix">The transformation matrix to apply.</param>
    public static LineSegment Transform(LineSegment lineSegment, ref Matrix3x2 matrix)
    {
        return lineSegment with { Start = Vector2.Transform(lineSegment.Start, matrix), End = Vector2.Transform(lineSegment.End, matrix) };
    }

    #endregion

    #region Equality Methods

    /// <summary>
    /// Determines whether this line segment is equal to the specified object.
    /// </summary>
    /// <param name="obj">The object to compare.</param>
    /// <returns>
    /// <c>true</c> if the object is a <see cref="LineSegment"/> with the same start and end; otherwise, <c>false</c>.
    /// </returns>
    public override readonly bool Equals([NotNullWhen(true)] object obj)
    {
        return obj is LineSegment other && Equals(other);
    }

    /// <summary>
    /// Determines whether this line segment is equal to another line segment.
    /// </summary>
    /// <param name="other">The line segment to compare with this line segment.</param>
    /// <returns>
    /// <c>true</c> if the line segments have the same start and end; otherwise, <c>false</c>.
    /// </returns>
    public readonly bool Equals(LineSegment other)
    {
        return Equals(other);
    }

    #endregion

    /// <summary>
    /// Computes the hash code for this line segment.
    /// </summary>
    /// <returns>A hash code derived from the start and end points.</returns>
    public override readonly int GetHashCode()
    {
        return HashCode.Combine(Start, End);
    }

    /// <summary>
    /// Creates a string representation of this line segment.
    /// </summary>
    /// <returns>A formatted string containing the start and end points.</returns>
    public override readonly string ToString()
    {
        return $"LineSegment({Start} - {End})";
    }

    internal readonly string DebugDisplayString => ToString();

    #region Operators

    /// <summary>
    /// Tests whether two line segments are equal.
    /// </summary>
    /// <param name="left">The first line segment.</param>
    /// <param name="right">The second line segment.</param>
    /// <returns><c>true</c> if both line segments have the same start and end; otherwise, <c>false</c>.</returns>
    public static bool operator ==(LineSegment left, LineSegment right)
    {
        return left.Equals(right);
    }

    /// <summary>
    /// Tests whether two line segments are not equal.
    /// </summary>
    /// <param name="left">The first line segment.</param>
    /// <param name="right">The second line segment.</param>
    /// <returns><c>true</c> if the line segments have different start or end points; otherwise, <c>false</c>.</returns>
    public static bool operator !=(LineSegment left, LineSegment right)
    {
        return !left.Equals(right);
    }

    #endregion
}