点と移動する線分の交点 - ゲームプログラミングというゲームを攻略するWIKI

問題を定義する

• (x, y) で表される点と
• (x1 + t*dx1, y1 + t*dy1) から (x2 + t*dx2, y2 + t*dy2) への線分

の交わる t を求める。

ただし２回交わるときは０位上の小さい方を使う。

問題を整理する

x - (x1 + t*dx1) : y - (y1 + t*dy1 = (x2 + t*dx2) - (x1 + t*dx1) : (y2 + t*dy2) - (y1 + t*dy1

外項の積は内項の積

(x - (x1 + t*dx1))*(*1) = (y - (y1 + t*dy1))*(*2)

a = (dy1*dx2 - dx1*dy2) b = (dy2*x - dy1*x + dx1*y - dx2*y + dy1*x2 + y1*dx2 - dx1*y2 - x1*dy2) c = y2*x - y1*x + x1*y - x2*y + y1*x2 - x1*y2 = 0

とすると

a*t*t + b*t + c = 0

となるので、解の公式が使える。

例外的な状況

• a=0 の場合は解の公式が使えない。

実装

というわけで以下のようなコードになる。

double annexation(double x, double y, double x1, double y1, double dx1, double dy1, double x2, double y2, double dx2, double dy2)
{
	double a = dy1*dx2 - dx1*dy2;
	double b = dy2*x - dy1*x + dx1*y - dx2*y + dy1*x2 + y1*dx2 - dx1*y2 - x1*dy2;
	double c = y2*x - y1*x + x1*y - x2*y + y1*x2 - x1*y2;
	if (a == 0)
	{
		// t*b + c = 0
		if (b != 0)
		{
			return NAN;
		}
		return - c / b;
	}
 
	double s = b*b - 4*a*c;
	if (s <= 0)
	{
		return NAN;
	}
 
	double r = sqrt(s);
 
	double t1 = (- b + r) / (2*a);
	double t2 = (- b - r) / (2*a);
 
	if (t1 < t2)
	{
		if (t2 < 0)
		{
			return NAN;
		}
		if (t1 < 0)
		{
			return t2;
		}
		return t1;
	}
	else
	{
		if (t1 < 0)
		{
			return NAN;
		}
		if (t2 < 0)
		{
			return t1;
		}
		return t2;
	}
}