Some simple geometry algorithms (rectangle inersect / line within rectangle)

[lozina]

Anyone good with the geometry algorithms?

I need an algorithm which detects if *any* point of a line is within a given rectangle

and:

an algorithm which detects if *any* point of a rectangle is within another given rectangle (though maybe the algorithm above can be used on the 4 sides for this one)

the thing is though, it HAS to be fast. I cant have any brute force method I need the most efficient streamlined way to do it...

So far my searching has found plenty of algorithms for detecting if one rectangle is ENTIRELY within another - but thats no good. Also I found intersection algorithms for rectangles but they do extra work by calculating the intersected areas - performance hit for me.

 

[PhatoseAlpha]

2d or 3d?

 

[Markbnj]

Rectangles intersecting with rectangles is easy, because if two rects intersect then one of the four corners of one of the rectangles must be within the bound of the other. So in the worst case you have to check eight points against two bounds. Shouldn't be too slow, and in most cases you can bail well before all eight are checked.

I haven't thought about either problem in a long while, but there must be plenty of highly optimized algorithms available for both these problems. Or does noone have to do primitives anymore? 🙂

2d or 3d?

Good question. I was assuming 2D. If it's 3D then you need a generalized algorithm for planar intersection.

 

[PhatoseAlpha]

I would expect for the former question in 2d, it should be fairly straightforward.

Any line that touches or passes through a rectangle will pass either through two opposite sides or two adjacent sides. Thus, if you check the intersection of the line against two paralell sides, if it intersects the rectangle, it must intersect at least one of them.

So, use two paralell sides, and check for their intersection. I'd likely treat each side as an actual line, calculate the intersections of the side and the line you're comparing, then determine if it is within the line segment that is the line. Do it for two opposite sides, and if either one comes up, it intersects - if not, it doesn't.

 

[lozina]

It's 2D

Rectangles intersecting with rectangles is easy, because if two rects intersect then one of the four corners of one of the rectangles must be within the bound of the other. So in the worst case you have to check eight points against two bounds. Shouldn't be too slow, and in most cases you can bail well before all eight are checked.

Yeah good point, I'll have a maximum of 4 points to check if they are contained within this one rectangle. thanks.

 

[lozina]

I would expect for the former question in 2d, it should be fairly straightforward.

Any line that touches or passes through a rectangle will pass either through two opposite sides or two adjacent sides. Thus, if you check the intersection of the line against two paralell sides, if it intersects the rectangle, it must intersect at least one of them.

So, use two paralell sides, and check for their intersection. I'd likely treat each side as an actual line, calculate the intersections of the side and the line you're comparing, then determine if it is within the line segment that is the line. Do it for two opposite sides, and if either one comes up, it intersects - if not, it doesn't.

What about if the line is fully contained within the rectangle? Does not intersect either side but begins and ends within the bounds of the rectangle. I want those included.

So maybe worst case scenario is 3 checks:
1. is the line's starting point contained within the bounds of the rectangle?
2. does the line intersect side 1?
3. does the line intersect side 2?

if any of the 3 conditions were true the line or part of the line is within the bounds and hence I need it. otherwise continue to the next

 

[PhatoseAlpha]

What about if the line is fully contained within the rectangle? Does not intersect either side but begins and ends within the bounds of the rectangle. I want those included.

So maybe worst case scenario is 3 checks:
1. is the line's starting point contained within the bounds of the rectangle?
2. does the line intersect side 1?
3. does the line intersect side 2?

if any of the 3 conditions were true the line or part of the line is within the bounds and hence I need it. otherwise continue to the next

Ah, I see. You're talking about line segments, not lines. Not the same thing, really.

This is problematic because the 2 sides rule does not apply to line segments, only lines.

 

[ivan2]

depends on how your input's being given there are different ways to do it fast.

if you are just getting 4 points of a rectangle randomly in a non-ordered fashion then you will want to check if one end of the line is within the 2 triangles these points will form. This way you don't have to know how the points are ordered therefore your time will be linear instead of the sorting nLogn.

if your points are already sorted, then u might be able to just checked 4 borders, saves you a little bit of time, but still linear.

couldn't think of a better way as of yet =/

 

[degibson]

How about solving for the intercept as others have suggested?

Ignoring the special case of a line segment x=k for y=[a,b], you should be able to express your line segment in the form y = m*x+x0 for x=[a,b].

Now, others have pointed out that a line that intersects a rectangle intersects one of its four sides. Each of those is an x=k for y=[a,b] or y=k for x=[a,b]. Set y = y or x = x as necessary and see if a solution exists. E.g., if a rectangle's upper edge is y = 4 on x=[2,3], and your line segment is y = 2x+0, then 2x=4 implies x=2 is an intercept. If this solution had been outside of the domain of the segment, there would be no intercept with that edge. Repeat for all edges.

The nice thing about this method is it works for a rectangle of any orientation, e.g., not necessarily xy aligned. It also works for arbitrary polygons in time linear in the number of edges.

The only case not handled above that I can think of is the case where the line segment is fully subsumed by the rectangle. In that case, computing the domain and range of the segment and ensuring that the domain is included by the domain of the rectangle and the range is included by the range of the rectangle is sufficient.

EDIT: I accidentally used 'b' twice in my examples. Switched the y-intercept from 'b' to x0

 

[Schmide]

Do a quick bounds check then regress to a triangle method.

1) Compute the x and y maximum and minimum for all points of the rectangle. (bounding rectangle)
2) Reject if both points of the line on the same side of any of the extremes.
3) Reject if no collision against extents of the bounding rectangle.
4) Include if there is an intersection on the line segments of the original rectangle
5) Subdivide the original rectangle into two triangles and include if either point is within a triangle.

You will find it much easier to do a point inclusion/exclusion test on a triangle rather than a rectangle.