Опорные прямые = касательные к выпуклым многоульникам
У меня есть два выпуклых многоугольника, заданных своими вершинами в каком-то порядке обхода (например, по часовой стрелке с произвольной вершины, std::vector<Point>). Как найти за линейное время верхнюю и нижнюю касательные к этим многоульникам? То есть такие две точки, что первая принадлежит первому многоульнику, вторая - второму, и при этом прямая больше не пересекает многоульники. Верхняя означает, что все точки многоульников кроме этих двух лежат ниже этой прямой, нижняя - выше.
Считаем, что для заданных многоульников такие касательные всегда существуют.
Пунктиром обозначены нужные касательные.
Ответы (1 шт):
Для решения подобных задач за линейное время предназначен алгоритм Rotating Calipers
Именно эта задача, похоже, называется "установление моста между выпуклыми многоугольниками" или объединение выпуклых полигонов, также см. "common tangents"
Хорошая страница о них убита, сохранилась в wayback архиве