曲线交点检测函数无法识别交点的修复方法咨询

原函数无法检测到交点的核心问题是采用固定步长遍历采样点，只有当交点恰好落在遍历的x值上时才能被捕获，实际中几乎不可能命中，导致大量交点被遗漏。

由于你使用的是线性插值，两条曲线本质都是由多条直线段组成的折线，因此有两种更可靠的修复思路：

方案一：直接检测线段间的交点（最准确） #

遍历两条折线的所有线段对，检查每一对线段是否相交，找到交点后直接返回。这种方法完全不会错过交点，且精度可控。

修复后的代码：

using System.Collections.Generic;
using System.Linq;

public static Vec2 FindIntersectionOfTwoCurves(List<double> xList1, List<double> yList1,
                                               List<double> xList2, List<double> yList2)
{
    // 输入合法性校验
    if (xList1 == null || yList1 == null || xList2 == null || yList2 == null ||
        xList1.Count != yList1.Count || xList2.Count != yList2.Count ||
        xList1.Count < 2 || xList2.Count < 2)
        return null;

    // 生成第一条曲线的所有线段
    var segments1 = new List<(Vec2 Start, Vec2 End)>();
    for (int i = 0; i < xList1.Count - 1; i++)
    {
        segments1.Add((new Vec2(xList1[i], yList1[i]), new Vec2(xList1[i+1], yList1[i+1])));
    }

    // 生成第二条曲线的所有线段
    var segments2 = new List<(Vec2 Start, Vec2 End)>();
    for (int i = 0; i < xList2.Count - 1; i++)
    {
        segments2.Add((new Vec2(xList2[i], yList2[i]), new Vec2(xList2[i+1], yList2[i+1])));
    }

    // 检查每一对线段是否相交
    foreach (var seg1 in segments1)
    {
        foreach (var seg2 in segments2)
        {
            if (TryGetLineSegmentIntersection(seg1.Start, seg1.End, seg2.Start, seg2.End, out Vec2 intersection))
            {
                return intersection;
            }
        }
    }

    return null;
}

// 辅助函数：计算两条线段的交点
private static bool TryGetLineSegmentIntersection(Vec2 p1, Vec2 p2, Vec2 p3, Vec2 p4, out Vec2 intersection)
{
    intersection = null;

    double den = (p1.X - p2.X) * (p3.Y - p4.Y) - (p1.Y - p2.Y) * (p3.X - p4.X);
    if (den == 0)
        return false; // 线段平行或重合

    double t = ((p1.X - p3.X) * (p3.Y - p4.Y) - (p1.Y - p3.Y) * (p3.X - p4.X)) / den;
    double u = -((p1.X - p2.X) * (p1.Y - p3.Y) - (p1.Y - p2.Y) * (p1.X - p3.X)) / den;

    // 检查t和u是否在[0,1]范围内（线段相交而非直线相交）
    if (t >= 0 && t <= 1 && u >= 0 && u <= 1)
    {
        double x = p1.X + t * (p2.X - p1.X);
        double y = p1.Y + t * (p2.Y - p1.Y);
        intersection = new Vec2(x, y);
        return true;
    }

    return false;
}

public class Vec2
{
    public double X { get; set; }
    public double Y { get; set; }

    public Vec2(double x, double y)
    {
        X = x;
        Y = y;
    }
}

方案二：用数值根查找算法（适合需要保留插值逻辑的场景） #

如果需要保留插值后的连续曲线逻辑，可以通过寻找函数 f(x) = y1(x) - y2(x) 的根来找到交点，使用二分法可以高效且准确地定位根的位置，避免步长遍历的遗漏问题。

修复后的代码：

using MathNet.Numerics.Interpolation;
using System.Collections.Generic;
using System.Linq;

public static Vec2 FindIntersectionOfTwoCurves(List<double> xList1, List<double> yList1,
                                               List<double> xList2, List<double> yList2)
{
    // 输入合法性校验
    if (xList1 == null || yList1 == null || xList2 == null || yList2 == null ||
        xList1.Count != yList1.Count || xList2.Count != yList2.Count ||
        xList1.Count < 2 || xList2.Count < 2)
        return null;

    IInterpolation interpolation1 = Interpolate.Linear(xList1, yList1);
    IInterpolation interpolation2 = Interpolate.Linear(xList2, yList2);

    double lowerBound = Math.Max(xList1.Min(), xList2.Min());
    double upperBound = Math.Min(xList1.Max(), xList2.Max());

    // 检查区间端点是否已经是交点
    double fLower = interpolation1.Interpolate(lowerBound) - interpolation2.Interpolate(lowerBound);
    if (Math.Abs(fLower) < 1e-7)
        return new Vec2(lowerBound, interpolation1.Interpolate(lowerBound));

    double fUpper = interpolation1.Interpolate(upperBound) - interpolation2.Interpolate(upperBound);
    if (Math.Abs(fUpper) < 1e-7)
        return new Vec2(upperBound, interpolation1.Interpolate(upperBound));

    // 检查区间内是否存在根（函数值异号）
    if (fLower * fUpper >= 0)
        return null;

    // 二分法查找根
    const int maxIterations = 100;
    const double tolerance = 1e-10;
    double xMid = 0;
    for (int i = 0; i < maxIterations; i++)
    {
        xMid = (lowerBound + upperBound) / 2;
        double fMid = interpolation1.Interpolate(xMid) - interpolation2.Interpolate(xMid);

        if (Math.Abs(fMid) < tolerance)
            break;

        if (fLower * fMid < 0)
            upperBound = xMid;
        else
        {
            lowerBound = xMid;
            fLower = fMid;
        }
    }

    return new Vec2(xMid, interpolation1.Interpolate(xMid));
}

public class Vec2
{
    public double X { get; set; }
    public double Y { get; set; }

    public Vec2(double x, double y)
    {
        X = x;
        Y = y;
    }
}

内容的提问来源于stack exchange，提问作者user366312