Точка в алгоритме полигонов в соревнованиях по программированию

Question

Какой лучший алгоритм для решения точки в полигоне в соревнованиях по программированию?

Answer 1

Снимите луч (в произвольном направлении) из точки и проверьте, сколько раз он пересек границы многоугольника, если он равен даже тогда, когда точка находится за пределами многоугольника, в противном случае точка находится внутри многоугольника.

Если вам нужно сделать это для большого количества точек запроса, вы можете триангулировать многоугольник (фактически триангулировать как внутри, так и в области между многоугольником, в котором находится выпуклый элемент), чтобы вы могли выполнять лучевую съемку в O(log n)

Answer 2

Если у вас есть выпуклый многоугольник, вы можете использовать это:

http://e-maxx.ru/algo/pt_in_polygon