Попадание точки в многоугольник. Количество заныриваний не равно количеству выныриваний.
Есть точка O, есть многоугольник A[n] на плоскости. Надо выяснить, попадает ли точка в многоугольник.
Основа алгоритма описывается очень просто: давайте возмём бесконечный горизонтальный луч из точки направо. Если луч пересекает границу четное число раз (в том числе 0 раз) , то точка вне многоугольника. Если нечетное число раз - то внутри.

Затем программист пытается обработать хитрые случаи: луч проходит через вершину многоугольника, сторона многоугольника совпадает с лучом. В коде возникают какие-то if, какие-то EPSILON..., молитвы о том, что редкие случаи когда две точки на расстоянии EPSILON но луч между ними - не существуют, насильно изгонясь из сознания ( Collapse )
Смотри ещё: • Угол между двумя векторами
Смотри ещё: • Пересечение двух отрезков
Основа алгоритма описывается очень просто: давайте возмём бесконечный горизонтальный луч из точки направо. Если луч пересекает границу четное число раз (в том числе 0 раз) , то точка вне многоугольника. Если нечетное число раз - то внутри.
Затем программист пытается обработать хитрые случаи: луч проходит через вершину многоугольника, сторона многоугольника совпадает с лучом. В коде возникают какие-то if, какие-то EPSILON..., молитвы о том, что редкие случаи когда две точки на расстоянии EPSILON но луч между ними - не существуют, насильно изгонясь из сознания ( Collapse )
Смотри ещё: • Угол между двумя векторами
Смотри ещё: • Пересечение двух отрезков