线段相交检测：共享起点不判定为相交的问题排查

我要实现线段放置检测逻辑，判断待放置线段是否与已有线段列表相交。目前基于方向法和共线点检测实现了isIntersect等方法及Line结构体，但遇到两个线段共享起点时被误判为相交的问题。尝试添加l1.startingPoint != p && l1.endingPoint != p的条件修正，但问题仍存在，希望得到解决帮助。

相关代码 #

工具方法实现 #

public static bool onLine(Line l1, Vector2 p)
{   //检查点p是否在线段l1上
    if (p.x <= Mathf.Max(l1.startingPoint.x, l1.endingPoint.x) && p.x <= Mathf.Min(l1.startingPoint.x, l1.endingPoint.x) &&
       (p.y <= Mathf.Max(l1.startingPoint.y, l1.endingPoint.y) && p.y <= Mathf.Min(l1.startingPoint.y, l1.endingPoint.y)))
        return true;

    return false;
}

public static int directionV2(Vector2 a, Vector2 b, Vector2 c)
{
    float val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
    if (val == 0)
        return 0;     //共线
    else if (val < 0)
        return 2;    //逆时针方向
    return 1;    //顺时针方向
}

public static bool isIntersect(Line l1, Line l2)
{
    //计算两条线段及对方端点的四个方向值
    int dir1 = directionV2(l1.startingPoint, l1.endingPoint, l2.startingPoint);
    int dir2 = directionV2(l1.startingPoint, l1.endingPoint, l2.endingPoint);
    int dir3 = directionV2(l2.startingPoint, l2.endingPoint, l1.startingPoint);
    int dir4 = directionV2(l2.startingPoint, l2.endingPoint, l1.endingPoint);

    if (dir1 != dir2 && dir3 != dir4)
        return true; //线段相交

    if (dir1 == 0 && onLine(l1, l2.startingPoint)) //line2的起点在line1上
        return true;

    if (dir2 == 0 && onLine(l1, l2.endingPoint)) //line2的终点在line1上
        return true;

    if (dir3 == 0 && onLine(l2, l1.startingPoint)) //line1的起点在line2上
        return true;

    if (dir4 == 0 && onLine(l2, l1.endingPoint)) //line1的终点在line2上
        return true;

    return false;
}

Line结构体定义 #

public struct Line
{
    public Vector2 startingPoint;
    public Vector2 endingPoint;

    public Line(Vector2 start, Vector2 end)
    {
        this.startingPoint = new Vector2(start.x, start.y);
        this.endingPoint = new Vector2(end.x, end.y);
    }
}

问题根源分析 #

1. onLine方法逻辑错误：代码中判断p.x <= Mathf.Max(...) && p.x <= Mathf.Min(...)，两个条件同时成立只有当线段x坐标完全相同且p的x等于该值，否则永远为假。正确逻辑应该是p.x >= Mathf.Min(...) && p.x <= Mathf.Max(...)，y坐标同理——你把大于等于写成了小于等于，导致共线点的范围判断完全失效。
2. 共享端点判定逻辑缺失：当前代码会把共享端点的情况判定为相交（因为端点在对方线段上），如果业务需求是共享端点不算相交，需要额外排除这种场景。
3. 浮点数精度问题：直接用val == 0或Vector2相等判断，容易因浮点误差导致误判。

修复方案 #

步骤1：修正onLine方法的范围与共线判断 #

public static bool onLine(Line l1, Vector2 p)
{
    // 先判断点是否在线段的轴对齐包围盒内
    bool inXRange = p.x >= Mathf.Min(l1.startingPoint.x, l1.endingPoint.x) && 
                    p.x <= Mathf.Max(l1.startingPoint.x, l1.endingPoint.x);
    bool inYRange = p.y >= Mathf.Min(l1.startingPoint.y, l1.endingPoint.y) && 
                    p.y <= Mathf.Max(l1.startingPoint.y, l1.endingPoint.y);
    
    if (!inXRange || !inYRange)
        return false;
    
    // 通过叉乘确认点是否在直线上（共线），加入浮点精度容错
    float cross = (l1.endingPoint.x - l1.startingPoint.x) * (p.y - l1.startingPoint.y) - 
                  (l1.endingPoint.y - l1.startingPoint.y) * (p.x - l1.startingPoint.x);
    return Mathf.Abs(cross) < 1e-6f;
}

步骤2：排除共享端点的情况（按需选择） #

如果业务定义共享端点不算相交，在isIntersect开头添加判断：

public static bool isIntersect(Line l1, Line l2)
{
    // 排除共享端点的情况（浮点精度容错）
    float eps = 1e-6f;
    if (Vector2.Distance(l1.startingPoint, l2.startingPoint) < eps || 
        Vector2.Distance(l1.startingPoint, l2.endingPoint) < eps || 
        Vector2.Distance(l1.endingPoint, l2.startingPoint) < eps || 
        Vector2.Distance(l1.endingPoint, l2.endingPoint) < eps)
    {
        return false;
    }

    // 原有的方向判断逻辑
    int dir1 = directionV2(l1.startingPoint, l1.endingPoint, l2.startingPoint);
    int dir2 = directionV2(l1.startingPoint, l1.endingPoint, l2.endingPoint);
    int dir3 = directionV2(l2.startingPoint, l2.endingPoint, l1.startingPoint);
    int dir4 = directionV2(l2.startingPoint, l2.endingPoint, l1.endingPoint);

    if (dir1 != dir2 && dir3 != dir4)
        return true;

    if (dir1 == 0 && onLine(l1, l2.startingPoint))
        return true;

    if (dir2 == 0 && onLine(l1, l2.endingPoint))
        return true;

    if (dir3 == 0 && onLine(l2, l1.startingPoint))
        return true;

    if (dir4 == 0 && onLine(l2, l1.endingPoint))
        return true;

    return false;
}

步骤3：修正directionV2的精度判断 #

public static int directionV2(Vector2 a, Vector2 b, Vector2 c)
{
    float val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
    if (Mathf.Abs(val) < 1e-6f)
        return 0;     //共线
    else if (val < 0)
        return 2;    //逆时针方向
    return 1;    //顺时针方向
}

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