Находится ли точка в произвольно нарисованной фигуре?

Question

[Виталий Сирык]

Необходимо узнать, находится ли точка в обведенном участке. Есть массив точек линии.

Answer 1

[Immortal_pony]

В наиболее простом случае можно построить окружность и искать далее вхождение точки в нее:
(x - x0)^2 + (y - y0)^2 <= R^2
где x и y - координаты вашей точки, x0 и y0 - координаты центра окружности, R - радиус окружности, ^2 - возведение в квадрат. Если условие выполняется, то точка находится внутри (или на окружности, в случае равенства левой и правой частей). Если не выполняется, то точка вне окружности.

Если же все же необхоим произвольный контур, то в этой статье описан алгоритм определения попадания точки в произвольный контур. Также, можно прочиатать о вопросе на Википедии.

Comments

[Константин Нагибович]

В условии ни слова про радиус и координаты центра.

[Виталий Сирык]

Возможно я неправильно поставил вопрос. Нужно узнать, находится ли точка в произвольной нарисованной фигуре.

[Immortal_pony]

Константин Нагибович, их легко получить, вписав/описав окружность в построенный из массива точенк многоугольник.
Можно, конечно, искать попадание точки в контур, но это куда более нетривиальная задача - habrahabr.ru/post/125356

[Immortal_pony]

Виталий Сирык, вот тут описан алгоритм определения попадания точки в произвольный контур - habrahabr.ru/post/125356. Также, можно прочиатать о вопросе на Википедии - https://ru.wikipedia.org/wiki/Задача_о_принадлежно...

[Виталий Сирык]

Immortal_pony, спасибо!

Answer 2

[tsarevfs]

Если есть произвольная замкнутая ломаная и точка: проводим из точки луч в верх, считаем количество пересечений с отрезками составляющими ломаную. Если нечетное -- внутри, иначе -- снаружи. Отрезки стоит брать полуоткрытые, чтобы избежать проблем при прохождении через узлы ломаной.

Comments

[Adamos]

А какие проблемы с узлами ломаной? Точка узла принадлежит обоим отрезкам, четное пересечение.

[tsarevfs]

Adamos: это нужно считать как одно пересечение (фактически оно и есть одно). Иначе ответ будет неправильный.

[Adamos]

tsarevfs: понял, но мы оба неправы. Зависит от того, по одну сторону от луча лежат сходящиеся в этой вершине отрезки (чет) или по разные (нечет).

[tsarevfs]

Adamos: Да, про касание вершины я забыл.

Answer 3

[DDDsa]

Находится.

Comments

[Александр Ручкин]

ааа)))