两线段交点

  假设有如下图的两段线段BA, CD,求交点E:

求线段与线段交点

  先求得C和D是否在向量BA两边,BA叉乘BC,BA叉乘BD,分别得到法向量两条法向量n1,n2,并单位化:
\vec n1 = normalize(BA \times BC)
\vec n2 = normalize(BA \times BD)

  得到的n1和n2都垂直于BA和CD组成的平面,通过点乘求的两条法向量夹角,便可知道C和D是否在向量BA两侧:
\vec n1 \cdot \vec n2 = \mid \vec n1 \mid \mid \vec n1 \mid cos\theta

  1. n1 x n2的结果如果大于0,锐角,说明C和D在向量BA同侧,BA和CD不可能相交。
\vec n1 \cdot \vec n2 > 0

  2. n1 x n2的结果如果小于0,钝角,说明C和D在向量BA两侧,BA和CD可能相交。
\vec n1 \cdot \vec n2 < 0

  3. 考虑到向量BA和CD有可能平行,BA和CD需要点乘求夹角,已证明是否平衡。

  同理,我们求得A和B是否分别在向量CD两侧。假设最终结果是,C和D在向量BA两侧,并且A和B也在向量CD两侧,两线段有交点。接下来我们求交点E得坐标。作BA垂直线C'D',以C为起点,CD投影C'D',CA投影C'O。在梯形CC'D'D中,满足以下等式:
\frac{C'O}{C'D'} = \frac{CE}{CD}

  C'O和C'D'长度已知,CD向量已知,因此可求得CE向量。

using UnityEngine;

public class Sample : MonoBehaviour
{
    private void Start()
    {
        //假设在XZ平面,忽略Y轴。
        Vector3 A = new Vector3(0, 0, 4);
        Vector3 B = new Vector3(0, 0, -1);
        Vector3 C = new Vector3(-2, 0, 1);
        Vector3 D = new Vector3(5, 0, 3);

        //尝试得到交点
        if (TryGetPointOfIntersection(B, A, C, D, out Vector3 resultPoint))
        {
            Debug.Log($"Sample.Start() : 交点为{resultPoint}");
        }
    }

    /// <summary>
    /// 尝试获取交点
    /// </summary>
    private bool TryGetPointOfIntersection(Vector3 fromPoint1, Vector3 toPoint1, Vector3 fromPoint2, Vector3 toPoint2, out Vector3 resultPoint)
    {
        if (!IsIntersect(fromPoint1, toPoint1, fromPoint2, toPoint2))
        {
            resultPoint = Vector3.zero;
            return false;
        }

        //两条向量
        Vector3 vector1 = toPoint1 - fromPoint1;
        Vector3 vector2 = toPoint2 - fromPoint2;

        //求向量1垂线.(必须单位化,这样点乘求的才是投影,你懂我意思吗)
        Vector3 perpendicularLine = new Vector3(vector1.z, 0, -vector1.x).normalized;

        //投影
        //相当于C'O
        float shadowVector1 = Vector3.Dot(toPoint1 - fromPoint2, perpendicularLine);

        //相当于C'D'
        float shadowVector2 = Vector3.Dot(vector2, perpendicularLine);

        //交点
        resultPoint = fromPoint2 + vector2 * (shadowVector1 / shadowVector2);

        return true;
    }

    /// <summary>
    /// 是否相交
    /// </summary>
    private bool IsIntersect(Vector3 fromPoint1, Vector3 toPoint1, Vector3 fromPoint2, Vector3 toPoint2)
    {
        return IsTwoSide(fromPoint1, toPoint1, fromPoint2, toPoint2) && IsTwoSide(fromPoint2, toPoint2, fromPoint1, toPoint1);
    }

    /// <summary>
    /// 两点是否在向量两侧
    /// </summary>
    private bool IsTwoSide(Vector3 fromPoint1, Vector3 toPoint1, Vector3 fromPoint2, Vector3 toPoint2)
    {
        Vector3 baseVector = toPoint1 - fromPoint1;
        Vector3 normal1 = Vector3.Cross(baseVector, fromPoint2 - fromPoint1).normalized;
        Vector3 normal2 = Vector3.Cross(baseVector, toPoint2 - fromPoint1).normalized;

        return Vector3.Dot(normal1, normal2) < 0;
    }
}

红色点为交点

Author : SunnyDecember
Date : 2019.11.17
原文

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
禁止转载,如需转载请通过简信或评论联系作者。