Выбрать полигоны, в которые входит точка

love_bach
Дата: 29.03.2018 19:36:22
не используя гис и т.п. нужен алгоритм
Соколинский Борис
Дата: 29.03.2018 21:07:26
PtInRegion()
mayton
Дата: 30.03.2018 00:14:52
love_bach
не используя гис и т.п. нужен алгоритм

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

Для вогнутых есть алгоритм четности. Из точки выпускают луч коллинеарно
оси X. И если количество пересечений с гранями полигона четно или нечетно
то принимается решение. Сложность этого метода только в формальных
договоренностях о том как быть если луч проходит через точку и как задать
направление обхода.

Вогнутые полигоны можно представить логической суперпозицией двух выпуклых А и Б.
При этом решать булево выражение типа A и не-Б.

Еще есть метод дробления полигона на набор выпуклых трапеций. Для трапеции
поиск попадания - тривиален. Плюс тут можно делать всякие оптимизации
по скорости. (Метод 3). Для методов 1 и 3 возможны еще оптимизации
по методу BSP деревьев (если ищется скоростное решение).

Плюс для всех-всех методов имеет смысл строить выпуклый BoundingVolume
и делать тривиальные оптимизации.

Из экзотики еще есть метод основанный на интеграле по контуру для
кусочно-линейной функции но я его не помню. Кодил когда-то на Basic как
самый первый метод инженерной графики.
Akina
Дата: 30.03.2018 07:37:04
mayton
Еще есть метод дробления полигона на набор выпуклых трапеций.
Или триангуляция полигона - она, кстати, и попроще будет.
Соколинский Борис
Дата: 30.03.2018 20:31:11
mayton
Если полигоны выпуклые - то легко. Для всех полигонов задается
направление обхода (например по часовой стрелке). Далее решается
уравнение типа "положение точки относительно прямой" для каждого
отрезка из образующих полигон. (Метод 1)

Для выпуклых есть более простой алгоритм Грэхема: обходим точки границы по/против часовой и считаем знак векторного произведения с базой в точке. Если она внутри, знак будет постоянным.
А для невыпуклых с возможными пакостями типа самопересечения/дырок внутри нифига аналитические методы работать не будут.
Проще тупо перебрать все составные сегменты или прямоугольники, как винда делает.
mayton
Дата: 30.03.2018 20:46:30
Я надеюсь что у автора нет дырявых.
mayton
Дата: 31.03.2018 10:23:23
Шикин и Боресков - Комп. Графика - 8.5. Проверка принадлежности точки многоугольнику.

Описана реализация на С++.
love_bach
Дата: 31.03.2018 11:11:04
спасибо.
но вопрос был не "принадлежность точки полигону", а "выбрать все полигоны, в которые входит точка".

понятно, что итерация по всем полигонам и проверка "входит" решает задачу. нужно что-то более эффективное

mayton ,
дырявых нет
mayton
Дата: 31.03.2018 11:45:15
love_bach, на алгоритм сильно влияет следующее.

Будут-ли полигоны часто обновляться? Если нет - то можно индексировать пространство
через BSP/Quad/R-Tree. И решать задачу по индексу. При этом индексировать мы будем
не сами полигоны а их пересечения. Тоесть если полигоны A и Б частично перекрываются
то в индекс попадает узлы:
1) Только A
2) А и Б
3) Только Б

Для большего числа полигонов будет соотв более сложные комбинации (worst-case - для N
полигонов нам придется проиндексировать 2 в степени N узлов индеса). Обновление подобных
структур данных затруднено но зато поиск - поиск логарифмичен.

Если пространство дискретное (пиксели) то возможно нам подойдет даже связка координат - и
ссылки на объекты представляющие полигон.

(1,1) -> A
(1,2) -> A,B

Вобщем как видите - нету сферического алгоритма. Нужно знать постановку. Причем чем детальнее
тем лучше.
L1G
Дата: 31.03.2018 14:39:44
простой способ ускорить перебор:
для всех полигонов предрассчитывать габариты (минимумы и максимумы координат всех точек одного полигона)
тогда при полном переборе можно будет без полной проверки отбрасывать те, минимумы которых больше координат точки или максимумы меньше