Определить, что точка внутри фигуры или нет?

Question

[Max Cohen]

Добрый день, по какой формуле или алгоритме можно определить, что точка внутри этой фигуры?

Answer 1

[Max Cohen]

Вот решение и формула, код.

Задача о принадлежности точки многоугольнику

Answer 2

[evgeniy_lm]

Сумма углов между тестовой точкой и ближайшими точками фигуры должна быть 360 градусов. Берем по очереди все пары точек фигуры, определяем углы, суммируем и удивляемся

Comments

[Rsa97]

Для контура произвольной формы не сработает.

[evgeniy_lm]

Rsa97, это сработает для любого контура выпуклого многоугольника (как на картинке).
Другой вариант определить что все точки многоугольника находятся выше, ниже, правее или левее искомой точки. Значит искомая точка находится вне фигуры. Опять же это справедливо только для выпуклых многоугольников.

Если многоугольник не выпуклый его нужно сделать выпуклым (не помню как) выделив один большой многоугольник и несколько маленьких вычитаемых. Тогда задача решается в два этапа: 1. определяем лежит ли точка внутри большого многоугольника. Если да то 2. определяем лижит ли точка внутри вычитаемых многоугольников.

[Rsa97]

evgeniy_lm, Опять же, упираемся в точность вычислений. Если получили 359.9999991231 градус, то что это значит?

[evgeniy_lm]

Rsa97, точность 2,5e-7% Это уже задрочизм.
Если точка не лежит внутри то сумма углов будет существенно меньше
Если точек очень много >20 тогда можно определить по расположению точек, я уже писал

[stratosmi]

Rsa97,

Опять же, упираемся в точность вычислений. Если получили 359.9999991231 градус, то что это значит?

Пренебрежимо близко к границе?

Answer 3

[Rsa97]

Проведите из точки луч в любую сторону. Если он пересекает контур нечётное число раз, то точка в контуре, если чётное (или ноль), то вне контура.
Если луч попадает в вершину, то надо определить, как расположены примыкающие к этой вершине отрезки контура относительно луча. Если отрезки находятся с разных сторон от луча, то засчитывается одно пересечение, если с одной - то ни одного.
Если один из отрезков контура совпадает с лучом, то надо смотреть как располагаются относительно луча соседние отрезки.

Ещё можно взять интеграл по контуру относительно точки, но там сложно распознать краевые случаи из-за погрешности вычислений.

Comments

[evgeniy_lm]

Вы путаете графический метод с аналитическим.
аналитически его можно применять только если многоугольник определен функцией. для многоугольника заданного точками это крайне сложно.

[Rsa97]

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

[evgeniy_lm]

Вы графическое (картинку) представление фигуры путаете с аналитическим (набор точек, функция). Как вы будите интегрировать массив с координатами точек?

[Rsa97]

evgeniy_lm, В графическом представлении интеграл - это площадь. Вспомните, как даётся определение интеграла через трапеции. Теперь возьмите, например, трапецию, нижняя сторона которой - ось X, боковые стороны x = 0 и x = 10, верхняя - y = x/2+10. Посчитайте площадь трапеции, сначала по стандартной формуле, затем через интеграл (x/2+10)dx от 0 до 10. Удивитесь, что результат получился тот же самый.
Когда контур задан ломаной линией (то есть координатами концов отрезков), то обычный интеграл по нему можно представить в виде суммы площадей трапеций, интеграл относительно точки - в виде суммы площадей треугольников.
Конечно, если исходные данные представлены исключительно в виде картинки цвет(x, y), то интегрирование не поможет, но там и ваш метод суммирования углов даст дикую погрешность.

Answer 4

[Данил]

Если известны координаты:

Х_фигуры_min < Х_точки < Х_фигуры_max
Y_фигуры_min < Y_точки < Y_фигуры_max

Answer 5

[zhopop]

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

Answer 6

[Black0ut]

Rsa97 А подскажи пожалуйста, почему именно так: "Если отрезки находятся с разных сторон от луча, то засчитывается одно пересечение, если с одной - то ни одного"? Есть какое то правило на этот счет? Формула? Всю голову сломал, но так и не додумался почему так это работает.

Comments

[Rsa97]

Потому что если отрезки находятся по одну сторону от луча, то он не пересекает контур, а просто касается его.