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

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

ただいまの
回答率

87.93%

線分交差判定について.

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 4,379

score 13

長方形と線分が交差するかどうかの判定プログラムを組もうとしているのですが,わかりません.
以下はのソースコードは,2線分が交差するかどうかを判定するプログラムです.
線分同士の交差は,或る程度理解することができたのですが,ここからどこをどう変えれば,長方形と線分の交差にできるのかがわからず,行き詰っています.
よければ,助言いただけないでしょうか?

該当のソースコード

#include <stdio.h>

/**************************/
/* ベクトルの大きさの2乗 */
/*************************/
double norm(double *x)
{
    return x[0] * x[0] + x[1] * x[1];
}****

/****************************/
/* 2つのベクトルの内積      */
/*      a,b : 2つのベクトル */
/****************************/
double dot(double *a, double *b)
{
    return a[0] * b[0] + a[1] * b[1];
}

/******************************/
/* 2つのベクトルの外積(z成分) */
/*      a,b : 2つのベクトル   */
/******************************/
double cross(double *a, double *b)
{
    return a[0] * b[1] - a[1] * b[0];
}

/***************************/
/* 点と線分の関係          */
/*      p0,p1,p2 : 3つの点 */
/***************************/
int ccw(double *p0, double *p1, double *p2)
{
    int sw = 0;
    double a[2], b[2], EPS = 1.0e-8;

    a[0] = p1[0] - p0[0];
    a[1] = p1[1] - p0[1];
    b[0] = p2[0] - p0[0];
    b[1] = p2[1] - p0[1];
    if (cross(a, b) > EPS)   // 点p2は線分p0-p1の反時計方向
        sw = 1;
    else if (cross(a, b) < -EPS)   // 点p2は線分p0-p1の時計方向
        sw = -1;
    else if (dot(a, b) < -EPS)   // 点p2は線分p0-p1の手前
        sw = 2;
    else if (norm(a) < norm(b))   // 点p2は線分p0-p1の先
        sw = -2;

    return sw;   // 点p2は線分p0-p1の上
}

/************************************/
/* 線分p1-p2と線分p3-p4の交点の有無 */
/************************************/
int isIntersect(double *p1, double *p2, double *p3, double *p4)
{
    int sw = 0;   // 交点なし

    if (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0)
        sw = 1;   // 交点あり

    return sw;
}

int main()
{
    double a[2], b[2], c[2], d[2];
    int sw;

    printf("線分ABにおける点Aの座標(x, y)");
    scanf_s("%lf %lf", &a[0], &a[1]);
    printf("線分ABにおける点Bの座標(x, y)");
    scanf_s("%lf %lf", &b[0], &b[1]);
    printf("線分CDにおける点Cの座標(x, y)");
    scanf_s("%lf %lf", &c[0], &c[1]);
    printf("線分CDにおける点Dの座標(x, y)");
    scanf_s("%lf %lf", &d[0], &d[1]);

    sw = isIntersect(a, b, c, d);

    if (sw > 0)
        printf("交点あり\n");
    else
        printf("交点なし\n");

    return 0;
}

試したこと

四角形の任意の辺と線分のベクトルの外積が0以下になればいいということは調べていると分かったのですが,実際どう組みかえればいいのかがわかりませんでした.

補足情報(言語/FW/ツール等のバージョンなど)

より詳細な情報

  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 3

checkベストアンサー

0

main関数内にて、長方形の頂点 A,B,C,D(時計回り) と、線分の端点α, β を得る(scan_fする)ように変更。
以下の組み合わせに対して、線分交差判定関数(isIntersect)を呼ぶ。
・A-B、α-β
・B-C、α-β
・C-D、α-β
・D-A、α-β
・A-C、α-β
・B-D、a-β
どれか1つでも「交差している」と判定されれば、線分は長方形に交差している。

ベクトルの計算はあまりとくいじゃないですが、大体こんな感じになるかと思います。
線分の端点と各頂点の位置関係によって絞り込むような処理も必要になるかもしれません。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/07/15 01:45

    交点の有無とmain関数内のみを変更すればよいということでしょうか?
    内積,外積,点と線分の関係などの中身は変更しなくて大丈夫なんでしょうか.

    キャンセル

  • 2016/07/15 08:16

    isIntersect()という関数が正しく動くのであれば、細かい関数群は変更しなくても良いかと思います。
    たとえば頂点の位置関係を判定するための新しい関数が追加になる可能性はありますが。

    キャンセル

  • 2016/07/15 13:09

    四角形ABCDと線分αβで交差判定できました!
    各頂点の座標を入力することでできました.
    おこがましいかもしれませんが,四角形の辺の長さを入力して交差判定することは結構難しくなってしまうのでしょうか?

    キャンセル

  • 2016/07/19 08:34

    少なくとも2つの頂点座標が必要です。
    辺の長さだけだと、四角形の位置(角度)が一意にならないので、交差判定はできません。

    キャンセル

0

線分の交差がわかるのであれば、
長方形を構成する点A,B,C,Dを結ぶ線分AB,BC,CD,DAが
直線の線分と交差しているか判定すればいいのではないでしょうか?

さらに、交差してないが、直線が長方形内部にある場合に交差していると判定するなら、
直線を構成する2点が長方形内にあるかの判定も合わせて行えばいいと思います。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/07/14 10:00

    言葉に語弊がありました.申し訳ありません.
    線分交差の理屈はわかったのですが,プログラミングに関しては全くの初心者でありまして,上記のソースコードも文献を見ながら書いたものになります.どの式がここに該当する.などは理解できたのですが,いざ長方形となるとどこをいじればよいのかがわからなかったためしです.
    うまく言葉に表せているかわかりませんが.未熟で申し訳ないです.

    キャンセル

  • 2016/07/14 10:01

    それだと不十分で、線分が長方形の対角線を串刺しにしているときに交差していると判定できません。

    キャンセル

0

こんにちは。

現在のソースは、a, b, c, dの4点の座標を入力して、線分abと線分cdが交わるかどうか判定してますね?
ならば、四角形abcdの各頂点a, b, c, dの4点の座標と、追加で2点x, yを入力し、下記を判定すれば良いと思います。

線分abと線分xyが交わるかどうか?
線分bcと線分xyが交わるかどうか?
線分cdと線分xyが交わるかどうか?
線分daと線分xyが交わるかどうか?

「四角形と線分が交わる」=「四角形の各辺と線分が交わる」であればこれで行ける筈です。
(線分が頂点で交わる時に注意して下さい。)

なお、長方形∈四角形ですので、abcdの入力方法はもう少し工夫するべきですが、それなりにたいへんですので、まずは四角形でやってみることをお勧めします。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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