[C++] 線分交差判定

C++

コロナで大変ですが、就活が終了しました。

来年から社会人です。

頑張ります。

ソースコード

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

struct Point {
  double x;
  double y;
};

double norm(Point p0, Point p1) {
  return sqrt(pow(p1.x - p0.x, 2) + pow(p1.y - p0.y, 2));
}


double dot(Point p0, Point p1, Point p2) {
  return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
}


double cross(Point p0, Point p1, Point p2) {
  return ( p1.x - p0.x ) * ( p2.y - p0.y ) - ( p2.x - p0.x) * (p1.y - p0.y);
}

int positional_relationship(Point p0, Point p1, Point p2) {
  if(cross(p0, p1, p2) > 0) //反時計回り
    return 1;
  else if(cross(p0, p1, p2) < 0) //時計回り
    return -1;
  else if(dot(p0, p1, p2) < 0) //一直線上で反転向き
    return 2;
  else if(norm(p0, p1) < norm(p0, p2)) // 一直線上で同じ向き
    return -2;
  else //線分上に存在
    return 0;
}

bool isIntersected(Point p0, Point p1, Point p2, Point p3) {
  if(positional_relationship(p0, p1, p2) * positional_relationship(p0, p1, p3) <= 0 && positional_relationship(p2, p3 ,p0) * positional_relationship(p2, p3, p1) <= 0)
    return true;
  return false;
}

int main(void) {
  int q;
  cin >> q;
  Point p0, p1, p2, p3;

  for(int i = 0; i < q; i++) {
    cin >> p0.x >> p0.y >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y;
    if(isIntersected(p0, p1, p2, p3))
      cout << "1" << endl; //交差しているなら1を表示する
    else
      cout << "0" << endl; //交差していないなら0を表示する
  }

}

簡単な解説

まず、位置関係としては大きく分けて5種類あると思います。

それをif文を使って限定していくイメージです。

反時計回りではなかったら、次は時計回りかな見たいに範囲を狭めていきます。

交差判定の条件

反時計回りなら正の値を、時計回りなら負の値を返して、線分上にあるなら0を返すといった感じにしました。

今回は以上になります。

ではまた。

コメント

タイトルとURLをコピーしました