Как проверить, принадлежит ли точка четырехугольнику?
К примеру у меня есть следующие точки, образующие 4-ех угольник.
x1 = 81.0582
y1 = 348.106
x2 = 127.111
y2 = 367.577
x3 = 120
y3 = 256
x4 = 166.053
y4 = 275.471
По условию не дано, какая из этих точек верхняя вершина или нижняя. Это несложно вычислить и я это сделал. Но дело в том, что четырехугольник лежит под углом и это усложняет задачу. Подскажите, какой алгоритм использовать, чтобы узнать, принадлежит ли точка (любая) четырехугольнику или нет?
Ответы (1 шт):
Вам нужно провести из проверяемой точки любой луч и сосчитать сколько раз он пересекается со сторонами четырехугольника. Точка находится внутри если это число нечётное.
Для определённости можно выбрать горизонтальный луч направленный вправо. Вам понадобится одна примитивная операция - проверка пересечения горизонтального луча и отрезка. "Примитивная" - это термин, который не означает что эта операция простая. :)
Тонкий момент когда луч проходит через вершину четырехугольника, надо будет тщательно обработать этот случай.
Подробности тут: