perogram

線分の交差判定 c++ Judgment of intersection of line segments

関数

// 交差判定セット
typedef complex<double> C;
double cross(C a, C b){
    return a.real() * b.imag() - a.imag() * b.real();
}
// ベクトル p0->p1, q0->q1
bool is_intersect(C p0, C p1, C q0, C q1){
    // p側から見た交差チェック
    auto v0 = p1 - p0;
    auto v1 = q0 - p0;
    auto v2 = q1 - p0;
    if(cross(v0, v1) * cross(v0, v2) >= 0){
        return false;
    }
    // q側から見た交差チェック
    v0 = q1 - q0;
    v1 = p0 - q0;
    v2 = p1 - q0;
    if(cross(v0, v1) * cross(v0, v2) >= 0){
        return false;
    }
    return true;
}

使い方

C p0(0, A);
C p1(X, B);

C q0(Sx, Sy);
C q1(Tx, Ty);

bool f = is_intersect(p0, p1, q0, q1);
if(f){
    p_yes();
}else{
    p_no();
}

追記:Ver 2

// 交差判定セット
typedef complex<double> C;
// 外戚
double cross(C a, C b){
    return a.real() * b.imag() - a.imag() * b.real();
}
// 内積
double inner_product(C a, C b){
  return a.real() * b.real() + a.imag() * b.imag();
}
// a is in between b and c?
bool in_between(C a, C b, C c){
  auto v1 = b-a;
  auto v2 = c-a;
  if(inner_product(v1, v2)<=0){
    return true;
  }else{
    return false;
  }
}
// ベクトル p0->p1, q0->q1
bool is_intersect(C p0, C p1, C q0, C q1){
    // ちょうど接する時はtrueにする
    // 平行時も判定できるように(内分点で判定)
    if(
    in_between(p0, q0, q1) ||
    in_between(p1, q0, q1) ||
    in_between(q0, p0, p1) ||
    in_between(q1, p0, p1)
    ){
      return true;
    }

    // 以降、通常時の交差チェック
    // p側から見た交差チェック
    auto v0 = p1 - p0;
    auto v1 = q0 - p0;
    auto v2 = q1 - p0;
    if(cross(v0, v1) * cross(v0, v2) >= 0){
        return false;
    }
    // q側から見た交差チェック
    v0 = q1 - q0;
    v1 = p0 - q0;
    v2 = p1 - q0;
    if(cross(v0, v1) * cross(v0, v2) >= 0){
        return false;
    }
    return true;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // 複素数の宣言
    // C p0(1, 2);

    // 並行&重なる
    debug(is_intersect({0,0}, {1,0}, {0.5,0}, {2,0}), true);

    // 並行&重ならない
    debug(is_intersect({0,0}, {1,0}, {2,0}, {3,0}), false);

    // 重なる
    debug(is_intersect({0,0}, {1,2}, {-1,1}, {10,0}), true);

    // 垂直に刺さる(これは微妙なところ)基本trueだと思われる
    debug(is_intersect({0,0}, {2,2}, {1,1}, {2,0}), true);

    return 0;
}

Verified