Plane Sweep Algorithm for finding Line Segment Intersections
This is an introduction to the plane sweep technique by the example of the problem of finding all intersections of a set of line segments.
Chapters:
00:00:00 introduction
00:06:03 observations
00:11:38 concepts
00:14:30 status & events
00:17:27 degenerate cases & quiz
00:20:08 data structures (for status)
00:23:37 finding events
00:25:15 data structure for events
00:28:19 plane sweep algorithm
00:30:22 event handling
00:33:12 running time
00:37:58 linear space
00:40:42 handling degenerate cases
00:42:46 conclusion
Correction: 00:19:35 Here n is the number of vertices of both polygons. (thanks to
@karatsurba4791 )