Алгоритмы и структуры данных 12. Принадл. точки многоугольнику. Пересеч. полуплоск-тей. Bounding box

Алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Дата лекции: 17.11.2022 Лектор: Степанов Илья Даниилович Монтажер: Голицын Сергей Оператор: Жулябина Ира 00:00:00 — начало; проверка принадлежности точки многоугольнику; способ 0 (только для выпуклых многоугольников) 00:03:29 — способ 1 — для невыпуклых многоугольников (просуммировать углы, под которыми из точки видны стороны) 00:08:23 — способ 2 — для целочисленных координат 00:12:20 — что делать, если луч проходит через вершину 00:16:33 — способ 3 — разбираемся с вершинами в способе 2 00:30:44 — пересечение полуплоскостей 00:38:24 — введение bounding box (предыстория — на 00:35:24) 00:42:10 — алгоритм пересечения полуплоскостей за O(n^2) 00:52:07 — алгоритм за О(n log(n)) 01:06:09 — второй алгоритм за O(n log(n)) 01:15:55 — тонкости алгоритма