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‬ )