質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.19%

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

受付中

回答 6

投稿

  • 評価
  • クリップ 2
  • VIEW 3,820

sakubou_san

score 13

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

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 6

+3

まず、直線 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 で一致するかどうかでも直線上にあるかどうかを判定できますが、浮動小数の一致判定になるので、外積の方がいいです。
また、参考のリンク先には外積による線分上の判定も出ています。


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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2014/12/01 21:53

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

    キャンセル

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2014/12/01 11:00

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

    キャンセル

+1

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

コンピュータグラフィックでは、純粋な数学(幾何) だけでなく、計算誤差の検討や計算速度を考慮することが必要です。
例えばこんあ検討を...
- 点が線分上にあるか?(改)http://amuraba.blog.fc2.com/blog-entry-412.html

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

古い書籍 and 英語 になりますが、こんなものがあります。
- Graphics Gems http://tog.acm.org/resources/GraphicsGems/

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2014/12/01 21:50

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2014/12/01 18:01

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

    キャンセル

  • 2014/12/01 18:16

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

    キャンセル

0

参考ページを紹介します。
- 点と線分間の距離 http://d.hatena.ne.jp/ponkotuy/20110822/1314023755

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.19%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

閲覧数の多いCの質問