[C++] 線分と線分の距離

C++

就活で大変でしたが、頑張って更新していきたいと思います。

ってことで今回は線分と線分の距離について投稿していきます。

ソースコード

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

using namespace std;

struct Point {
  double x;
  double y;
};

double min(double a, double b) {
  if(a < b)
    return a;
  else
    return b;
}

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


double distance(Point p0, Point p1, Point p2) {
  if(dot(p0, p1, p2) < 0)
    return norm(p0, p2);
  else if(dot(p1, p0, p2) < 0)
    return norm(p1, p2);
  else
    return fabs( cross(p0, p1, p2) ) / ( norm(p0, p1) );
}


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;
    double min_dist = 0.0;
    if(isIntersected(p0, p1, p2, p3)) {
      printf("%.10lf\n", min_dist);
      continue;
    }
  
    //printf("%lf %lf\n", distance(p0, p1, p2), distance(p0, p1, p3));
    min_dist = min(min( distance(p0, p1, p2), distance(p0, p1, p3) ), min( distance(p2, p3, p0), distance(p2, p3, p1) ) );
    printf("%.10lf\n", min_dist); //ここで距離の表示
  }

}

解説

上の画像の解説と通りです。

この問題を解いているとき⓵の方しか求めていなくて解くのに時間がかかってしまいました。

なのでしっかり⓵と⓶どっちもしっかり求めて小さい方を選択するのが正しいやり方です。

もちろん交差したら距離は0になりますよ笑

今回は以上になります。

ではまた。

コメント

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