# Fast way to find out, if a line segment touches a quadrat

## Recommended Posts

LonelyStar    192
Hi everybody, I want to find out if some line-segments touches a quadrat. Now, I could find the intersection of the line segment with all 4 sides of the quadrat and aditional test of the start and/or end point are within the quadrat. Would work, but I wonder if there is a faster way. Any Ideas? Thanks! Nathan

Eelco    301

##### Share on other sites
Cygon    1219
Afaik, that's the only way to do it.

There still might be some clever alternative way to do it, the appropriate magic words for google are probably something similar to "line segment rectangle intersection test" ;)

-Markus-

##### Share on other sites
LonelyStar    192
@Elco
Sorry for my bad english. What I mean with a "quadrat" is a rectangle with the same width as height.

##### Share on other sites
jyk    2094
If you just need a boolean result, but not the actual points of intersection, the separating axis approach is the fastest algorithm I know of. Here's some code, which you may be able to adapt to your needs:

bool AABB2::IntersectSeg2(const Segment2& s) const{    Vector2 dir = s.GetDirection() * 0.5f;    Vector2 diff = (s.GetOrigin() + dir) - m_center();    if (m_extents[0] + Math::Fabs(dir[0]) < Math::Fabs(diff[0]))        return false;    if (m_extents[1] + Math::Fabs(dir[1]) < Math::Fabs(diff[1]))        return false;    Vector2 perp = dir.Perp(); // Perp() returns -y, x    if (GetProjectedRadius(perp) < Math::Fabs(diff.Dot(perp)))        return false;    return true;}float AABB2::GetProjectedRadius(const Vector2& axis) const{    // Absolute() returns the vector with all components set to their absolute values    return m_extents.Dot(axis.Absolute());}

The line segment is in origin-direction form, and the AABB is in center-extents form. The line segment direction vector is not normalized, i.e. it represents the full length of the segment.

##### Share on other sites
To get accurate answers you need to specify your problem fully before asking. Unfortunately there's still information missing. Specifically, does the line segment lie in the plane of the square? That is, is the problem 2D or 3D?

##### Share on other sites
DrGUI    402
Quote:
 Original post by LonelyStar@ElcoSorry for my bad english. What I mean with a "quadrat" is a rectangle with the same width as height.

Am I missing something or is that a square?

##### Share on other sites
LonelyStar    192
@DrGUI: Yes, I think a square is exactly what I mean.
@jyk: Thank, I think what you posted is exactly what I need.
Greetings,
Nathan