Fast way to find out, if a line segment touches a quadrat
Author
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
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-
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-
Author
@Elco
Sorry for my bad english. What I mean with a "quadrat" is a rectangle with the same width as height.
Sorry for my bad english. What I mean with a "quadrat" is a rectangle with the same width as height.
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:
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.
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.
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?
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?
Author
Hi and thanks for answers your answers!
@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
@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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
