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

• http://perogram.hateblo.jp/entry/abc016_4
• この記事を関数として切り出した
• ※1番上のを安易に使うと誤判定する場合があります

関数（追記：❌）

// 交差判定セット
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（追記：AOJで通らないので❌）

• http://gihyo.jp/dev/serial/01/geometry/0007?page=1
• ここにあるように、平行時のチェックが抜けていたので対応
• 蟻本p227 on_segに似ている

// 交差判定セット
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

• POJ https://vjudge.net/solution/22941500

整数バージョン（AOJなので漏れないはず）✅

• verified
  • http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B
  • AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4867237#2

// 交差判定セット（整数VER）
typedef complex<ll> C;
// 外積
ll cross(C a, C b){
    return a.real() * b.imag() - a.imag() * b.real();
}
// 内積
ll dot(C a, C b){
  return a.real() * b.real() + a.imag() * b.imag();
}
// a is in b and c ?
bool is_in(C a, C b, C c){
  if(a==b)return true;
  if(a==c)return true;
  C v0 = b-a;
  C v1 = c-a;
  if(cross(v0,v1)!=0)return false;// 同一線上にない
  if(dot(v0,v1)<0)return true; // 逆向きならin
  return false;
}
// ベクトル p0->p1, q0->q1
bool is_intersect(C p0, C p1, C q0, C q1){

  {
    // 同じ点があるなら交差
    if(p0==p1)return true;
    if(p0==q0)return true;
    if(p0==q1)return true;
    if(p1==q0)return true;
    if(p1==q1)return true;
    if(q0==q1)return true;
  }

  bool is_parallel = false;
  {
    C v = p0-p1;
    C w = q0-q1;
    if(cross(v,w)==0) is_parallel=true;
  }

  if(is_parallel){
    // 包含・重なり・ギリギリ接触を交差とする

    if(is_in(p0,q0,q1))return true;
    if(is_in(p1,q0,q1))return true;

    if(is_in(q0,p0,p1))return true;
    if(is_in(q1,p0,p1))return true;

    return false;
  }

  // 以降、平行ではないとする

  // 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;
}