Алгоритм: создать крышу с максимальной высотой
Я нашел эту проблему в книге и отчаянно пытаюсь ее решить. Сам вопрос: создать крышу (неплоские крыши) с максимальной высотой. Стены находятся под углом 90 градусов или параллельно.
Мой подход:
У меня есть все крайние точки. Так что я могу использовать метод сканирования. Я отсортирую все свои точки по оси X, а затем по оси Y. Затем я пройду весь список точек и нарисую линию под углом 45° к стенам. Я проверю, пересекается ли какая-либо линия с моей текущей линией, которую я уже нарисовал. Если нет совпадения, я перейду к следующей точке и нарисую еще одну линию под углом 45° к стенам. Теперь велика вероятность того, что последние 2 линии пересекаются, и поэтому я создам новую точку в точке пересечения.
У меня проблема в том, что было бы много особых случаев. Есть ли более простой способ, о котором я не думал? Существуют ли другие алгоритмы, которые больше подходят для такого рода проблем? Что бы вы подумали о такой проблеме?
Пример:
Вот на что похожа крыша.
2 ответа
Я не уверен, что это то, что вы имели в виду, но мой ответ нацелен на достижение крыши с максимальной высотой заглядывания, а не с максимальной средней высотой.
Максимальная высота взгляда в этой задаче определяется максимальным квадратом, который может вписаться в вашу структуру.
Поэтому, чтобы найти его, вам просто нужно найти максимальный квадрат, который может поместиться, и выполнить простое вычисление высоты пирамиды. Например, если вы нашли квадрат с краем aи вы строите крышу под углом 45 градусов от основания, как вы упомянули, затем: Peek = sqrt(3)*a,
Поиск максимального квадрата не должен быть сложной задачей: для каждого угла в структуре, идти в каждом направлении (вверх, вниз, влево, вправо) по прямой линии, пока вы не выйдете из структуры (предположим, мы получили эти значения up, down, left, right), максимальный квадрат, который может быть построен из угла, является максимальным значением между min{up, left}, min{up, right}, min{down, left}, min{down, right}, а максимальный квадрат - это максимальное значение, полученное из любого угла.
Теперь построим пирамиду, откуда из угла с максимальным значением. в остальной части структуры вы можете делать все, что захотите, так как она не превзойдет высоту этой пирамиды.
Многие люди критиковали то, как я задал свой вопрос, что чего-то не хватает, и действительно, не хватает входных данных. Так что в качестве входных данных у меня есть пример набора точек:
(0, 0) (6, 0) (6, -2) (8, -2) (8, 8) (-2, 8) (-2, 3) (0, 3)
в правильном порядке.
Следующее, что мне нужно сделать, это разместить точки, как у меня на рисунке 1. В моем случае я поместил их немного в нижнем правом углу. Теперь необходимо увидеть, какие точки имеют форму, а какие - нет. Это можно легко определить, пересекая горизонтальные и вертикальные линии, которые вы делаете из точки здания. Если вы найдете нечетное число, вы знаете, что дело в форме. В противном случае мы удаляем его.
После всего этого мы пытаемся найти самый большой прямоугольник, который мы можем создать из каждой найденной точки (красная линия). Единственное, чего нам не хватает сейчас, так это того, что мы создаем новую точку в нижнем правом прямоугольнике и делаем другой прямоугольник в верхнем левом углу (желтая линия). Как видно из моего примера, мы находим в этом примере самый большой квадрат, используя меньшую сторону прямоугольника. Это разделенное на 2 даст нам наибольшую высоту формы.
Если вам нужны какие-либо дополнительные разъяснения, не стесняйтесь спрашивать меня.