Геометрическая задача на пересечение полигонов

Попадаем на земляной полигон, смотрим на север, юг, восток и запад. Если и там кругом земля, значит, воды нет. Дальше 2 варианта – или на этом успокаиваемся, или увеличиваем радиус поиска.

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

И это… замляной полигон и так состоит из земли. Мне нужно определить не смотрит ли мой прямоугольник-окно-зона на чисто земляной участок карты.

Может для поиска воды/земли построить такую штуку?

https://ru.wikipedia.org/wiki/R-дерево_(структура_данных)

Монте-Карло?

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

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

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

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

P. S. А если прямоугольник весь на земле, но посредине есть озеро: это считается доступ к воде? Мой способ позволяет определить только доступ к океанам, но не к озёрам.

P. P. S. А реки учитываются?

Чтобы метод луча работал в среднем более универсально нужно будет

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

2. побить каждый прямоугольник сеткой с шагом меньше самого маленького ребра

3. Решить кейсы попадания точек на ребра многоугольников

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

Озёра и реки, думаю, буду игнорировать. Чёрт с ними. Они не важны.

В общем виде мне нужен метод для рассчёта ПЛОЩАДИ пересечения двух произвольных полигонов.

Площадь пересечения «окна» со всеми земляными полигонами = 0 – чисто вода.

Площадь пересечения «окна» со всеми земляными полигонами +- епсилон = площадь «окна» – чисто земля.

Промежуточные значения – и вода и земля.

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

А вдруг там участок с выходом на воду, но в этом месте база подводных ракетных крейсеров? Тогда эта вода тоже недоступна.

Докинуть точек на ребра полигонов

Это про улучшение метода луча? Ок, возможно. Я исходил из предположения что это уже есть и работает. Я решал ровно ту задачу, которую ТС поставил в описании.

Пусть каждый полигон хранит метаинформацию: граничит он с водой или нет.

Если вода и земля отличаются, то решение очевидно. Если не отличаются, то какая тогда разница.

Ну так эту информацию нужно где-то брать. Вот я и думаю как её вытащить из того что есть.

Пусть каждый полигон земли определен набором прямых вида ax + by = c. В матрицу A загоняешь нормали всех прямых. В вектор B загоняешь все точки, через которые проходят соответствующие прямые пологина.

Теперь Пусть P - это интересующий нас полигон. Пусть он состоит из точек p_i.

Для каждой точки p_i проверяем все ли элементы вектора A*p_i - B > 0. Если да, значит точка лежит строго внутри данного полигона земли.

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

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

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

Прямая, содержащая отрезок полигона - решающее правило . Если >0 то с одной стороны прямой если <0 то с другой и соответственно, если =0 то на прямой.

Полигон - система неравенств таких прямых.

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

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

Поэтому я и предлагаю Монте-Карло, всё равно точки накидывать.

Хранить при создании не вариант?

Не вариант. Там этих зон больше сотни. Их и так создавать крыша немного съехала, а если ещё и добавлять какие-то метаданные, то приши пропало. И при этом я на 100% уверен, что расположение и габариты зон будут меняться ещё раз 10.

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

Вот только по хорошему такое должно быть одним полигоном.

Ну и да, ты бы слои добавил для группировки полигонов по признакам.

ты бы слои добавил для группировки полигонов

Зачем? Куда? Какие слои? Чтобы группировать полигоны нужно их проанализировать. Эту задачу я сейчас и решаю :)

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

Нужно точно знать, чем отличаются вода и земля или в какой точно точке достоверно земля (или достоверно вода).

Не-не-не, метаданные не у зон, а у полигонов. Зона должна только определить какие полигоны в неё входят и проверить их свойства.

Полигоны это государства и острова. Они – земля и только земля по определению.

Зоны – прямоугольники-окна сквозь которые я смотрю на карту. И мне нужно определить вижу ли я только землю, только воду или всего понемногу.

Обычные такие слои, земля, океаны, моря, реки, леса, поля, населенные пункты, здания… Ты же не хочешь перебирать все полигоны для определения к какой категории принадлежат те или иные?

Монте-Карло?

Монте-Кристо, блджад.

Чуваку нужно найти пересечение списка полигонов А со списком полигонов Б.

