2018年6月8日 星期五

[Algorithm][Geometry] Sweep line algorithm

Problems:



Articles: https://leetcode.com/articles/rectangle-area-ii/
  • Moving the sweep line
  • Sweeping algorithms typically manage two sets of data:
    • The sweep-line status gives the relationships among the objects intersected by the sweep line.
    • The event-point schedule is a sequence of x-coordinates, ordered from left to right, that defines the halting positions of the sweep line. We call each such halting position an event point. Changes to the sweep-line status occur only at event points.
  • The sweep-line status is a total preorder T:
    • INSERT(T, s): insert segment s into T.
    • DELETE(T, s): delete segment s from T.
    • ABOVE(T, s): return the segment immediately above segment s in T.
    • BELOW(T, s): return the segment immediately below segment s in T.
Any-segments-intersect algorithm:
ANY-SEGMENTS-INTERSECT(S)
  1. T -> {}
  2. sort the endpoints of the segments in S from left to right, breaking ties by putting points with lower y-coordinates first 
  3. for each point p in the sorted list of endpoints
  4.     if p is the left endpoint of a segment s
  5.     then INSERT(T, s)
  6.     if (ABOVE(T, s) exists and intersects s) or (BELOW(T, s) exists and intersects s)
  7.         then return TRUE
  8.     if p is the right endpoint of a segment s
  9.         if both ABOVE(T, s) and BELOW(T, s) exist and ABOVE(T, s) intersects BELOW(T, s)
  10.             return TRUE
  11.         DELETE(T, s)
  12. return FALSE



Java:


沒有留言:

張貼留言