Исходный многоугольник
Cтраница 2
При этом подобное положение дела имеет общий характер: для каждого невыпуклого мюго угольника М всегда можно найти выпуклый многоугольник М, имеющий те же длины сторон, что и М ( и тот же порядок следования сторон), но большую площадь, причем переход от М к М осуществляется аналогично переходу от четырехугольника A BCD к четырехугольнику ABC D на рис. 27, а, но в несколько этапов - так, в изображенной на рис. 27 6 ситуации мы сначала отражаем часть DEFGH контура заданного многоугольника М относительно прямой Ij Е DH, получая многоугольник MI ss ABCDE F G H, который можно, пожалуй, счесть более выпуклым, чем исходный многоугольник М; затем отражаем ломаную AHG F относительно прямой / 2 AF, приходя к почти выпуклому многоугольнику Мг ABCDE F G H затем отражаем ломаную ВАН относительно прямой 1з ВН, приходя к выпуклому многоугольнику Mr ArBCDE FrG Hf. [16]
Площадь и периметр исходного многоугольника обозначим через S и Р соответственно. [17]
Идея алгоритма состоит в разбиении исходного многоугольника на совокупность монотонных под-многоугольников с последующей триангуляцией последних. Разбиение производится путем проведения ряда диагоналей в исходном многоугольнике. [18]
Если линия пересекает каждое отражение многоугольника, можно взять отражение этой линии в исходном многоугольнике и получить тем самым искомый ответ. [19]
 |
Схематичное представление области видимости. Каждая кривая представляет сегмент, являющийся частью границы многоугольника. [20] |
Каждый такой горизонтальный отрезок, не вырождающийся в точку, соответствует паре видимости. На каждой из прямых у утш и у утах лежит не более чем одна вершина исходного многоугольника. Граничный сегмент начинается вершиной или частью стороны исходного многоугольника, называемой усеченной стороной, и заканчивается вершиной или усеченной стороной. Сторона исходного многоугольника, содержащая усеченную сторону, называется концевой стороной сегмента. [21]
Все стороны, не принадлежащие заштрихованным многоугольникам, входят в периметр исходного и полученного многоугольников. Что же касается заштрихованных многоугольников, то их стороны, лежащие на прямой сгиба, входят в периметр полученного многоугольника, а все остальные стороны - в периметр исходного многоугольника. Так как у любого многоугольника сумма его сторон, лежащих на некоторой прямой, меньше суммы остальных сторон, то периметр исходного многоугольника всегда больше, чем периметр полученного. [22]
 |
Иллюстрация работы алгоритма О Рурка и др. Ребро, помеченное числом /, обрабатывается подпрограммой ДВИЖЕНИЕ на / - и итерации. Начальные ребра выделены жирной линией. [23] |
Итак, заключаем, что если после 2 ( 1 - - М) шагов подпрограммы ДВИЖЕНИЕ данный алгоритм не смог обнаружить ни одной точки пересечения, то границы исходных многоугольников вовсе не пересекаются. [24]
Теперь мы готовы к обсуждению самого алгоритма вычисления пар видимости. Входными данными для алгоритма служит описание одной области видимости V. Чтобы алгоритм можно было применить к исходному многоугольнику, мы преобразуем этот многоугольник в область видимости, разбив его границу на два боковых граничных сегмента, концевыми вершинами которых являются вершины исходного многоугольника с минимальной и максимальной / - координатой; / - координаты этих двух вершин выбираются в качестве значений г / min и Утах для получаемой таким образом области. Приводимый ниже алгоритм аналогичен алгоритму из разд. [25]
 |
Схематичное представление области видимости. Каждая кривая представляет сегмент, являющийся частью границы многоугольника. [26] |
Каждый такой горизонтальный отрезок, не вырождающийся в точку, соответствует паре видимости. На каждой из прямых у утш и у утах лежит не более чем одна вершина исходного многоугольника. Граничный сегмент начинается вершиной или частью стороны исходного многоугольника, называемой усеченной стороной, и заканчивается вершиной или усеченной стороной. Сторона исходного многоугольника, содержащая усеченную сторону, называется концевой стороной сегмента. [27]
Стороны произвольного выпуклого многоугольника покрашены снаружи. Проводится несколько диагоналей многоугольника. Доказать, что хотя бы один из многоугольников, на которые разбит диагоналями исходный многоугольник, весь покрашен снаружи. Допускается, чтобы в вершине многоугольника окраска заходила внутрь. [28]
Действительно, преобразуем первый многоугольник подобно с коэффициентом подобия, равным k A B / AB. Тогда стороны его все станут равны сторонам второго многоугольника, а углы не изменятся. По признаку равенства многоугольников полученный многоугольник будет теперь равен второму данному многоугольнику, а тем самым исходные многоугольники подобны. Еще раз обратим внимание на связь между площадями и периметрами подобных многоугольников. [29]
Действительно, преобразуем первый многоугольник подобно с коэффициентом подобия, равным kA B / AB. Тогда стороны его все станут равны сторонам второго многоугольника, а углы не изменятся. По признаку равенства многоугольников полученный многоугольник будет теперь равен второму данному многоугольнику, а тем самым исходные многоугольники подобны. Еще раз обратим внимание на связь между площадями и периметрами подобных многоугольников. [30]
Страницы: 1 2 3