Python проблема производительности: разница между двумя полигонами - PullRequest
Новая
       2

Python проблема производительности: разница между двумя полигонами

0 голосов
/ 06 февраля 2020

Я сейчас использую Python 3.7 и хочу найти разницу между многими полигонами. Под этим я подразумеваю, что если у меня есть многоугольник A и многоугольник B , я хочу выполнить математическую операцию "A not B" . Есть два возможных результата этой операции, как показано на следующем рисунке:

enter image description here

Таким образом, два многоугольника, которые я вычитаю («вырезаем») друг из друга либо дайте мне новый многоугольник, либо пусто. Все остальные случаи можно игнорировать. Форма многоугольника не обязательно должна быть точной для случая 1. Поэтому допустимо, если многоугольник немного меняется.

Для случая 2 мне нужно знать, является ли многоугольник пустым.

Кроме того, в многоугольнике A и B нет никаких "дырок", поэтому они могут быть описаны только своей внешней границей.

Я уже создал прототип, который использует операцию difference shapely для этого. Я «обрезаю» как можно меньше (один раз на каждые два многоугольника).

Мой код немного сложен, но в основном он разбивается на эту простую функцию: 

def cut_hole(A : Polygon, B : Polygon) -> Polygon:
    """
    Cuts a "hole" into shapely polygon A
    :return: The polygon resulting of the operation A-B. Might be empty!
    """
    outer = A #not in my code, just to point out what I mean
    inner = B
    return outer.difference(inner)

Теперь мой Проблема в том, что это очень медленно! Я работаю примерно с 15.000 операциями в пакете (30.000 полигонов), и мне требуется около 10-15 минут, чтобы рассчитать их все. Мне бы очень хотелось, чтобы go было меньше 5 минут.

Пожалуйста, имейте в виду, что это не учитывает все другие операции. 15 минут только для разностной операции. Я могу отсортировать каждый многоугольник А до каждого многоугольника В менее чем за 1 мин. Мне просто нужен быстрый способ получить полученный полигон из них.

Я провел этот тест на «хорошем» компьютере (Intel Core i7, 16 ГБ Ram). Ни у ЦП, ни у ОЗУ не было предела.

Итак, большой вопрос: как я могу ускорить это?

Есть ли способ перевести полигоны в форму, которую легче ручка? Или есть «лучший» способ получить разницу двух полигонов?

Есть ли альтернативная библиотека, которая может быть лучше? Или я могу получить хорошее использование другого оборудования? Если да, то какое это может быть оборудование?

Наконец, мой следующий шаг - попытаться распараллелить «вырезание». Есть ли встроенный способ сделать это быстро и эффективно? Потому что я не нашел его в форме.

Также я был бы очень признателен за советы по анализу возможных узких мест.

Приложение:

Некоторые из полигоны кажутся довольно сложными. Я имею в виду, что в среднем более сложные полигоны содержат 15.000 точек. Несложные полигоны менее 100 баллов. Однако обычно (как в 99%) полигоны типа A или типа B не являются сложными одновременно.

Вот пример сложного многоугольника в WKT

1 Ответ

1 голос
/ 06 февраля 2020

Принимая ваши точки по порядку:

  • Я очень сомневаюсь, что есть другой, более подходящий формат / библиотека для манипулирования полигонами в python, чем shapely, это справочный пакет. Вы можете попробовать simplify свою геометрию, но некоторые быстрые тесты показали, что это также медленная операция (p - полигон, который вы копировали выше): 

    p2 = p.buffer(-10)                   # creating a 2nd polygon
%timeit p.simplify(1)                # 58.4 ms, from 15000 to 8000 points
%timeit p.difference(p2)             # 53.2 ms 

%timeit p.difference(p2.simplify(1)) # 127ms
%timeit p.simplify(1).difference(p2) # 114ms

  • Shapely использует GEOS под капотом. Возможно, вы можете попытаться покопаться в этом направлении для решений более низкого уровня.

  • В стройном параллелизме нет. Однако, поскольку вы, похоже, уже сопоставили свои полигоны «As» и «Bs», вы можете распараллелить фигурную операцию через пул потоков или пул процессов (см. multiprocessing package). Если они не совпадают, вы можете проверить это быстро через intersects (намного быстрее, чем intersection или difference. Если некоторые из ваших полигонов не пересекаются, это будет огромное ускорение.

  • Учитывая размер ваших данных (5 ГБ - это много геометрий ...), я не думаю, что вы можете сэкономить столько времени, кроме как с распараллеливанием, так как один difference занимает ~ 70 мс, что дает ~ 1050 с = 17 мин для 15000 операций

...