3 replies to this topic

[TheUnbeliever]

I've done some searching, and haven't got anywhere really. I'm trying to find (an) algorithm(s) to a) find if a line intersects a rectangle and b) to find the intersection points of a line and a rectangle. If it helps, the rectangle will always be aligned with the x and y axes (this is 2D). This is for a very simple AI to avoid rectangular obstacles - I want to cull all the obstacles that it definitely won't hit (hence (a), above) and then find the first intersection point of the line with the rectangle, steering round the obstacle to whichever direction requires least angle change (hence (b), above). This line is obviously an extension of the velocity vector, by:

Line vectorExtend(Vector2 V)
{
    Line LV = new Line(new Point<float>(0, 0), new Point<float>((V.X, V.Y));
}

EDIT: I realise that I could find the line that makes up each side of the rectangle, then find the intersection of the velocity line and each of these lines, ignoring those which are outwith the triangle (i.e. collide with the line I get by projecting the sides, but not the sides themselves). Unfortunately, while I can do this on paper, I don't know any way of doing it programmatically that isn't overkill (surely there's a more efficient way for 2 lines than doing it the linear algebra way using the inverse of matrices).

[xissburg]

You know the parametric line equation? if not. it is a function that returns you the point on the line according to the value of the scalar you give as argument for it:

P(s) = P0 + s*(P1 - P0)
where P1 and P0 are two points on the line. Going from s=0 to s=1 you travel from P0 to P1. Its very easy to understand how it works.

You just need to find the value of s that makes the x component of the P(s) function equal to the x component of the horizontal lines of the rectangle(the y component is the same of this horiazontal line) and the same for the y component and the vertical lines of the sides of the rectangle(the x component is the same of this vertical line). The intersection which gives you the smaller value for s is the first intersection. Of course you'll also need to check if the intersection point is inside the lines of the box...you can optmize it a bit by excluding the sides of the boxes that are backfacing P0. And take care about parallel lines. I would write a code for you but I dont have enough time to do now :(...anyway, hope this helps ;)

[TheUnbeliever]

Sorry for the slow reply, I just discovered that C# generics are very different from how I thought they were (similar to C++ templates) and so had to write a fair bit of support code to get them to work as I wanted/needed.

That looks genuinely useful, I'll just need to code it up now, thanks. :-)

[papalazaru]

I'll give you the code :)

bool SegmentIntersect1D(const float c, const float r, const float a, const float b, float& t0, float& t1)

{

	const float threshold = 1.0e-8f;

	const float min = c - r;

	const float max = c + r;

	const float d   = b - a;

	

	if (fabs(d) < threshold)

	{

		return (a >= min && a <= max);

	}



	const float id  = 1.0f / d;



	float u0, u1;

	u0 = (min - a) * id;

	u1 = (max - a) * id;



	if (u0 > u1) 

	{

		swapf(u0, u1);

	}



	if (u1 < t0 || u0 > t1)

	{

		return false;

	}



	t0 = max(u0, t0);

	t1 = min(u1, t1);



	if (t1 < t0)

	{

		return false;

	}



	return true; 

}



// segment : [A, B].

// Oriented Box : [C, E, D[3]].

// result : [tenter, texit].

bool SegmentIntersectBox(const Vector& A, const Vector& B, const Vector& C, const Vector& R, const Vector D[3], float& t0, float& t1)

{

	t0 = 0.0f;

	t1 = 1.0f;



	for(int i = 0; i < 3; i ++)

	{

		if (!SegmentIntersect1D(C.DotProduct(D[i]), R[i], A.DotProduct(D[i]), B.DotProduct(D[i]), t0, t1)) 

		{

			return false;

		}

	}

	return true;

}



// segment : [A, B].

// Oriented Box : [C, E, D[3]].

// result : [Pnear, Pfar].

bool SegmentIntersectBox(const Vector& A, const Vector& B, const Vector& C, const Vector& R, const Vector D[3], Vector& Pnear, Vector& Pfar)

{

	float t0, t1;

    if (!SegmentIntersectBox(A, B, C, R, D, t0, t1))

	{

		return false;

	}

	

	Pnear = A + t0 * (B - A);

	Pfar  = A + t1 * (B - A);

	return true;



}

It's in 3D, but 2D, it's the same, it's just one less dimension.