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

[mancunian]

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

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

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

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

Comments

[the_cleanser]

1. Берешь произвольную точку (a1,b1), находящуюся заведомо вне многоугольника.
2. Соединяешь отрезком с (a,b)
3. Проверяешь, проходит ли отрезок через какую-либо вершину многоугольника. Если проходит - возвращаешься к п.1, где выбираешь другую точку.
4. Считаешь количество пересечений отрезка (a,b)-(a1,b1) со сторонами многоугольника.
Если количество пересечений четное - точка (a,b) вне многоугольника. Если нечетное - внутри.
Работает с любыми многоугольниками, не только с выпуклыми.

[roman_kr]

yгу. И для простой реализации просто прямую надо провести параллельно оси х.

[a_p]

чтобы проверить, лежит ли точка А внутри многоугольника, нужно выбрать какую-нибудь (например, среднее всех вершин) точку В внутри него и проверить, пересекает ли отрезок АВ какую-нибудь сторону многугольника.

[mancunian]

А как проверить, что два отрезка пересекаются?

[a_p]

Лежит ли точка пересечения соответствующих прямых внутри отрезков.

[roman_kr]

простой ответ:
рабочий алгоритм такой :
проводим из точки луч, если внутри - число пересечений с границей нечетное, если снаружи четное.
простая Реализация - луч проводим параллельно оси х от (х_min до мах(х) т.е. надо проверить для списка ребер пересечения простым неравенеством y_n

[the_cleanser]

Вряд ли. Недостаточно учитывать только проекции на X или Y.
Ноль должен получаться и для суммы проекций на X, и на Y.

Возьмите единичный квадрат с центром в (0,0) и любую точку вне квадрата, лежащую на оси Oy. Сумма проекций на Х даст 0.

[newlondoner]

Я бы взял векторы, представляющие каждую сторону Xn = (xn - xn-1, yn - yn-1), и скалярно умножил на векторы ортогональные (a - xn, b - yn).
Nn = (yn - b, a - xn)
То есть, посчитал бы N скалярных произведений pn = (Xn, Nn). Если у них у всех один знак, значит точка внутри.

[tengokawana]

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