2点の頂点を結んだとき・・・

Question

C言語での質問です。
適当に2点（A,B)をとります。
その2点A,Bを結び線分とします。
そして、適当にもう一点(c)をとります。
このC点がAB線分上にあるかの判定を行いたいのですが、
参考にあるサイト、プログラムなどありませんでしょうか？

Answer 1

まず、直線 AB 上に点があるかどうかはベクトルの 外積 を使います。
外積は 符号付き面積 と呼ばれることもあり、
ベクトル AB, AC の外積は AB, AC を辺に持つ平行四辺形の面積となります。
この面積(外積)が 0 の時、 直線上にあります。

外積の値は次の式で求め、これが 0 かどうかで判定します。

/* ABx * ACy - ABy * ACx */
(xb - xa) * (yc - ya) - (yb - ya) * (xc - xa) 

cf. 平面幾何におけるベクトル演算 » 内積と外積

次に線分 AB 上にあるかどうかですが、
線は 2 点で表すので、プログラミングでは直線は次のような式で表すと扱いやすいです。

`
P = tA + (1-t)B

x = t・xa + (1 - t)xb
y = t・ya + (1 - t)yb
`

点 P (x, y) が直線上の点を表し、 t = 0 なら B で、 t = 1 なら A です。
この t が 0 以上 1 以下の時に線分上の点ということになります。

x (または y) で t を求め、これが範囲内にあるかどうかで判定します。

/* 
xc = t・xa + (1 - t)xb 
(xa - xb)t = xc - xb  */
(xc - xb)/(xa - xb)

なお、 この t が x, y で一致するかどうかでも直線上にあるかどうかを判定できますが、浮動小数の一致判定になるので、外積の方がいいです。
また、参考のリンク先には外積による線分上の判定も出ています。

プログラミングで点や図形を扱う分野を『計算幾何学』といいます。
外積を使うなどは知らないと思いつきにくいところなので、図形を扱うプログラムをやる場合は計算幾何学の基本的なところは抑えておいた方がいいと思います。

Comments

[sakubou_san]

回答ありがとうございます。
この手法ならば、ほぼ誤差が出ないですね
一度このアルゴリズムでコーディングしてみます。
幾何学の勉強不足でした。

Answer 2

三角不等式を用いればいいのではないでしょうか？
例えば、直線AB上に点Cがあるか判断する際、直線上にあるならばL = ((aからc)+(cからb))が(aからb)より小さい値になるはずですよね
cが直線上にない場合、必ずLは(aからb)よりも大きい値になります

プログラムで書いてみます。

#include <iostream>
#include <cstdio>
#include <complex.h>
#define EPS 1e-10
#define EQ ((abs((a)-(b))) < EPS)
using namespace std;
typedef complex<double> P;

bool point_is_on_line(P a, P b, P c) {
return(abs(a-c)+abs(b-c) < abs(a-b) + EPS);
}

int main(void) {
P a(1, 2), b(2, 3), c(3, 3);
if(point_is_on_line(a, b, c)) {
cout << "accept" << endl;
} else {
cout << "failed" << endl;
}
return(0);
}

Comments

[sakubou_san]

なるほど、そういう手があったんですね
ありがとうございます。

Answer 3

直接の回答にはなりませんが、参考情報を。

コンピュータグラフィックでは、純粋な数学(幾何) だけでなく、計算誤差の検討や計算速度を考慮することが必要です。
例えばこんあ検討を...

• 点が線分上にあるか？（改）http://amuraba.blog.fc2.com/blog-entry-412.html

コンピュータグラフィックをつかったゲームでは 大量の衝突判定や画像レンダリング計算 をリアルタイムで行う必要があり、いろいろな手法が開発されています。
そして計算手法については、たくさんの資料があります。

古い書籍 and 英語 になりますが、こんなものがあります。

• Graphics Gems http://tog.acm.org/resources/GraphicsGems/

コンピュータ関係の学校(高校、大学) では コンピュータグラフィック については最近はどんな教科書を使っているのでしょうか？

Comments

[sakubou_san]

回答ありがとうございます。
私は精密な計算が必要なため、今回の使用は遠慮しておきます
ですが、参考情報ありがとうございます。
ちなみに、私が使っている参考書は「GLUTによるOpenGL入門」と「ビジュアル情報処理CG・画像処理入門」と手元にないのですが幾何学の参考書を読んでいます

Answer 4

線分ABの距離 = 線分ACの距離+線分BCの距離
この条件をみたすときは線分上に点Cが存在すると思われますが、いかがでしょうか？

実装例を以下に示します。

#include<stdio.h>
#include<stdbool.h>
#include<math.h>

double pow2(double x) {
  return x * x;
}

// 線分ABの距離
double dist(double Ax,double Ay, double Bx, double By) {
  return sqrt( pow2(Ax-Bx) + pow2(Ay-By) );
}

// 点Cが線分AB上であれば true (端点を含む), それ以外は false
bool onSegment(double Ax,double Ay, double Bx, double By, double Cx, double Cy) {
  return dist(Ax,Ay,Bx,By) == ( dist(Ax,Ay,Cx,Cy) + dist(Bx,By,Cx,Cy) );
}

int main(){
  double Ax = 0, Ay = 0;
  double Bx = 5, By = 0;
  double Cx = 2, Cy = 0;
  if( onSegment(Ax,Ay,Bx,By,Cx,Cy) ) {
    puts("on");
  } else {
    puts("off");
  }
  return 0;
}

Answer 5

参考ページを紹介します。

• 点と線分間の距離 http://d.hatena.ne.jp/ponkotuy/20110822/1314023755

• 線分上の最も近い点 http://qiita.com/yuba/items/2f35d1e5e162f44fc1b3

点と線分の距離 （または距離の２乗）が 十分に小さい なら、線分上の点だと判断すれば良いとおもいます。

Answer 6

実践したことはないのですが「線分 交点 座標 プログラム」で検索するとヒントが有るかも知れません。点Cを「短い線」として交点を求めてはどうでしょうか。

Comments

[katoy]

> ... 点Cを「短い線」...
線 より 半径の小さい円 として考えて、 円と線分の交点が存在するか? で判定するほうが良い気がします。

[BlueMoon]

コメント有難うございます。その方が実用的と思えます。