Исходный многоугольник

Cтраница 3

Все стороны, не принадлежащие заштрихованным многоугольникам, входят в периметр исходного и полученного многоугольников. Что же касается заштрихованных многоугольников, то их стороны, лежащие на прямой сгиба, входят в периметр полученного многоугольника, а все остальные стороны - в периметр исходного многоугольника. Так как у любого многоугольника сумма его сторон, лежащих на некоторой прямой, меньше суммы остальных сторон, то периметр исходного многоугольника всегда больше, чем периметр полученного. [31]

Теперь мы готовы к обсуждению самого алгоритма вычисления пар видимости. Входными данными для алгоритма служит описание одной области видимости V. Чтобы алгоритм можно было применить к исходному многоугольнику, мы преобразуем этот многоугольник в область видимости, разбив его границу на два боковых граничных сегмента, концевыми вершинами которых являются вершины исходного многоугольника с минимальной и максимальной / - координатой; / - координаты этих двух вершин выбираются в качестве значений г / min и Утах для получаемой таким образом области. Приводимый ниже алгоритм аналогичен алгоритму из разд. [32]

Схематичное представление области видимости. Каждая кривая представляет сегмент, являющийся частью границы многоугольника. [33]

Каждый такой горизонтальный отрезок, не вырождающийся в точку, соответствует паре видимости. На каждой из прямых у утш и у утах лежит не более чем одна вершина исходного многоугольника. Граничный сегмент начинается вершиной или частью стороны исходного многоугольника, называемой усеченной стороной, и заканчивается вершиной или усеченной стороной. Сторона исходного многоугольника, содержащая усеченную сторону, называется концевой стороной сегмента. [34]

А именно концевые точки каждого разреза в более сложном из двух многоугольников определяются пересечениями хорд. В / г-угольнике или / г-грамме угол между двумя хордами равен я / и или кратен я / и, если и четно, а если и нечетно, то он может быть дополнительным к такому углу. Следовательно, при данном разрезании любая сторона любой части равна стороне исходного многоугольника, умноженной на рациональную функцию от синусов и косинусов углов, кратных я / и. Ограничимся парой многоугольников, у которых углы я / и равны или один из углов равен целому кратному другого с небольшим множителем. В подобных случаях, если решение обладает вышеуказанной характерной чертой, сторона s2 второго многоугольника равна умноженной на RTF стороне Si исходного многоугольника. Преобразование двух таких многоугольников, как мы видели, оказывается необычайно экономным. Это побуждает нас заняться систематическим исследованием таких пар многоугольников. [36]

Страницы: 1 2 3