Sign in to follow this  
LonelyStar

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

Recommended Posts

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

Share this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by LonelyStar
@Elco
Sorry 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 this post


Link to post
Share on other sites

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