КАК ПРОВЕРИТЬ ПРИНАДЛЕЖНОСТЬ ТОЧКИ ПОЛИГОНУ

[Livanderiaamarum]

Есть 2D пространство с обычной системой координат. В нем есть произвольный многоугольник с рандомным числом вершин расположение которых тоже рандомно , но известно.
Есть точка, положение которой тоже рандомно , но координаты тоже известны.

КАК определить принадлежит она полигону или нет?

Гуглил, нашел кучу способов, фракталы графики и.т.п. Есть ли в вашем арсенале способ попроще?:)

http://cs304309.vk.com/u11538055/-3/x_b70bd6a5.jpg

____________________________________________
А ТЕПЕРЬ ПРАВИЛЬНЫЙ ОТВЕТ!!!!

НУЖНО ПРОВЕСТИ ИЗ ЭТОЙ ТОЧКИ ЛУЧ В ЛЮБОМ НАПРАВЛЕНИИ И ПОСЧИТАТЬ СКОЛЬКО ГРАНЕЙ ПЕРЕСЕЧЕТ ЭТОТ ЛУЧ, ЕСЛИ ЧЕТНОЕ ЧИСЛО, ЗНАЧИТ ТОЧКА ВНЕ ПОЛИГОНА, ЕСЛИ НЕЧЕТНОЕ, ЗНАЧИТ ТОЧКА ВНУТРИ ПОЛИГОНА. ЕСЛИ ПОПАДАЕТ НА ВЕРШИНУ, ТО СДЕЛАТЬ ОПЕРАЦИЮ ЗВАНОГО СМЕНИВ НАПРАВЛЕНИЕ ВЕКТОРА)

[ksa]

Есть ли в вашем арсенале способ попроще?
Типа самый простой - закрашивать полигон цветом, а потом проверять цвет точки - если равна цвету полигона, то принадлежит, если нет - не принадлежит
(с)

[Livanderiaamarum]

Типа самый простой - закрашивать полигон цветом, а потом проверять цвет точки - если равна цвету полигона, то принадлежит, если нет - не принадлежит
(с)

ух ты)) не подумал) это получится типа как ускоритель видеокартой? если мы будем canvas использовать)? ыы

нет ну а если нам нужно все абстрактно сделать)?
просто интересно))

[ksa]

Я давно с графикой не работал... Т.ч. в этом не советчик. Просто этот "способ" запомнил, вот собственно и всё.... :)

[ksa]

а если нам нужно все абстрактно сделать)?
Вот абстракный вариант.

Проверка принадлежности точки полигону


Алгоритм несложный. Просматриваем все вершины. Теперь получим вектор от точки пересечения до текущей вершины: вычитаем вектор точки пересечения из вектора текущей вершины. Аналогично получим вектор от точки пересечения до следующей вершины. Затем находим угол между этими векторами и добавляем его к текущему углу Angle. Нетрудно доказать, что после просмотра всех вершин значение Angle будет равно 2*pi (360 градусов) только в том случае, если точка находится внутри полигона. В силу неточностей вычислений с плавающей точкой может быть, например, что угол будет равен (2*pi – 0.00001), поэтому проверяем, если угол больше либо равен 2*pi*const (константа близкая к единице), возвращаем true, точка находится внутри полигона, иначе возвращаем false.
http://www.gamedev.ru/articles/?id=30123

[irezvov]

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