WPF 基础 2D 图形学知识判断点是否在线段上

在知道一个使用两个点表示的线段，和另一个点，求另一个点是否在线段上

本文算法属于通用的算法，可以在 WPF 和 UWP 和 Xamarin 等上运行，基本上所有的 .NET 平台都能执行

如下图，如果点在线段上，那么修改线段颜色

假定有线段的定义如下

    public record Line
    {
        public Point APoint { get; init; }

        public Point BPoint { get; init; }
    }

以上代码使用了 .NET 5 加 C# 9.0 的新语法

在传入一个点，求这个点是否在线段上，最简单理解的算法是根据两点之间直线距离最短，只需要求 P 点和线段的 AB 两点的距离是否等于 AB 的距离。如果相等，那么证明 P 点在线段 AB 上，代码如下

        private static bool CheckIsPointOnLine(Point point, Line line, double epsilon = 0.1)
        {
            // 最简单理解的算法是根据两点之间直线距离最短，只需要求 P 点和线段的 AB 两点的距离是否等于 AB 的距离。如果相等，那么证明 P 点在线段 AB 上
            var ap = point - line.APoint;
            var bp = point - line.BPoint;
            var ab = line.BPoint - line.APoint;

            // 只不过求 Length 内部需要用到一次 Math.Sqrt 性能会比较差
            if (Math.Abs(ap.Length + bp.Length - ab.Length) < epsilon)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

不使用 Vector 类，可以替换为如下计算方法。上面代码的 ap 等变量是使用 WPF 的两个点的相减能拿到 Vectore 类，而在 Vectore 类里面有 Length 属性而优化代码的。其实核心计算和下面代码相同。下面代码是 Tone Škoda 提供的，详细请看 https://stackoverflow.com/a/56850069/6116637

public static double CalcDistanceBetween2Points(double x1, double y1, double x2, double y2)
{
    return Math.Sqrt(Math.Pow (x1 - x2, 2) + Math.Pow (y1 - y2, 2));
}

public static bool PointLinesOnLine (double x, double y, double x1, double y1, double x2, double y2, double allowedDistanceDifference)
{
    double dist1 = CalcDistanceBetween2Points(x, y, x1, y1);
    double dist2 = CalcDistanceBetween2Points(x, y, x2, y2);
    double dist3 = CalcDistanceBetween2Points(x1, y1, x2, y2);
    return Math.Abs(dist3 - (dist1 + dist2)) <= allowedDistanceDifference;
}

以下是另一个方法，以下方法性能比上面一个好，上面的方法需要用到平方再开方，计算复杂度会高一些

根据点和任意线段端点连接的线段和当前线段斜率相同，同时点在两个端点中间，就可以认为点在线段内

(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)

因为乘法性能更高，因此计算方法可以根据如下公式进行改进

 (x - x1) * (y2 - y1) = (y - y1) * (x2 - x1)
 (x - x1) * (y2 - y1) - (y - y1) * (x2 - x1) = 0

在完成斜率判断之后，还需要判断点在两个端点中间，判断点是否在两个端点中间可以通过 x 和 y 两个分量都在两个端点中间作为判断条件，如下面公式

             x1 < x < x2, assuming x1 < x2
             y1 < y < y2, assuming y1 < y2

以下是代码

            if (EqualPoint(point, line.APoint, epsilon) || EqualPoint(point, line.BPoint, epsilon))
            {
                return true;
            }

            // 乘法性能更高，但在一些要求精度的情况下可能 double 误差大。请试试在返回 true 的时候，看看 CrossProduct 的值，可以发现误差依然很大
            var crossProduct = (point.X - line.APoint.X) * (line.BPoint.Y - line.APoint.Y) -
                               (point.Y - line.APoint.Y) * (line.BPoint.X - line.APoint.X);

            // 将 crossProduct 和 0 比较，从而判断是否平行。可以看到在一些满足点在线上的情况下，如果和 0 进行完全相等比较时，可能因为精度误差问题，判断失败

            if (Math.Abs((point.X - line.APoint.X) / (line.BPoint.X - line.APoint.X) - (point.Y - line.APoint.Y) / (line.BPoint.Y - line.APoint.Y)) < epsilon)
            {
                var minX = Math.Min(line.APoint.X, line.BPoint.X);
                var maxX = Math.Max(line.APoint.X, line.BPoint.X);

                var minY = Math.Min(line.APoint.Y, line.BPoint.Y);
                var maxY = Math.Max(line.APoint.Y, line.BPoint.Y);

                if (minX < point.X && point.X < maxX && minY < point.Y && point.Y < maxY)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }

上面代码的 CrossProduct 是不用使用的，只是为了告诉大家，尽管乘法性能比较好，但是误差比较大。以上的 CrossProduct 使用了叉乘的方法，在本文末尾也会重新再讲一次

当然以上算法有漏洞，在于如果 A 和 B 两个点的 Y 坐标相同或 X 坐标相同的时候，那么以上算法不适合。可以先判断 CrossProduct 的值，如果是等于零，那么证明有 A 和 B 两个点的 Y 坐标相同或 X 坐标相同

            var crossProduct = (point.X - line.APoint.X) * (line.BPoint.Y - line.APoint.Y) -
                               (point.Y - line.APoint.Y) * (line.BPoint.X - line.APoint.X);
            // 先判断 crossProduct 是否等于 0 可以解决 A 和 B 两个点的 Y 坐标相同或 X 坐标相同的时候，使用除法的坑
            if (crossProduct == 0 || Math.Abs((point.X - line.APoint.X) / (line.BPoint.X - line.APoint.X) - (point.Y - line.APoint.Y) / (line.BPoint.Y - line.APoint.Y)) < epsilon)
            {
                var minX = Math.Min(line.APoint.X, line.BPoint.X);
                var maxX = Math.Max(line.APoint.X, line.BPoint.X);

                var minY = Math.Min(line.APoint.Y, line.BPoint.Y);
                var maxY = Math.Max(line.APoint.Y, line.BPoint.Y);

                if (minX <= point.X && point.X <= maxX && minY <= point.Y && point.Y <= maxY)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }

以上代码放在 github 和 gitee 欢迎小伙伴访问

以上方法的计算有些重复，其实加上了 CrossProduct 只是为了水平和垂直的线段，其实可以做特殊处理优化水平和垂直的线段的计算，如下面代码

    public static class Math2DExtensions
    {
        public static bool CheckIsPointOnLineSegment(Point point, Line line, double epsilon = 0.1)
        {
            // 以下是另一个方法，以下方法性能比上面一个好

            // 根据点和任意线段端点连接的线段和当前线段斜率相同，同时点在两个端点中间
            // (x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)
            // x1 < x < x2, assuming x1 < x2
            // y1 < y < y2, assuming y1 < y2
            // 但是需要额外处理 X1 == X2 和 Y1 == Y2 的计算

            var minX = Math.Min(line.APoint.X, line.BPoint.X);
            var maxX = Math.Max(line.APoint.X, line.BPoint.X);

            var minY = Math.Min(line.APoint.Y, line.BPoint.Y);
            var maxY = Math.Max(line.APoint.Y, line.BPoint.Y);

            if (!(minX <= point.X) || !(point.X <= maxX) || !(minY <= point.Y) || !(point.Y <= maxY))
            {
                return false;
            }

            // 以下处理水平和垂直线段
            if (Math.Abs(line.APoint.X - line.BPoint.X) < epsilon)
            {
                // 如果 X 坐标是相同，那么只需要判断点的 X 坐标是否相同
                // 因为在上面代码已经判断了 点的 Y 坐标是在线段两个点之内
                return Math.Abs(line.APoint.X - point.X) < epsilon || Math.Abs(line.BPoint.X - point.X) < epsilon;
            }

            if (Math.Abs(line.APoint.Y - line.BPoint.Y) < epsilon)
            {
                return Math.Abs(line.APoint.Y - point.Y) < epsilon || Math.Abs(line.BPoint.Y - point.Y) < epsilon;
            }

            if (Math.Abs((point.X - line.APoint.X) / (line.BPoint.X - line.APoint.X) - (point.Y - line.APoint.Y) / (line.BPoint.Y - line.APoint.Y)) < epsilon)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }

    public record Line
    {
        public Point APoint { get; init; }

        public Point BPoint { get; init; }
    }

以上代码放在 github 和 gitee 欢迎小伙伴访问

除了以上方法之外，还可以通过叉积法求点是否在直线上，再通过判断与端点两点的差值从而判断点是否在线段上

叉积法又称向量法。计算方法就是将原本线段构成向量，再与所求点与线段任意端点构成的向量，两个向量之间的叉乘计算，求向量的叉乘结果与 0 判断，从而判断点是否在线段所在直线上。在 2D 几何的向量叉乘计算上，更准确来说是使用向量叉乘在二维空间中的推广

    /// <summary>
    /// 求线点关系
    /// 使用叉积方法求点在线的左侧还是右侧
    /// 使用向量法求点到线的距离
    /// 详细请看 “叉积法”或“向量法”
    /// </summary>
    /// <param name="line"></param>
    /// <param name="point"></param>
    /// <returns></returns>
    public static PointWithLineRelation CalculatePointWithLineRelation(this Segment2D line, Point2D point)
    {
        Vector2D v1 = line.Vector;
        Vector2D v2 = (point - line.PointA);
        var crossProductValue = v1.Det(v2);
        var distance = Math.Abs(crossProductValue) / line.Length;
        return new PointWithLineRelation(crossProductValue, distance);
    }

/// <summary>
/// 点与线的关系
/// </summary>
/// <param name="CrossProductValue"></param>
/// <param name="Distance"></param>
public readonly record struct PointWithLineRelation(double CrossProductValue, double Distance)
{
    public PointInLineCrossProductResult CrossProductResult
    {
        get
        {
            if (CrossProductValue > 0)
            {
                return PointInLineCrossProductResult.PointInLineLeft;
            }
            else if (CrossProductValue < 0)
            {
                return PointInLineCrossProductResult.PointInLineRight;
            }
            else
            {
                return PointInLineCrossProductResult.PointInLine;
            }
        }
    }
};

public enum PointInLineCrossProductResult
{
    PointInLineLeft,
    PointInLine,
    PointInLineRight,
}

以上的 Vector2D 的 Det 的定义如下

[DebuggerDisplay("X = {X}, Y = {Y}")]
public readonly record struct Vector2D(double X, double Y)
{
    /// <summary>
    /// 向量行列式，即向量叉乘在二维空间中的推广。
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public double Det(Vector2D other)
    {
        return (X * other.Y) - (Y * other.X);
    }

    [Obsolete("和 Det 完全相同，请使用 Det 代替", true)]
    public double CrossProduct(Vector2D other) => Det(other);
}

可以看到这里介绍的叉乘方法本质上和上文所述的数学计算过程是相同的，只是所使用的概念不同

以上更多的数学定义代码我放在 github 和 gitee 欢迎访问

原文链接: http://blog.lindexi.com/post/WPF-%E5%9F%BA%E7%A1%80-2D-%E5%9B%BE%E5%BD%A2%E5%AD%A6%E7%9F%A5%E8%AF%86-%E5%88%A4%E6%96%AD%E7%82%B9%E6%98%AF%E5%90%A6%E5%9C%A8%E7%BA%BF%E6%AE%B5%E4%B8%8A

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。欢迎转载、使用、重新发布，但务必保留文章署名林德熙 (包含链接: https://blog.lindexi.com )，不得用于商业目的，基于本文修改后的作品务必以相同的许可发布。如有任何疑问，请与我联系。

WPF 基础 2D 图形学知识 判断点是否在线段上

WPF 基础 2D 图形学知识判断点是否在线段上