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

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

行動規範の内容に同意します

回答6件

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

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

lang
1/* ABx * ACy - ABy * ACx */
2(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 を求め、これが範囲内にあるかどうかで判定します。

lang
1/* 
2xc = t・xa + (1 - t)xb 
3(xa - xb)t = xc - xb  */
4(xc - xb)/(xa - xb)

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

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

投稿2014/12/01 02:37

yohshiy

総合スコア863

sakubou_san

2014/12/01 12:53

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

行動規範の内容に同意します

三角不等式を用いればいいのではないでしょうか？
例えば、直線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);
}

投稿2014/11/30 17:27

tukejonny

総合スコア50

sakubou_san

2014/12/01 02:00

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

行動規範の内容に同意します

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

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

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

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

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

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

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

投稿2014/12/01 03:29

katoy

総合スコア22324

sakubou_san

2014/12/01 12:50

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

行動規範の内容に同意します

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

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

C
1#include<stdio.h>
2#include<stdbool.h>
3#include<math.h>
4
5double pow2(double x) {
6  return x * x;
7}
8
9// 線分ABの距離
10double dist(double Ax,double Ay, double Bx, double By) {
11  return sqrt( pow2(Ax-Bx) + pow2(Ay-By) );
12}
13
14// 点Cが線分AB上であれば true (端点を含む), それ以外は false
15bool onSegment(double Ax,double Ay, double Bx, double By, double Cx, double Cy) {
16  return dist(Ax,Ay,Bx,By) == ( dist(Ax,Ay,Cx,Cy) + dist(Bx,By,Cx,Cy) );
17}
18
19int main(){
20  double Ax = 0, Ay = 0;
21  double Bx = 5, By = 0;
22  double Cx = 2, Cy = 0;
23  if( onSegment(Ax,Ay,Bx,By,Cx,Cy) ) {
24    puts("on");
25  } else {
26    puts("off");
27  }
28  return 0;
29}