線分交差判定について．

Question

長方形と線分が交差するかどうかの判定プログラムを組もうとしているのですが，わかりません．
以下はのソースコードは，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/ツール等のバージョンなど)
より詳細な情報

Answer 1

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

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

Comments

[ohana1515]

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

[tnd-.-b]

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

[ohana1515]

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

[tnd-.-b]

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

Answer 2

こんにちは。

現在のソースは、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の入力方法はもう少し工夫するべきですが、それなりにたいへんですので、まずは四角形でやってみることをお勧めします。

Answer 3

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

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

Comments

[ohana1515]

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

[yuba]

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