Sign in to follow this  

Collisions of lines and a rectangle

This topic is 2049 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a rectangle and a lot of line segments on the 2d plane, and I want to check if any of the line segments touches the interior of the rectangle. I know how to check that for a single line, but I have so many lines that the brute force approach is not efficient. What kind of algorithm cound I use?

Share this post


Link to post
Share on other sites
To clarify, do you have multiple lines and just one rectangle, or do you have multiple lines and multiple rectangles to check against each other?

Share this post


Link to post
Share on other sites
Since the line itself can be used to define the AABB it sits in, you might try testing the AABB of each line to the real AABB you are testing against. If they intersect, do the actual line-segment to AABB test.

If that doesn't make it fast enough, divide your world up in some way. Partition it into a regular grid, or use a quad tree or something. Then it is very easy and quick to tell who might potentially be touching the rectangle in the middle, and only test those.

[edit] Also here is my AABB to Line Segment test. I obviously don't know how it compares to yours, but it's pretty fast as is.
[CODE]
// Collision detection 2d: Aabb and Line Segment
inline bool Cd2ALs(const Aabb2 &a, const LineSeg2 &ls) {
// Based on http://www.gamedev.net/topic/338987-aabb---line-segment-intersection-test/ with bugfix.
float hlx = (ls.x2 - ls.x1) * .5f;
float hly = (ls.y2 - ls.y1) * .5f;
float hax = (a.maxX - a.minX) * .5f;
float hay = (a.maxY - a.minY) * .5f;
float cx = fabs((ls.x1 + hlx) - (a.minX + hax));
float cy = fabs((ls.y1 + hly) - (a.minY + hay));
float adx = fabs(hlx);
float ady = fabs(hly);
if (cx > hax + adx) // Check projection onto x axis
return false;
if (cy > hay + ady) // Check projection onto y axis
return false;
if (adx * cy + ady * cx > ady * hax + adx * hay + .00001f) // Check proj. onto axis perp. to line
return false;
return true;
}
[/CODE] Edited by achild

Share this post


Link to post
Share on other sites

This topic is 2049 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this