tgoop.com/the_algorithms/4683
Last Update:
Касательные между двумя выпуклыми многоугольниками
Чтобы найти касательные между двумя выпуклыми многоугольниками, вы можете выполнить следующие общие шаги.
Алгоритм:
1. Убедитесь, что полигоны отсортированы против часовой стрелки.
2. Определите вершину в каждом многоугольнике, ближайшую к другому многоугольнику. Эти вершины являются потенциальными отправными точками касательных линий.
3. Для каждой из вершин, определенных на шаге 2, вычислите касательные линии от этой вершины к другому многоугольнику.
4. Убедитесь, что каждая рассчитанная касательная не пересекает внутреннюю часть ни одного многоугольника.
5. Сохраните эти касательные, они являются касательными между двумя многоугольниками.
Сложность: O(n1 log (n1) + n2 log(n2))
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4683