[Алгоритмы] Проверка на попадание точки в заданный участок

[Akopalipsis]

Предполагаю, что мой вопрос может и по другому называться, но не представляю как.
Нужно проверить совпадает ли точка с выбранным участком. То есть, участок, это не ДО, а математически изменяемая..ммм.. произвольная фигура описанная только математически. Скажите как это правильно называется или если кто-то уже с этим сталкивался, подскажите самый производительный алгоритм.

[bav]

Я бы начал с Википедии: задача о принадлежности точки многоугольнику.

[Akopalipsis]

bav, Спасибо! Сейчас начну
Прочёл, мало, что ещё есть?)

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

[Bletraut]

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

Писал когда-то подобные вещи для своего 3д велосипеда.

[alexcon314]

http://algolist.manual.ru/
http://habrahabr.ru/post/125356/
Akopalipsis, гугл уже не в моде?

[vorodis2]

Качаете либу Nape там есть метод создания физического многоугольника по опорным точкам и есть метод проверки принадлежности точки к эному.
Конечно это если как из пушки по птицам стрелять, но я бы сделал именно так.

[Akopalipsis]

Начать хочется с - Все Спасибо!

Куда проще накидать точек в массив, а затем уже проводить невидимый контур

Можно немного подробнее.

Akopalipsis, гугл уже не в моде?

Гугл-то пака не может ответить на вопрос о самом производительном алгоритме, да и есть возможность,
о которой Bletraut

Конечно это если как из пушки по птицам стрелять, но я бы сделал именно так.

Мне нужно с целю самообразования и Nape не подходит. Хочется найти самый быстрый алгоритм проверки.

[alexcon314]

Гугл-то пака не может ответить на вопрос о самом производительном алгоритме

Печалька. .

Добавлено через 1 час 32 минуты
[ответ на удаленный пост пользователя Akopalipsis]
Нет, и в мыслях не было. Я провоцирую вас "найти самый быстрый алгоритм проверки", выполнив два нехитрых действия:
- включить мозг;
- постучать по клаве;
А заодно поделиться результатами на радость всем.
Это все вместо того, чтобы сидеть, сложа руки и ждать, что кто-то умный придет и все сразу расскажет и покажет. А вам останется только скопипастить решение и рассыпаться в благодарностях.

[Akopalipsis]

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

Добавлено через 2 минуты

Это все вместо того, чтобы сидеть, сложа руки и ждать

Могу только сказать, что Вы очень ошибаетесь.

[Dukobpa3]

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

Про векторы не сильно понял. Чем помогут?
Возможно при условии выпуклого многоугольника и да, но если это ломаная - уже не могу представить.