Personal tools
You are here: Home Projects Internal Projects Sweep of the plane
« April 2017 »
April
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
30
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