Подскажите, как возможно реализовать такую задачу.

Есть рандомное количество точек с координатами, которые образуют собой фигуру.
Есть определенная точка с координатами.

Как определить находится ли заданная точка в фигуре?
Есть какой-нибудь отлаженный алгоритм? Может готовое что-нибудь встречали?    

Если картинка это квадрат который представляет собой закрытый набор пикселей то:
получаем координаты всех пикселей
смотрим если по x оси есть другие пиксели кроме нашей точки
и смотрим по y

если по x и y нифига нету то однозначно нашу точку никакая закрытая фигура не окружает

Главное смотреть как бы что есть точка снизу и сверху и справа и слева


У меня воображения не хватает представить закрытую фигуру которая не будет "резаться" таким методом

Если фигура замкнутая, обязательно и по x и по Y справа слева снизу сверху наш выстрел попадет

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

Автор так и не сказал если фигура таки закрытая или нет... потому что если она не закрытая я не представляю как такое возможно рповерить и что есть окружает или нет

Skevalt, спасибо, почитаю.

Muerto, фигура закрытая, но может быть сложная. К примеру может быть и 150, и 200 точек. 
Задача у меня изначально такая: курьер на гугл карте рисует фигуру, клиент ставит точку. Курьер может ошибиться и нарисовать к примеру вот такое:, но мне все равно нужно это определить - находится ли точка клиента в зоне курьера. 

Ну тогда мой метод как мне кажется будет самым простым...

Я такое никогда не делал и вообще я мало работаю с картинками, но все же php GD :

http://php.net/manual/en/book.image.php

Получаем картинку

Далее смотрим на размер картинки

Насколько я понимаю, верхний левый угол это (0,0) и когда мы идем вниз по x или y , мы увеличиваем параметры...
значит на самом деле

Точка у нас с координатами которые нам известны?
Тогда искать её не нужно...


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

Muerto, забавная мысль - использовать gd для решения математических задач   только, imho, у нас есть список координат вершин и координата нужной точки. А картинки-то и нет. Зато ее можно нарисовать с помощью imagefilledpolygon и посмотреть цвет. Или можно нарисовать все грани фигуры, сделать imagefill из требуемой точки и посмотреть на цвет точки, гарантированно не принадлежащий фигуре. Если она покрасилась - исходная точка вне фигуры. Второй способ убережет нас от явной ошибки курьера с "перекрученными" вершинами.

В принципе - любой замкнутый многоугольник можно полностью порезать на непересекающиеся выпуклые многоугольники. Так что останется только перебрать все такие выпуклые "нарезки".
Вероятно есть какая-то теорема по этому поводу, возможно кто-нибудь ее укажет и заодно укажет эффективный способ разбиения. 

ksnk, Респэкт, к сожалению не достаточно имею опыт работы с GD что бы додуматься до твоего решения...

В общем гениально... красим фигуру, и затем смотрим если наша точка сменила цвет =-)

Вот только вопросик просыпается...
конечно мы исходим из того что фигура у нас замкнутая, но так для общего равзития, если я fill сделаю на не замкнутую, что случиться?
выкинет ошибку, или покрасит весь прямоугольник картинки?