по обе стороны от
по обе стороны от точки A на прямой окажется четное число точек пересечения со сторонами, то точка лежит вне многоугольника, а если нечетное - то внутри.
Таким образом, алгоритм состоит в следующем: выбираем прямую, находим, с какими сторонами она пересекается и в каких точках, и считаем количество таких точек с одной стороны от A.
В качестве прямой удобно взять, например, горизонтальную прямую (Y = A.y).
Для нее проще, чем для произвольной прямой, проверять наличие точки пересечения с отрезком, считать ее координату (одну!) и проверять, с какой стороны от A эта точка лежит.
При реализации этого алгоритма стоит иметь в виду 2 небольшие детали:
*
прямая может проходить через вершину многоугольника, причем 2 разными способами - пересекая границу многоугольника или касаясь границы многоугольника;
*
сторона прямоугольника может быть горизонтальной и лежать на прямой.
Время O(N) является неплохим, и вряд ли можно желать лучшего, если речь идет о вопросе, решаемом
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
