Есть ли оптимизированный способ получить выпуклую оболочку, если я знаю, что мои точки всегда расположены в два прямоугольника?
Я запрограммировал классический алгоритм выпуклой оболочки (просто перечислив все точки), но, поскольку у меня есть куча пар прямоугольников, я блуждал, не мог ли быть более эффективный способ сделать это для этого особого случая.
Это то, о чем я говорю, чтобы уточнить:
Я пробовал сортировать точки разными способами, но не могу найти общего правила для оптимизации. Является ли базовый алгоритм выпуклой оболочки наиболее эффективным способом и в этом случае?
Обновить
Чтобы прояснить мою конечную цель, у меня есть ~ 100 прямоугольников, уже сгруппированных в пары по два, и тысячи точек, для которых я должен проверить, лежат ли они внутри каждой из этих выпуклых оболочек в режиме реального времени. Теперь, когда я немного подумал об этом, я думаю, что выпуклая часть корпуса не будет узким местом во всей операции (но их все еще ~ 100, и я стремлюсь к обработке 60 кадров в секунду в реальном времени), так что я мог бы также используйте простой старый алгоритм, как предложил @BartKiers, а затем вернитесь к этому после профилирования.
Я оставлю вопрос открытым на некоторое время, возможно, у кого-то есть идея оптимизации, которая в любом случае может быть полезна.
