Prof. Dr. Jay Martin Anderson
Professor Emeritus of Computer Science, Franklin & Marshall College
  • home
  • Development
    • Gallery
    • Stop and Pray
    • Stations at St. Thomas
    • PricePer
    • What's It Cost?
    • my own
    • at F&M
    • for clients
  • Small Gallery
  • LVC
  • Visualization
    • Algorithm Visualization >
      • Binary Space Partition
      • Convex Hull >
        • Extreme Point algorithm
        • Extreme Edge algorithm
        • "Gift Wrap" algorithm
        • Incremental algorithm
        • Incremental algorithm in three dimensions
        • "QuickHull" algorithm
      • Delaunay triangulation >
        • Incremental algorithm
        • from the Voronoi diagram
      • Line intersection >
        • a "brute force" algorithm
        • Sweepline algorithm
      • Motion planning
      • Point-in-Polygon >
        • Plumbline algorithm
        • Trapezoidal Map
        • Winding Number
      • Polygon triangulation >
        • "Art Gallery" Problem
        • Recursive algorithm
        • Make Monotone Polygons
        • Triangulate a Monotone Polygon
      • Voronoi diagram >
        • Fortune's algorithm
        • Intersection of Half-Planes
        • Quadtree algorithm
    • Data Visualization
  • OpenGL
    • OpenGL for Apple Software Developers
  • iBooks
  • about me
    • contact
Line Intersection:  a "sweep line" algorithm
Picture
The search for intersections of line segments can be made much faster if we only compare those line segments which are near to each other.  One device for doing this is to allow a horizontal line to sweep down the area; only those line segments which the "sweepline" intersects could possibly intersect each other.

The segments which the sweepline intersect forms a "working set" of line segments, amongst which we test for intersections.  If the working set is ordered from left to right, then only neighbors in the working set could intersect each other.  As the sweepline moves down, segments enter and leave the working set, and the working set is maintained in left-to-right order.  Every time the working set changes, we search again for possible intersections.

Click the Download button at the right to download a zipped file of all movies described on this page.

download
Proudly powered by Weebly