Простой вопрос

[mancunian]

Чёта я туплю...

Пусть (x1, y1),..., (xn, yn) - вершины выпуклого многоугольника. Как проще всего проверить, будет ли точка (a,b) внутри него?

В интернетах какая-то хрень, коды какие-то, понимаешь. А мне простой алгоритм нужен.

UPDATE. Всем большое спасибо, кто откликнулся. Всё теперь работает.

Comments

[sea_hog]

А правильно ли я понял, что вершины многоугольника перечислены в естественном порядке? Если да, то можно так: найти все векторы из (a,b) в вершины и посчитать n углов между ними (все углы от 0 до 180 градусов). Потом сложить. Если получилось 360 градусов -- значит внутри; если меньше -- значит снаружи.

[rsokolov]

Векторные произведения (a - x_i ,b - y_i) X (x_n+1-x_i,y_i+1,y_i) должны быть либо все положительные, либо все отрицательные.

[bljakhin_mukher]

sea_hog меня опередил. Это достаточно простое решение, по-моему. Естественный порядок в случае чего можно получить взяв точку L с минимальной абсциссой (если их несколько, то выбрать с минимальной ординатой) и точку R с максимальной. Взять L в качестве начальной точки, потом перечислить все точки лежащие выше отрезка LR в порядке возрастания абсцисс, потом R, потом остальные точки в порядке убывания абсцисс,

[orleanz]

А какой алгоритм вам больше всего понравился?

[mancunian]

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

[orleanz]

а еще есть такой совсем простой способ - сначала пишем подпрограмму, которая по координатам треугольника вычисляет его площадь (формула Герона). Потом, используя ее, вычисляем сумму площадей треугольников, полученных при проведениии из точки (А,Б) линий к каждому из отрезков. Если точка находится внутри многогранника, то сумма площадей этих треугольников должна быть равна площади самого многоугольника (ее можно найти аналогичным образом), как бы сумма его лепестков.

[eisenberg]

Помилуйте, это какой-то ад вычислительной сложности. Зачем Герона. Площадь треугольника считается как векторное произведение сторон (ещё модуль и пополам).