Personal tools
You are here: Home Projects In-house Projects Sweep of the plane
« October 2017 »
October
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

Sweep Line

[Intersections]

 

Abstract

Let C:={c1,c2, ...cn} be a set of curves for which we want to compute all intersections. We want to avoid testing pairs of curves that are far apart. To find the intersecting pairs we imagine sweeping a line l from left to right over the plane, starting from a position left to all curves. While we sweep the plane, we keep track of all curves intersecting it.

This type of algorithm is called a plane sweep algorithm and the line l is called the sweep line. The status of the sweep line is the set of curves intersecting it. The status changes while the sweep line moves to the right, but not continuously. The sweep line status is updated at specific points called the event points. These points are actually the endpoints of all curves and their intersection points. The initial set of event points are only the endpoints of the curves. More event points are added as intersection points are calculated.

The Sweep_line_2 class implements the plane sweep algorithm, and can be used to compute the intersection points of a given collection curves, the disjoint-interior subcurves induced by such a collection, and a few other retaled tasks.

In particular, we take advantage of the implemented sweep line algorithm to construct a Planar Map of intersecting curves efficiently. See CGAL::Pm_with_intersection for more details.

Links

Contact

Baruch Zukerman http://www.cs.tau.ac.il/~baruchzu baruchzu@post.tau.ac.il
Ron Wein http://www.cs.tau.ac.il/~wein wein@post.tau.ac.il
Tali Zvi http://www.startdl.com/ talizvi@post.tau.ac.il
Eti Ezra http://www.cs.tau.ac.il/~estere estere@post.tau.ac.il
Document Actions