# Sweep Line Algorithm

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

## Recommended Posts

I'm currently reading David Eberly's Game Physics, and I have a question concerning the sweep line algorithm presented at the end of the 5th chapter. The algorithm and its presentation seem straightforward enough, but I'm wondering why there's a need to maintain sorted lists of x and y intervals. If the condition for the intersection of two 2D rectangles is that both the x and y extents must overlap, then why isn't it sufficient to maintain a sorted list for one dimension, and then if an intersection is detected in one dimension, perform a check for intersection in the other dimension on the rectangles themselves.

I'd greatly appreciate any and all insights. Thanks.

##### Share on other sites
What you suggest works for the initial sort of the boxes. However, when you start moving the boxes and updating each frame, a sort only on x is not sufficient. Consider box0 with 0 <= x <= 2 and 0 <= y <= 2. Consider box1 with 1 <= x <= 3 and 1 <= y <= 3. In the initial sort on x, you find that x-intervals [0,2] and [1,3] overlap, so then you test for box-box overlap and find the boxes intersect. Suppose box1 is moved to 1 <= x <= 3 and 3 <= y <= 4; that is, the box is moved in the y-direction. The two boxes are no longer overlapping, so you need to remove the pair from the overlap set. If you only sort on x, you would never enter the insertion-sort swap code because the x-endpoints have not changed at all (the x-list is still correctly ordered).

##### Share on other sites
Dr. Eberly,

I had thought that a loop like that which initializes the algorithm, and which inserts intersecting rectangle indices in the overlap set (using an AABB instance method to check y overlap) could also be used to remove such intervals from the overlap set when they only intersected in x but not on y. I've stared a little harder at your example code (in WmlIntersectingRectangles.cpp), and it's clearer to me now that maintaining two lists is necessary to efficiently leverage spatial and temporal cohesion.

Now, I can write some sketches and try this out on my own. Thank you!

What you suggest works for the initial sort of the boxes. However, when you start moving the boxes and updating each frame, a sort only on x is not sufficient. Consider box0 with 0 <= x <= 2 and 0 <= y <= 2. Consider box1 with 1 <= x <= 3 and 1 <= y <= 3. In the initial sort on x, you find that x-intervals [0,2] and [1,3] overlap, so then you test for box-box overlap and find the boxes intersect. Suppose box1 is moved to 1 <= x <= 3 and 3 <= y <= 4; that is, the box is moved in the y-direction. The two boxes are no longer overlapping, so you need to remove the pair from the overlap set. If you only sort on x, you would never enter the insertion-sort swap code because the x-endpoints have not changed at all (the x-list is still correctly ordered).

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633767
• Total Posts
3013735
×