Есть ли какой-нибудь метод scipy, который вычисляет выпуклую оболочку двух непересекающихся многоугольников? У меня есть 2 набора точек P1 и P2 и их выпуклые оболочки CH (P1) и CH (P2), где оболочки не пересекаются. Я хочу найти выпуклую оболочку объединения точек в P1 и P2. Есть ли встроенный метод в scipy?
Вычисление выпуклой оболочки двух непересекающихся многоугольников в scipy
comment
Вопросы по кодированию и вопросы о конкретных библиотеках программирования или языках не относятся к теме CS.SE, но их можно задать на Stack Overflow. См. наш справочный центр. CS.SE предназначен для вопросов о концепциях, алгоритмах и науке.
- person D.W. schedule 04.11.2016
Ответы (1)
Документацию по реализации выпуклой оболочки Scipy можно найти здесь. Просто соедините два массива точек, чтобы получить их объединение. Передайте этот набор алгоритму выпуклой оболочки.
Каждая точка каждого многоугольника лежит внутри выпуклой оболочки своего многоугольника. В свою очередь, выпуклая оболочка обоих многоугольников полностью содержится внутри большей выпуклой оболочки. Таким образом, каждая точка в каждом многоугольнике лежит внутри большей выпуклой оболочки, а это означает, что это также справедливо для полного объединения точек многоугольника.
person
Arthelais
schedule
03.11.2016
Но когда в метод подается объединение точек, сложность становится nlogn, тогда как выпуклая оболочка объединения может быть определена за линейное время.
- person Sudipta Roy; 03.11.2016
Вы правы в том, что для решения вашей проблемы существует линейный алгоритм. Однако это очень специфическая оптимизация, не реализованная в SciPy. Вам действительно нужно решить задачу линейно? Если у вас нет массивных наборов очков, это не будет намного быстрее.
- person Arthelais; 03.11.2016
Мне это нужно для одного из моих заданий. Это не основная часть задания. Я думаю, я могу жить с этим. Это просто не делает алгоритм nlogn .
- person Sudipta Roy; 03.11.2016
В моем предыдущем комментарии есть ссылка на книгу, в которой есть реализация, которую вы могли бы использовать, но она не на Python.
- person Arthelais; 03.11.2016
Да, я знаю об этом. Я думал, есть ли короткий метод для этого. Спасибо, в любом случае.
- person Sudipta Roy; 03.11.2016
