# Collisions of lines and a rectangle

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

## 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 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 on other sites
Multiple lines and just one rectangle. The sides of the rectangle are in the directicion of the coordinate axes.

##### 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.

 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.
 // 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; }  Edited by achild

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• ### Forum Statistics

• Total Topics
633390
• Total Posts
3011631
• ### Who's Online (See full list)

There are no registered users currently online

×