Учитывая вектор направления и произвольный многоугольник (который может быть не выпуклым), что является эффективным алгоритмом для нахождения самой длинной прямой вдоль вектора, ограниченного многоугольником?Как найти самое длинное расстояние вдоль вектора внутри полигона?
примечание: оригинальная проблема, которая несколько связана с приведенной выше: задан треугольник, найдите наибольший ограниченный подобный треугольник внутри заданного многоугольника.
Вот ваш алгоритм развертки O (n log n) для вашей первой проблемы («оригинал» выглядит довольно сложным).
Предположим без ограничения общности, что вектор равен (1, 0). Предположим, что нет вырождения (это немного отличается от меня). Для каждого края многоугольника создайте событие «start» для вершины с меньшей y-координатой и событием «stop» для вершины с большим. Сортируйте события по y-координате и обрабатывайте их от наименьшего к наибольшему. Для события начала вставьте ребро в отсортированный набор, заданный координатой x пересечения ребра с текущей строкой развертки. Для события остановки удалите край. Как раз перед этим и сразу после работы на наборе проверьте, сегмент линии развертки, соединяющий два края в точке вставки/удаления, длиннее, чем самый длинный, найденный до сих пор. (Можно указать, находится ли сегмент внутри многоугольника, будут ли эти два ребра, пройденные против часовой стрелки относительно многоугольника, будут y-возрастающими или y-убывающими.)
К чему треугольник * подобный *? Сходство является свойством пары треугольников, а не одного треугольника. –
Возможно, я должен перефразировать записку, я имел в виду заданный треугольник, найти самый большой подобный треугольник, ограниченный полигоном. Я исправил это, спасибо. – ramino
Быть похожим на Хортона (слона). Скажи что ты имеешь в виду; и означает, что вы говорите. –