Как определить, содержит ли один полигон другой?

9

У меня есть 2 полигона. Я знаю координаты вершин обоих многоугольников. Какой лучший способ проверить, находится ли один полностью внутри другого? Например, алгоритм должен распознавать только черную трапецию, указанную ниже:

пример полигонов

user960567
источник
Я не могу дать подробный ответ прямо сейчас (возможно, сделаю это позже), но вы должны взглянуть на реализацию теоремы о разделительной оси для обнаружения столкновений. Алгоритм может быть немного изменен, чтобы легко проверить, что вы хотите. например, codezealot.org/archives/55
TravisG
1
Вам не совсем понятно, что вы понимаете под многоугольником внутри многоугольника. Что если все точки меньшего многоугольника находятся в большем, но каждая из них имеет сторону на одной линии, находятся ли они друг в друге? i47.tinypic.com/4i0sgg.jpg
speedyGonzales
@speedyGonzales, это также называется внутри.
user960567

Ответы:

5

Существует множество исходных фрагментов для метода, который выполняет тест для « точки внутри многоугольника ». Принцип исходит из теоремы Джордана о кривой для многоугольников ( http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Octavian/compgeom.html ).

Наивным способом было бы: имея этот метод, вызвать его PointInsidePolygon(Point p, Polygon poly):

  bool isInside = true;
  for each (Point p in innerPoly)
  {
    if (!PointInsidePolygon(p, outerPoly))
    {
      isInside = false; // at least one point of the innerPoly is outside the outerPoly
      break;
    }
  }
  if (!isInside) return false;
  // COMPULSORY EDGE INTERSECTION CHECK
  for each (innerEdge in innerPoly)
    for each (outerEdge in outerPoly)
    {
      if (EdgesIntersect(innerEdge, outerEdge))
      {
        isInside = false;
        break;
      }
    }

  return isInside;

Теоретически, он не должен пропустить ни одного сценария для ваших полигонов, но это не оптимальное решение.

Замечания по делу "Edge"

  • PointInsidePolygon(..) должен вернуть true, если точка находится на границе многоугольника (либо лежит на ребре, либо является вершиной)

  • EdgesIntersect(..)должен вернуть false, если innerEdgeэто подмножество (в геометрическом отношении) outerEdge. В этом случае ребра, очевидно, пересекаются, но для целей алгоритма нам нужно указать, что пересечение не нарушает семантику за isInsideпеременной

Генерал Ремакрс :

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

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

teodron
источник
1
Это вернет ложные срабатывания, когда внешний многоугольник вогнутый.
Сам Хочевар
2
Как ни странно, хотя теодрон и рыцарь666 индивидуально ошибочны, при объединении они должны дать правильный ответ. Если все точки многоугольника находятся внутри другого, и если их линии не пересекаются, то первый многоугольник полностью находится внутри другого.
Хакворт
Правда, он возвращает ложные срабатывания, он также должен учитывать пересечения ребер.
Теодрон
Это кажется правильным ответом. Я думаю, что не нужно проверять условие второго цикла.
user960567
Это не работает для пересечений конечной точки или если края перекрываются.
Брэндон Кон
2

Попробуйте сделать пересечение линии с каждой красной линией. В псевдокоде:

// loop over polygons
for (int i = 0; i < m_PolygonCount; i++)
{
    bool contained = false;

    for (int j = 0; j < m_Polygon[i].GetLineCount(); j++)
    {
        for (int k = 0; k < m_PolygonContainer.GetLineCount(); k++)
        {
            // if a line of the container polygon intersects with a line of the polygon
            // we know it's not fully contained
            if (m_PolygonContainer.GetLine(k).Intersects(m_Polygon[i].GetLine(j)))
            {
                contained = false;
                break;
            }
        }

        // it only takes one intersection to invalidate the polygon
        if (!contained) { break; }
    }

    // here contained is true if the polygon is fully inside the container
    // and false if it's not
}

Однако, как вы можете видеть, это решение будет работать медленнее, если вы добавите больше полигонов для проверки. Другое решение может быть:

  • Рендеринг многоугольника контейнера в пиксельный буфер с белым цветом.
  • Рендеринг дочернего полигона в другой пиксельный буфер с белым цветом.
  • Маска буфера контейнера поверх полигонального буфера с помощью маски XOR.
  • Подсчитайте количество белых пикселей; если он больше 0, дочерний полигон не полностью содержится в контейнере.

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

knight666
источник
1
Пересечения линий будет недостаточно, чтобы обнаружить полностью содержащиеся многоугольники.
Kylotan
1
Вопрос: если многоугольники полностью не пересекаются, ребра не пересекаются. Будет ли это работать в этом случае? Второй подход, основанный на графике, должен действительно работать!
Теодрон