Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Chapter 18. Computational Geometry > Exercises - Pg. 467

Computational Geometry } } return result; } Note the following key points when looking at the code: result contains the Point objects that make up the closest pair. distance represents the currently identified distance between the closest pair. Of course, this is also the width of the drag net. dragpoint is the index of the leftmost Point within the drag net. sweepx is the x coordinate of the Point under the sweep line. dragx is the x coordinate representing the left edge of the drag net. This algorithm ignores the first two points in the sorted list, starting the sweep line at the third point, as the first two have already been assumed to make the closest pair for now. It then ignores points that have slipped behind the drag net by advancing the dragpoint variable. Finally, it checks the distance from the point under the sweep line to each of the points in the drag net, updating the resulting closest pair and the distance between them if a closer pair is found than that currently identified. That wraps up your implementation of the plane sweep algorithm. If you now run all the tests defined for this algorithm, you'll see that they all pass.