python: сортировка двух списков полигонов для пересечений

Question

У меня есть два больших списка полигонов.

Используя python, я хочу взять каждый многоугольник в списке 1 и найти результаты его геометрического пересечения с многоугольниками в списке 2 (я использую shapely для этого).

Таким образом, для многоугольника i в списке 1 может быть несколько многоугольников в списке 2, которые могут пересекаться с ним.

Проблема в том, что оба списка велики, и если я просто вложу два цикла и запускаю команду пересечения для каждого Возможная пара полигонов, это занимает очень много времени. Я не уверен, что предшествующее пересечению с помощью логического теста значительно ускорит это (например, если пересекается: вернуть пересечение).

Что было бы для меня хорошим способом отсортировать или упорядочить эти два списка полигонов, чтобы сделать пересечения более эффективным? Есть ли алгоритм сортировки, который подходит для этой ситуации, и который я мог бы сделать с помощью Python?

Я относительно новичок в программировании и не имею опыта в дискретной математике, так что если вы знаете существующий алгоритм что я должен использовать, (который я предполагаю, существует для таких ситуаций), пожалуйста, ссылку или дать некоторые объяснения, которые могли бы помочь мне на самом деле реализовать его в Python.

Кроме того, если есть лучший сайт StackExchange для этого вопроса, дайте мне знать. Я чувствую, что это связывает общее программирование на Python, ГИС и геометрию, поэтому я не был уверен в этом.

Answer 1

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

Answer 2

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

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