Определить пересекаются ли отрезки в c# (Unity3D)

181

07 сентября 2018, 03:20

У меня есть два отрезка, знаю координаты точек на их концах, нужно определить пересекаются ли отрезки и где. Желательно встроенный в C# или в библиотеки Unity3D способ.

UnityEngine.Vector3 l1p1 = ..., l1p2 = ...; //First line
UnityEngine.Vector3 l2p1 = ..., l2p2 = ...; //Second line
... //Intersection finding code
UnityEngine.Vector3 intersectionPoint = ...; //Result of intersection point finding
bool linesIntersect = ...; //Result of intersection cheking

Answer 1

Отрезки в 3D пересекаются редко :)

Лобовой путь может быть таким:
Представим отрезки в параметрическом виде, где нулевой индекс относится к началу, а единичный - к концу отрезка. Для отрезка a

ax = ax0 + t * (ax1 - ax0) 
ay = ay0 + t * (ay1 - ay0) 
az = az0 + t * (az1 - az0)

Если отрезки пересекаются, то все три координаты совпадают, и получается система из трех линейных уравнений для двух неизвестных

ax0 + t * (ax1 - ax0) = bx0 + u * (bx1 - bx0)
ay0 + t * (ay1 - ay0) = by0 + u * (by1 - by0) 
az0 + t * (az1 - az0) = bz0 + u * (bz1 - bz0)

Решаем систему, проверяем, что она совместна (решение для первой пары уравнений совпадает с решением для второй и т.д.), и что параметры t и u лежат в пределах 0..1. В таком случае точка пересечения существует, и её находим, подставляя t в уравнения для первого отрезка.

Однако такой метод крайне чувствителен к вычислительным погрешностям.

Более надёжный способ - нахождение ближайших между собой точек отрезков как концов общего к отрезкам перпендикуляра, и проверка, что длина этого перпендикуляра укладывается в некий допуск и точки лежат в пределах отрезков.. Понадобится понимание векторного и скалярного произведения векторов.

Answer 2

Основываясь на ответе MBo, я создал эти методы для определения взаимоотношения линий (в том числе определения пересечений), если вы заметили неверное решение в методе или у вас есть предложение, прошу помочь мне в нахождении наилучшего решения.

[Serializable]
public enum LinesRelationship
{
    Intersect,
    Parallel,
    Superposition,
    Equal
}
public static List<LinesRelationship> GetLinesRelationship(Vector3 a0, Vector3 a1, Vector3 b0, Vector3 b1, out Vector3 intersectionPoint, bool a0IsEnd = true, bool a1IsEnd = true, bool b0IsEnd = true, bool b1IsEnd = true, bool x = true, bool y = true, bool z = true)
{
    float uxy, uxz, uyz, u, tx, ty, tz, t;
    List<LinesRelationship> relationships = GetLinesRelationship(a0, a1, b0, b1, out intersectionPoint, out uxy, out uxz, out uyz, out u, out tx, out ty, out tz, out t, x, y, z);
    if (relationships.Contains(LinesRelationship.Intersect))
        if (!(a0IsEnd ? t >= 0 : true) || !(a1IsEnd ? t <= 1 : true) || !(b0IsEnd ? u >= 0 : true) || !(b1IsEnd ? u <= 1 : true))
            relationships.Remove(LinesRelationship.Intersect);
    return relationships;
}
public static List<LinesRelationship> GetLinesRelationship(Vector3 a0, Vector3 a1, Vector3 b0, Vector3 b1, out Vector3 intersectionPoint, out float uxy, out float uxz, out float uyz, out float u, out float tx, out float ty, out float tz, out float t, bool x = true, bool y = true, bool z = true)
{
    if (!x)
        a0.x = a1.x = b0.x = b1.x = 0;
    if (!y)
        a0.y = a1.y = b0.y = b1.y = 0;
    if (!z)
        a0.z = a1.z = b0.z = b1.z = 0;
    uxy = (b0.x - a0.x - (b0.y - a0.y) / (a1.y - a0.y) * (a1.x - a0.x)) / ((b1.y - b0.y) / (a1.y - a0.y) * (a1.x - a0.x) - (b1.x - b0.x));
    uxz = (b0.x - a0.x - (b0.z - a0.z) / (a1.z - a0.z) * (a1.x - a0.x)) / ((b1.z - b0.z) / (a1.z - a0.z) * (a1.x - a0.x) - (b1.x - b0.x));
    uyz = (b0.y - a0.y - (b0.z - a0.z) / (a1.z - a0.z) * (a1.y - a0.y)) / ((b1.z - b0.z) / (a1.z - a0.z) * (a1.y - a0.y) - (b1.y - b0.y));
    u = !float.IsNaN(uxy) ? uxy : (!float.IsNaN(uxz) ? uxz : uyz);

    tx = (b0.x + u * (b1.x - b0.x) - a0.x) / (a1.x - a0.x);
    ty = (b0.y + u * (b1.y - b0.y) - a0.y) / (a1.y - a0.y);
    tz = (b0.z + u * (b1.z - b0.z) - a0.z) / (a1.z - a0.z);
    t = !float.IsNaN(tx) ? tx : (!float.IsNaN(ty) ? ty : tz);
    intersectionPoint = (a1 - a0) * t + a0;
    List<LinesRelationship> list = new List<LinesRelationship>();
    if (a0 == b0 && a1 == b1)
        list.Add(LinesRelationship.Equal);
    if (a0 == b1 && a1 == b0 || a0 == b0 && a1 == b1)
        list.Add(LinesRelationship.Superposition);
    if ((a0 - a1).normalized == (b0 - b1).normalized || (a0 - a1).normalized == (b1 - b0).normalized)
        list.Add(LinesRelationship.Parallel);
    if (!(float.IsNaN(intersectionPoint.x) && a0.x - a1.x != 0 && b0.x - b1.x != 0 || float.IsNaN(intersectionPoint.y) && a0.y - a1.y != 0 && b0.y - b1.y != 0 || float.IsNaN(intersectionPoint.z) && a0.z - a1.z != 0 && b0.z - b1.z != 0))
        list.Add(LinesRelationship.Intersect);
    return list;
}