Plane Sweep Algorithm

Posted in Data structure by

Imagine you want to create your own video game or your own collision detector. The Plane Sweep Algorithm is the basic, you can adjust it to your needs.

sweepline In the picture above you can see the red sweepline. And you see a lot of lines. Our goal is to find out on what positions the lines are hitting each other.

The Setup From now on x means horizontal and y means vertical. We sort the lines, using starting and endpoint. sorted sweepline The picture above should explain it all. The sorted line-points (since we only care about the points here) are now in Q. Additionally there is S. S is sorted by the y-values, but empty at the beginning.

How it workz The first item from Q is removed. That is the start point for the Sweepline. The sweepline hits a left point. The line that is associated with the point is added to S. Now the loop begins: Take the next point from Q: If it is a left point, add the associated line to S and sort S. Afterwards detect if the line could hit a line that is already in S. If yes, calculate the point of intersection and insert it in Q(and sort Q). If it is a right point, remove the associated line from S. And test is the lines above and below have a point of intersection. If yes, calculate it and put it into Q (sort!). Last case: If it is an intersection point, exchange the two lines that got the intersection in S. Again check if there is a new intersection and do as above.

Published at , Updated at 2011-10-25

next: Introduction to Data Structures prev: Minimal Spanning Tree