Что-то это почти один-в-один напоминает задачу поиска ближайших соседей (k-nearest neighbour, k-NN), для которой построено много классических алгоритмов, как точных, так и гораздо более быстрых приближенных. Может, туда посмотреть?
Я применил "в лоб" только один из приёмов (точный, а не приближенный), заимствованных оттуда. Это сразу дало прирост x8 на вашем тестовом примере с 1000 полигонов. Вкратце. Замечу, что в этом примере расстояния ищутся не эффективно. Для каждой точки в приведенном примере мы пробегаем ВСЕ полигоны и считаем расстояние до их центров. Это можно значительно улучшить, если найти ОДИН ОПОРНЫЙ полигон, лежащий в интервале max_dist, и ограничить дальнейший перебор только теми полигонами, которые лежат не далее, чем (2*max_dist) от найденного опорного. Расстояния между центрами полигонов можно кэшировать в словарь словарей расстояний, построенный на идентификаторах полигонов {id0: {id1: distance, id2:distance, ...}, ...}. Вложенные словари упорядочены по distance. Поэтому отбор ближайших полигонов для найденного опорного ведем по словарю и прекращаем, как только очередная дистанция превысила 2*max_dist.
Если вам достаточно приближенного решения, то есть жадный алгоритм поиска ближайших соседей. Он имеет существенно меньшую вычислительную сложность, чем точный, и как следствие, работает радикально быстрее на большом количестве элементов.
Сказанное выше сработает, если полигоны относительно статичны (не меняются "слишком часто"), иначе пересчет кэша расстояний съест весь выигрыш.
Дальнейшие размышления. В тестовом примере рассмотрен синтетический случай. Полигоны генерятся так, что РАВНОМЕРНО распределяются по указанной области. Я подозреваю, что в вашей реальной задаче это не так, и полигоны собраны в какие-то кластеры (возможно, ограничивают более-менее статичный 3D-объект?). Если да, то: 1) Вышеуказанный алгоритм даст еще больший выигрыш, т.к. равномерное распределение полиномов для него - пожалуй, самое плохое. Наибольший выигрыш по сравнению с полным перебором он даст как раз на кластеризованных полигонах. 2) Решение можно еще качественно ускорить, явно побив полигоны по кластерам с вычисляемым центром кластера и "радиусом" границы (keyword кластерный анализ). Можно сузить изначальный поиск полигона только теми кластерами, у которых расстояние от центра до точки не более, чем max_dist+cluster_radius
Ну и еще - в синтетическом примере работа ведется со списками питона, которые заметно медленнее, чем словари. Надеюсь, списки так используются только в синтетическом примере, а не в проде. А про ускорение numpy-вычислений другие участники уже написали.
Мне кажется, что эта тема возникла только из-за несоответствия абстрактной теории с конкретным ее применением. У любой реализации (у любого применения теории) есть допущения и есть границы, в которых эти допущения работают. Если пытаешься применить теорию на границах (за границами) - сам себе злобный Буратино. Это как бегать с ньютоновской механикой вокруг синхрофазотрона
Читаю, читаю, а мне всё хуже и хуже...
Что-то это почти один-в-один напоминает задачу поиска ближайших соседей (k-nearest neighbour, k-NN), для которой построено много классических алгоритмов, как точных, так и гораздо более быстрых приближенных. Может, туда посмотреть?
Я применил "в лоб" только один из приёмов (точный, а не приближенный), заимствованных оттуда. Это сразу дало прирост x8 на вашем тестовом примере с 1000 полигонов. Вкратце.
Замечу, что в этом примере расстояния ищутся не эффективно. Для каждой точки в приведенном примере мы пробегаем ВСЕ полигоны и считаем расстояние до их центров. Это можно значительно улучшить, если найти ОДИН ОПОРНЫЙ полигон, лежащий в интервале max_dist, и ограничить дальнейший перебор только теми полигонами, которые лежат не далее, чем (2*max_dist) от найденного опорного. Расстояния между центрами полигонов можно кэшировать в словарь словарей расстояний, построенный на идентификаторах полигонов {id0: {id1: distance, id2:distance, ...}, ...}. Вложенные словари упорядочены по distance. Поэтому отбор ближайших полигонов для найденного опорного ведем по словарю и прекращаем, как только очередная дистанция превысила 2*max_dist.
Если вам достаточно приближенного решения, то есть жадный алгоритм поиска ближайших соседей. Он имеет существенно меньшую вычислительную сложность, чем точный, и как следствие, работает радикально быстрее на большом количестве элементов.
Сказанное выше сработает, если полигоны относительно статичны (не меняются "слишком часто"), иначе пересчет кэша расстояний съест весь выигрыш.
Дальнейшие размышления. В тестовом примере рассмотрен синтетический случай. Полигоны генерятся так, что РАВНОМЕРНО распределяются по указанной области. Я подозреваю, что в вашей реальной задаче это не так, и полигоны собраны в какие-то кластеры (возможно, ограничивают более-менее статичный 3D-объект?). Если да, то:
1) Вышеуказанный алгоритм даст еще больший выигрыш, т.к. равномерное распределение полиномов для него - пожалуй, самое плохое. Наибольший выигрыш по сравнению с полным перебором он даст как раз на кластеризованных полигонах.
2) Решение можно еще качественно ускорить, явно побив полигоны по кластерам с вычисляемым центром кластера и "радиусом" границы (keyword кластерный анализ). Можно сузить изначальный поиск полигона только теми кластерами, у которых расстояние от центра до точки не более, чем max_dist+cluster_radius
Ну и еще - в синтетическом примере работа ведется со списками питона, которые заметно медленнее, чем словари. Надеюсь, списки так используются только в синтетическом примере, а не в проде. А про ускорение numpy-вычислений другие участники уже написали.
Мне кажется, что эта тема возникла только из-за несоответствия абстрактной теории с конкретным ее применением. У любой реализации (у любого применения теории) есть допущения и есть границы, в которых эти допущения работают. Если пытаешься применить теорию на границах (за границами) - сам себе злобный Буратино. Это как бегать с ньютоновской механикой вокруг синхрофазотрона