ei1333's page

距離

点(Point)と点(Point)の距離

点 $a$ と点 $b$ の距離は $|\overrightarrow {a- b}|$ である。

直線(Line)と点(Point)の距離

直線 $l$ と点 $p$ の距離は, 点 $p$ と点 $p$ の直線 $l$ に対する射影との距離である。

直線(Line)と直線(Line)の距離

直線 $l$ と直線 $m$ の距離は, $l, m$ が交差しているとき $0$, 交差していない時は直線 $l$ 上の適当な点 $l.a$ と点 $l.a$ の直線 $m$ に対する射影との距離である。

線分(Segment)と点(Point)の距離

点 $p$ の線分 $l$ に対する射影 $r$ を求める。

点 $r$ が線分 $l$ 上にあればそれと点 $p$ との距離, なければ線分 $l$ の両端の点 $l.a, l.b$ と点 $r$ との距離の min となる。

線分(Segment)と線分(Segment)の距離

線分 $a$ と線分 $b$ との距離を求める。

$a$ と $b$ が交差している場合は $0$, 交差していない場合は線分と点との距離に帰着させる。$a, b$ の両端の点と線分との距離の min をとればよい。

直線(Line)と線分(Segment)の距離

直線 $l$ と線分 $s$ の距離は, 交差している場合は $0$, 交差していない場合は $l$ と線分 $s$ の端点 $s.a, s.b$ との距離の min となる。

実装例

double Distance(const Point& a,const Point& b){
  return (a - b).abs();
}

double Distance(const Line& l,const Point& p) {
  return (p - Projection(l, p)).abs();
}

double Distance(const Line& l,const Line& m) {
  return Intersect(l, m) ? 0 : Distance(l, m.a);
}

double Distance(const Segment& s,const Point& p){
  Point r = Projection(s, p);
  if (Intersect(s, r)) return (r - p).abs();
  return min((s.a - p).abs(), (s.b - p).abs());
}

double Distance(const Segment& a,const Segment& b){
  if(Intersect(a, b)) return 0;
  return min(min(Distance(a, b.a), Distance(a, b.b)), min(Distance(b, a.a), Distance(b, a.b)));
}

double Distance(const Line& l,const Segment& s) {
  if (Intersect(l, s)) return 0;
  return min(Distance(l, s.a), Distance(l, s.b));
}