Зачем тут Монте-Карло?!?

Ты же не хочешь перебирать все полигоны

Хочет, в ОП-посте написано.

Я б решал задачу с обратного конца, т.е. сначала создаёшь удобные типы данных, а потом через них уже и решаешь. Т.е. полигон — это запись со списком вершин, типом и координатами левого-нижнего, правого-верхнего углов. Тогда для каждой зоны можно легко найти все входящие в неё полигоны, посмотреть их типы и решить задачу.

Отличное решение. Правда, ТС его, похоже, не заметил.

Если пересечений нет, то прямоугольник либо целиком внутри полигона, либо целиком снаружи. Тогда останется проверить одну любую точку прямоугольника, принадлежит ли она хоть какому-то полигону или нет.

Правда, если полигоны могут сами друг на друга накладываться, такой простой вариант не сработает. Тогда, как вариант, построить служебный прямоугольник, идентичный исходному, а потом на каждом пересечении «откусывать» от него пересекающий кусок. Не забыть учесть, что бывший прямоугольник может превратиться в набор несвязанных друг с другом островков.

Реальная жизнь диктует свои условия. У меня есть карта в том виде, в котором она есть. Никто её перерисовывать не будет. Никогда.

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

У тебя вариант либо проверять бесконечное число точек одного полигона на принадлежность другому, либо не бесконечное.

У тебя вариант либо проверять бесконечное число точек одного полигона

Норкоман? У полигона ограниченное число вершин.

1. Проверить, что все вершины внутри

2. Проверить что все вершины снаружи

3. Проверить все ребра на пересечения

4. Проверить, что не попал в наложения вершин/ребер

Такое себе

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

А найти пересечения двух многоугольников в евклидовом пространстве - задача чуть ли не для средней школы.

Видимо тс не закончил школу.

Разбиваешь полигон земли на выпуклые полигоны. Потом проверяешь каждую точку интересующего тебя квадрата на принадлежность всем выпуклым подполигонам нужного тебе полигона земли.

Пример:

p1 = [1.00000   0.00000
   0.50000   0.86603
  -0.50000   0.86603
  -1.00000   0.00000
  -0.50000  -0.86603
   0.50000  -0.86603
   1.00000  -0.00000];
   
function retval = poly_test(P, x)
  S = [0 -1,
    1 0];
    
  n = norm(diff(P), 2, "rows");
  
  A = S*diff(P)'*diag(1./n);
  d = diag((x-P)*A);
  if sum(d>=0) < size(P)(1)-1
    retval = 0;
    return
  else
    retval = 1;
    return
  endif
endfunction

poly_test(p1, [1.1, 0])
poly_test(p1, [0.1, 0])

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

bool PolygonObject::IsPointInsideObject(const QPoint &pt)
{
    QList<QPointF> ptlist;
    ptlist.reserve(_PointArray.size());
    std::copy(_PointArray.cbegin(), _PointArray.cend(), std::back_inserter(ptlist));
    auto poly = QPolygonF(ptlist);
    if(poly.containsPoint(pt.toPointF(), Qt::WindingFill))
        return true;
    return false;
}

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

Вроде не совсем по теме, но исходники кутей никто посмотреть не мешает.

Отрисовать карту в картинку, землю «залить» зелёным, море - голубым. Потом по координатам смотреть цвет.

А ещё можно при создании карты эту информацию сразу сохранять

В общем задачу решил так: графический движок, который я использую, умеет находить пересечения полигонов. Методом Гаусса я получаю площадь этих пересечений и могу получить процент покрытия землёй каждой зоны. 1.0 – нет воды, 0.0 – одна вода, остальное – есть и то и другое.

В общем задачу решил так

https://github.com/AngusJohnson/Clipper2:

A Polygon Clipping and Offsetting library (in C++, C# & Delphi)

Внизу есть ссылки на другие реализации для WASM, Java, Kotlin, Go и Lua.

Есть идеи?

https://cgal.org - всё что с вычислительной геометрией это туда :-) пересечения полигонов, диаграммы вороного и прочее-прочее

kfa2 slider-01
не дают писать в толксах, некромонгеры, если я знаю ответ на вопрос..