Блог

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

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

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

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

Редактировать:

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

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

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

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

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

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

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

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

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

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

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

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

Вот алгоритм в нотации, подобной 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 ) полигонов, гораздо большие наборы полигонов могут быть обработаны за разумное время.