Line Intersection: a "brute force" algorithm
|
The search for intersections of line segments can be carried out by comparing each line segment to each other line segment (O(N2)). Although some cases can be trivially rejected (both endpoints of one segment lie to the right of both endpoints of the other segment), many intersections must be directly computed, and then tested to be sure the intersection really does lie on both segments.
Click the Download button at the right to download a zipped file of all movies described on this page. |