Поиск общих вершин среди полигонов

Question

У меня скоро появится интересная проблема, и я начал думать об алгоритме. Чем больше я думаю об этом, тем больше я боюсь, потому что я думаю, что это будет ужасно масштабироваться (O (n ^ 4)), если я не смогу стать умным. У меня проблемы с умением об этом. Вот упрощенное описание проблемы.

У меня есть N полигонов (где N может быть огромным> 10 000 000), которые хранятся в виде списка из M вершин (где M порядка 100). Что мне нужно сделать, так это создать для каждого полигона список любых вершин, которые совместно используются другими полигонами (представьте, что полигоны являются окружающими интересующими областями, иногда областями, но сталкиваются друг с другом). Я вижу что-то вроде этого

Polygon i | Vertex | Polygon j | Vertex
   1          1         2          2
   1          2         2          3
   1          5         3          1
   1          6         3          2
   1          7         3          3

Это означает, что вершина 1 в многоугольнике 1 - это та же точка, что и вершина 2 в многоугольнике 2, а вершина 2 в многоугольнике 1 - это та же точка, что и вершина 3 в многоугольнике 2. Аналогично, вершина 5 в многоугольнике 1 совпадает с вершиной. 1 в многоугольнике 3 ....

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

Единственное, что я могу сейчас сделать, это то, что для каждого многоугольника я должен перебрать все многоугольники и вершины, давая мне масштабирование O (N ^ 2 * M ^ 2), что будет очень плохо в мое дело. У меня могут быть очень большие файлы полигонов, поэтому я даже не могу сохранить все это в ОЗУ, так что это будет означать многократное чтение файла.

Вот мой псевдокод до сих пор

for i=1 to N
  Pi=Polygon(i)
  for j = i+1 to N
    Pj=Polygon(j)
    for ii=1 to Pi.VertexCount()
      Vi=Pi.Vertex(ii)
      for jj=1 to Pj.VertexCount()
        Vj=Pj.Vertex(jj)
        if (Vi==Vj) AddToList(i,ii,j,jj)
      end for
    end for
  end for
end for

Я предполагаю, что это произошло в графическом сообществе (я не провожу там много времени, поэтому я не знаю литературы). Есть идеи?

Answer 1

Это классическая проблема итерации против памяти. Если вы сравниваете каждый полигон с любым другим полигоном, вы столкнетесь с решением O (n ^ 2). Если вы строите таблицу, когда проходите все полигоны, а затем пройдете по таблице, вы получите хорошее решение O (2n). Я задаю аналогичный вопрос во время интервью.

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

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

Answer 2

Если у вас есть данные многоугольника / грани, вам даже не нужно смотреть на вершины.

• Создать массив из [0..M] (где M - количество вершин)
• перебираем полигоны и увеличиваем запись массива каждого индекса вершины.

Это дает вам массив, который описывает, сколько раз используется каждая вершина. *

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

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

(* в этом примере предполагается, что у вас нет вырожденных полигонов, но их можно легко обработать).

Answer 3

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