线段相交

记两线段为(AB)与(CD)

一、方法一

1. 先判断线段是否共线

依据共线向量叉乘为零来判断
(vec{AB})与(vec{CD})叉乘是否为0，如果为0则共线

2. 在不共线情况下判断是否相交

依据(0 leq t leq 1)且(0 leq u leq 1)来判断，其中(t)和(u)的推导过程如下：

假设交点为(P)，则有(P = A + vec{AB} * t, quad t in [0, 1])且 (P = C + vec{CD} * u, quad u in [0, 1])
即

(A + vec{AB} * t = C + vec{CD} * u quad ==> quad vec{AB} * t = vec{AC} + vec{CD}*u)

由于向量自身的叉乘为0，所以上式两边同时叉乘(vec{CD})可得：

(vec{CD} times vec{AB} * t = vec{CD} times vec{AC})，

变形可得：

(t = frac{vec{CD} times vec{AC}}{vec{CD} times vec{AB}}， t in [0, 1])

同理，两边同时叉乘(vec{AB})可得：(-vec{AB} times vec{CD} * u = vec{AB} times vec{AC})，所以：

(u = frac{vec{AB} times vec{AC}}{vec{CD} times vec{AB}}， u in [0, 1])

3. 在相交的情况下计算交点

依据第2步计算的(t)和(u)，代入：(P = A + vec{AB} * t, quad t in [0, 1])且 (P = C + vec{CD} * u, quad u in [0, 1])即可求出交点(P)的坐标

代码实现

struct Point {
  float x, y;
  Point(const float& px = 0, const float& py = 0) : x(px), y(py) {}
  Point operator+(const Point& p) const {
    return Point(x + p.x, y + p.y);
  }
  Point& operator+=(const Point& p) {
    x += p.x;
    y += p.y;
    return *this;
  }
  Point operator-(const Point& p) const {
    return Point(x - p.x, y - p.y);
  }
  Point operator*(const float coeff) const {
    return Point(x * coeff, y * coeff);
  }
};

float Dot2d(const Point & A, const Point & B) {
  return A.x * B.x + A.y * B.y;
}
 
float Cross2d(const Point & A, const Point & B) {
  return A.x * B.y - B.x * A.y;
}

bool IsInsert(const Point& A, const Point& B, const Point& C, const Point&D)
{
     Point AB = B - A;
     Point CD = D - C;
     float det = Cross2d(CD , AB);

      // This takes care of parallel lines
      if (std::fabs(det) <= 1e-14) {
        return false;
      }

      Point AC= C - A;

      double t = Cross2d(CD, AC) / det;
      double u = Cross2d(AB, AC) / det;

      if (t > -EPS && t < 1.0f + EPS && u > -EPS && u < 1.0f + EPS) {
         return true;
         // intersections P = A + AB * t;
      }
}

二、方法二

1. 先判断线段是否共线

同方法一

2. 在不共线情况下判断是否相交

依据线段相交则一条线段两端点位于另一线段两侧来判断
相交情况下有如下两种情形：

判断是否在两侧可以依据两个向量的叉乘(右手法则)，如下：

(vec{OA} times vec{OB} > 0)，则(vec{OB})在(vec{OA})的逆时针方向
(vec{OB} times vec{OA} < 0)，则(vec{OA})在(vec{OB})的顺时针方向

所以在相交的两种情况下有：

• 情况1
  点(C)和(D)在(AB)两侧，则有：

((vec{AC} times vec{AB}) cdot (vec{AD} times vec{AB}) < 0)

点(A)和(B)在(CD)两侧，则有：

((vec{CA} times vec{CD}) cdot (vec{CB} times vec{CD}) < 0)

• 情况2
  由于端点在线段上，所以有一个叉乘为0，因此：

((vec{AC} times vec{AB}) cdot (vec{AD} times vec{AB}) = 0) 且 ((vec{CA} times vec{CD}) cdot (vec{CB} times vec{CD}) = 0)

代码实现

bool IsInsert(const Point& A, const Point& B, const Point& C, const Point&D)
{
     Point AB = B - A;
     Point CD = D - C;
     Point AC = C - A; 
     Point AD = D - A;
     Point CB = B - C;
     Point CA = -AC;  
     float det = Cross2d(CD , AB);

     // This takes care of parallel lines
     if (std::fabs(det) <= 1e-14) {
        return false;
     }

     if (Cross2D(AC, AB) * Cross2D(AD, AB) <= EPS  &&  Cross2D(CA, CD) * Cross2D(CB, CD)< EPS) {
         return true; 
     }
}

参考链接

line_intersection
Two_line_segments