@Magneto903

Можно ли как-то оптимизировать/ускорить этот код?

У меня есть такая задача:
Есть множество (100-1000) выпуклых полигонов (многоугольников)

Необходимо от каждой вершины каждого полигона построить касательные (по 2 касательные на каждый) на все другие полигоны, которые не пересекают (касаться могут) ни один из полигонов
Я это делал так:

Сначала генерирую много выпуклых полигонов

Затем для каждой вершины каждого полигона
строю от этой вершины 2 касательные на каждый полигон и проверяю, не пересекают ли какой-нибудь полигон касательные.

Но для 20 полигонов это работает почти 4 секунды. Но сколько это будет работать для 100 полигонов? Для 1000?
Мне надо, чтобы для 100-1000 полигонов это работало быстро. Возможно ли как-то решить эту задачу (улучшив этот алгоритм, или вообще используя другой алгоритм)?

Для построения касательных и проверки пересечения отрезка и полигона я использую библиотеку turf.js
  • Вопрос задан
  • 223 просмотра
Решения вопроса 1
wataru
@wataru
Разработчик на С++, гуглер, экс-олимпиадник.
Как я уже писал в другом вопросе - вам не нужны касательные из каждой точки на все полигоны. Нужны лишь общие касательные к каждой паре полигонов. Если полигоны не пересекаются, то таких всего 4 штуки. Если же они пересекаются, то их может быть сколько угодно.

Как-то сильно ускорить мне не удалось, но можно брать каждую точку одного полигона, строить 2 касательные на другой полигон и оставлять только те, которые одновременно являются касательными к первому полигону.
Это проверяется через векторные произведения веторов-сторон и вектора отрезка между полигонами. Отрезок между полигонами должен быть между двумя векторами сторон (если они ориентированны в одну сторону, скажем, против часовой стрелки). Это должно уже в почти в 4 раза уменьшить количество отрезков у вас.

Еще, возможно, тут проблема не в касательных. Вот у вас 20 полигонов, в каждом по 8 точек - это 160 точек начал. Для нахождения касательных к полигону можно перебрать все вершины. Это еще раз по 20*8=160. Итого, получается 160^2=25600 операций. Операции сложные (найти 3 вектора, взять векторные произведения), да. Но жаже если умножить это на 50, получается 1,280,000 элементарных операций. Современные процессоры выполняют миллиарды таких операций в секунду. Т.е по этой грубой прикидке - построение всех касательных занимает считанные миллисекунды.

У вас очень тормозит проверка на пересечения возможных кандидатов с полигонами.
Во-первых, как только вы нашли пересечение - можно дальше не проверять. Разделите циклы по intersect_any_1 и intersect_any_2 и останавливайтесь, как только нашли пересечение. Во-вторых, вы для каждой касательной заново строите объекты turf.js. Это, возможно, очень медленно.

Ну и, похоже turf.js слишком тормозной. Моя демка на C++ для 100 полигонов находит все хорошие касательные без пересечений за 30мс. А если отсекать полигоны по bounding box, то 16-20мс. Ну в 10 раз javascript медленнее. У вас явно что-то совсем не то делается где-то.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@Daddy_Cool
да, понять непросто.
Есть множество (100-1000) выпуклых полигонов (многоугольников)

Висят в пространстве касаясь или не касаясь друг друга ориентированные как угодно? Или это всё на плоскости происходит ?
Необходимо от каждой вершины каждого полигона построить касательные (по 2 касательные на каждый)
Что за касательные? ОК, пусть две прямые к каким-то точкам полигона.
на все другие полигоны,

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

Вроде ясно.
Если у вас N полигонов, то задача имеет сложность N^2 только для прямых.
Т.е. скорость будет сильно падать с увеличением количества полигонов.
для 20 полигонов это работает почти 4 секунды. Но сколько это будет работать для 100 полигонов? Для 1000?

Считаем - в 5 раз больше полигонов - в 25 раз дольше, т.е. 100 секунд.
В 40 раз больше - в 1600 раз дольше. Т.е. полтора часа.
Если полигонов много, это надо на CUDA делать, такие вещи хорошо параллелятся.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Artezio Нижний Новгород
от 130 000 до 180 000 ₽
Artezio Москва
от 160 000 до 220 000 ₽
Sportrecs Москва
от 150 000 до 200 000 ₽
30 нояб. 2020, в 22:50
100000 руб./за проект
30 нояб. 2020, в 22:47
600 руб./в час
30 нояб. 2020, в 22:24
3000 руб./за проект