COMP317 — Design and analysis of algorithms
Line segment intersection (Manhattan topology)
In a manhattan topology, line segments run either horizontally or
vertically. Each segment is defined by a pair of end-points, each
specified by a pair of coordinates in the x and y dimension.
Brute force search
Intersection of line segments can be done via a brute force method by
considering each unique pair of lines and determining if they
intersect. This approach is, of course, in O(n2).
A more efficient scheme is to sweep upwards through the lines to
detect intersection between lines as they are subject to scanning.
The horizontal sweep algorithm is in O(n log n).
- Sort all end-points by inserting one at a time into a y-tree
(i.e. a binary search tree ordered on the y-coordinate of each point).
- Through an in-order traversal of the y-tree ...
- remove the next point, p, from the y-tree
- if p is the lower end-point of a vertical line, insert it into
the x-tree (i.e. a binary search tree ordered on the x-coordinate
of each point)
- else if p is the upper point of a vertical line, remove the lower
point from the x-tree
- else if p is the end-point of a horizontal line, remove its other
end-point from the y-tree, then do a range search of the x-tree and
output any vertical lines whose x-coordinate falls within the range
given by the two x-coordinates of the horizontal line.
Adding end-points to the y-tree (Step 1) is loglinear. Removing them
(Step 2.1) is linear. Adding and removing vertical segment
end-points to the x-tree (Step 2.2 and 2.3) is loglinear. Range
searching(Step 2.4) is logarithmic. Note that each point removed from
the y-tree is either added to the x-tree or it causes a range search,
but not both.