Точки, полигоны и функторы

Долго колебался, стоит ли об этом писать, но после того, как знающий человек похвалил выбор алгоритма, решил все же рассказать. Интересная часть экстремистской задачи из прошедшего конкурса ПФП про вырезание московской области из России заключалась в том, чтобы определить для заданной точки, входит ли она в фигуру, заданную набором ломанных (набор невыпуклых многоугольников, в которых могут быть дырки из других многоугольников). Сперва меня терзали сомнения, можно ли использовать подходы из планиметрии в задаче, где координаты точек даны в терминах долготы и широты на совсем не плоской планете. Ведь если посмотреть на карту в районе полюса, становится хорошо заметно, что прямые в этой системе координат не такие уж прямые. Но потом забил на эти сомнения и стал решать планиметрически.

Основная идея решения в том, что из заданной точки пускается луч в северном направлении, и смотрится, сколько отрезков из полигонов он пересечет. Если нечетное количество, то точка внутри фигуры, иначе снаружи.


( Read more... )