Максимальная площадь пересечения участников заданных n геометрических фигур

Question

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

У меня есть следующие ограничения;

• ни одна из фигур не может пересекаться (пересечение между формами отсутствует, пересечение с 0 участниками)
• все фигуры могут пересекаться (есть пересечение во всех фигурах, пересечение n-участников)
• может быть более одного пересечения с k участником (форма A B C пересекается, форма D E F пересекается, есть пересечение 2 3 участников, не нужно находить оба, возвращать, когда найдены первые 3 участника)

Итак, в качестве отправной точки я, хотя и мог бы сделать это, используя грубую силу (пытаясь пересечь n, n-1, n-2 комбинацию заданных фигур), но сложность по времени будет O (n!). Мне интересно, если бы алгоритм мог быть оптимизирован?

РЕДАКТИРОВАТЬ:

Ну, я забыл рассказать о типах данных. Я использую библиотеку Esri / geometry для фигур. В частности, Polygon экземпляры класса.

Answer 1

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

1.Итеративное пересечение

Сохранение списка L (непересекающихся) полигонов с количеством отсчетов, которое в начале пусто.Теперь итерируйте данные полигоны P.Для каждого многоугольника p из P пересекают его со всеми многоугольниками l из L.Если есть пересечение между p и l, тогда удалите l из L и

• add set_intersection (l, p) с помощью previous count of l +1
• addset_minus (l, p) с `предыдущим счетом l '
• запомнить set_minus (p, l) и перейти к следующей записи L

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

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

2.Разложение пространства

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

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

Answer 2

Список необработанных (непустых) пересечений вместе с индексами полигонов, из которых было создано пересечение, сохраняется. Первоначально он заполнен отдельными полигонами. Всегда пересечение с большинством многоугольников и наименьшим максимальным индексом задействованных многоугольников убирается и пересекается со всеми многоугольниками с более высокими индексами (чтобы не смотреть снова и снова на одно и то же подмножество многоугольников). Это позволяет эффективно обрезать:

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

Вот алгоритм в Python-подобных обозначениях:

def findIntersectionFromMostMembers(polygons):
  unprocessedIntersections = [(polygon, {i}) for i, polygon in enumerate(polygons)]
  unprocessedIntersections.reverse() # make polygon_0 the last element

  intersectionFromMostMembers, indicesMost = (polygons[0], {0})
  while len(unprocessedIntersections) > 0:
    # last element has most involved polygons and least maximal polygon index
    # -> highest chance of being extended to best intersection
    intersection, indices = unprocessedIntersections.pop() # take out unprocessed intersection from most polygons

    if len(indices) + n - max(indices) - 1 <= len(indicesMost):
      continue # pruning 1: this intersection cannot beat best found solution so far
    for i in range(max(indices)+1, n): # pruning 2: only look at polyong with higher indices
      intersection1 = intersection.intersect(polygons[i])
      if not intersection1.isEmpty(): # pruning 3: empty intersections do not need to be considered any further
        unprocessedIntersections.insertSorted(intersection1, indices.union({i}), key = lambda(t: len(t[1]), -max(t[1])))
        if len(indices)+1 > len(indicesMost):
          intersectionFromMostMembers, indicesMost = (intersection1, indices.union({i}))

  return intersectionFromMostMembers, indicesMost

Производительность сильно зависит от того, сколько полигонов в среднем имеют общую область. Чем меньше (<< n) многоугольников имеют общие области, тем эффективнее обрезка 3. Чем больше у многоугольников общих областей, тем эффективнее обрезка 1. Обрезка 2 гарантирует, что никакое подмножество многоугольников не рассматривается дважды. Худший сценарий, по-видимому, заключается в том, что постоянная доля n (например, n/2) полигонов имеет некоторую общую область. До n=40 этот алгоритм завершается за разумное время (через несколько секунд или самое большее за несколько минут). Если непустое пересечение из большинства многоугольников включает только несколько (любая константа << n) многоугольников, гораздо большие наборы многоугольников могут быть обработаны за разумное время.