Javascript-форум - КАК ПРОВЕРИТЬ ПРИНАДЛЕЖНОСТЬ ТОЧКИ ПОЛИГОНУ

Javascript-форум (https://javascript.ru/forum/)

- Общие вопросы Javascript (https://javascript.ru/forum/misc/)

- - КАК ПРОВЕРИТЬ ПРИНАДЛЕЖНОСТЬ ТОЧКИ ПОЛИГОНУ (https://javascript.ru/forum/misc/23935-kak-proverit-prinadlezhnost-tochki-poligonu.html)

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

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

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

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

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

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

Цитата:

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

Есть ли в вашем арсенале способ попроще?

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

Цитата:

Сообщение от ksa (Сообщение 142229)

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

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

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

Цитата:

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

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

Вот абстракный вариант.

Цитата:

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

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

http://www.gamedev.ru/articles/?id=30123

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