Столкновение "точка - многоугольник"

[IgorOK]

Знает ли кто нибудь хорошие статьи на определение нахождения точки в многоугольнике?

[SBJoker]

в двух словах метод такой:
если луч проведенный через точку пересекает нечетное число сторон многоугольника - точка внутри этого многоугольника, иначе - снаружи.

[IgorOK]

А есть ли какие нибудь особенности трассировки луча? Т.е. его можно проводить произвольно?

[SBJoker]

Совершенно произвольно проводить, но с точки упрощения расчётов его можно провести параллельно одной из координатных осей

[IgorOK]

Сообщение от SBJoker

Совершенно произвольно проводить, но с точки упрощения расчётов его можно провести параллельно одной из координатных осей

Большое спасибо за помощь!

[MiXaeL]

Сейчас порисовал на бумажке, и мне кажется, есть хак.
Сумма расстояний от точки до вершин многоугольника внутри него всегда меньше периметра, а снаружи больше. Если у кому-то будет не лень проверить, было бы интересно узнать, так это или нет.
Для треугольника - тривиально.

Бред сказал, да =\. Внутри - всегда меньше, обратно - неверно. Легко проверить точкой на самой границе.

[Randomize]

http://geomalgorithms.com/a03-_inclusion.html