LINUX.ORG.RU

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

 , ,


0

1

А вдруг у кого есть опыт и сможет подсказать куда копать.

Сразу рассказываю на конкретном примере, чтобы не продираться через абстракции.

Есть карта мира, где земля (каждая страна и остров) заданы полигоном. Набором отрезков, формирующих периметр. Вода – всё что не земля.

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

Нужно все зоны проанализировать на доступ к воде и земле. Т.е. зона1 – чисто вода (тут просто – нет пересечения ни с одним из «земляных» полигонов)

Есть пересечение хоть с каким-то земляным полигоном? Хорошо, помечаем как наличие доступа к земле.

А как определять зоны без доступа к воде? Т.е. полностью покрытые земляными полигонами?

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

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

yars068 ★★★★★
()
Последнее исправление: yars068 (всего исправлений: 1)
Ответ на: комментарий от yars068

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

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

tempUser
() автор топика

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

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

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

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

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

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

Kroz ★★★★★
()
Последнее исправление: Kroz (всего исправлений: 7)
Ответ на: комментарий от Kroz

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

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

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

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

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

ya-betmen ★★★★★
()
Ответ на: комментарий от Kroz

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

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

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

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

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

tempUser
() автор топика

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

vazgen05 ★★★
()

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

Irma ★★★
()
Ответ на: комментарий от ya-betmen

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

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

Kroz ★★★★★
()

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

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

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

anonymous
()

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

anonymous
()
Ответ на: комментарий от anonymous

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

pfg ★★★★★
()

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

anonymous
()

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

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

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

Psilocybe ★★★★★
()
Ответ на: комментарий от Kroz

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

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

ya-betmen ★★★★★
()
Последнее исправление: ya-betmen (всего исправлений: 1)
Ответ на: комментарий от ugoday

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

tempUser
() автор топика
Ответ на: комментарий от ya-betmen

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

tempUser
() автор топика
Ответ на: комментарий от tempUser

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

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

Irma ★★★
()
Ответ на: комментарий от ugoday

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

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

tempUser
() автор топика
Ответ на: комментарий от tempUser

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

anonymous
()
Ответ на: комментарий от tempUser

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

ugoday ★★★★★
()
Ответ на: комментарий от anonymous

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

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

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

COKPOWEHEU
()
Ответ на: комментарий от ugoday

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

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

tempUser
() автор топика
Ответ на: комментарий от ya-betmen

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

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

LamerOk ★★★★★
()
Последнее исправление: LamerOk (всего исправлений: 1)
Ответ на: комментарий от LamerOk

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

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

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

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

Такое себе

ya-betmen ★★★★★
()
Ответ на: комментарий от ya-betmen

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

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

LamerOk ★★★★★
()

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

Пример:

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])
anonymous
()

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

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, для проверки пересечения с другим полигоном.

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

Loki13 ★★★★★
()

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

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

pihter ★★★★★
()

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

tempUser
() автор топика