Отсечение плоских фигур
Рассмотрим задачу об отсечении произвольного многоугольника по границе заданного выпуклого многоугольника (рис.8.3). Алгоритм сводит основную задачу к серии более простых задач об отсечении многоугольника вдоль прямой, проходящей через одно из ребер отсекающего многоугольника.
Рис.8.3. Алгоритм отсечения плоских фигур На каждом шаге выбираем очередное (рис. 8.4) ребро отсекающего многоугольника (ребра с цифрами). Предварительно необходимо договориться о направлении обхода вершин отсекаемого многоугольника (по часовой стрелке или против неё). После этого поочередно проверяется положение всех вершин данного многоугольника относительно прямой, проходящей через выбранное текущее ребро. При этом в результирующий многоугольник добавляется 0, 1 или 2 вершины.
Рис. 8.4. Пошаговое выполнение алгоритма
При последовательном отсечении многоугольника по четырем границам возможны 4 различных ситуации (рис. 8.5). Может также возникнуть вариант, когда ребро совпадает с границей.
Рис. 8.5. Различные случаи алгоритмы
Предположим, что точка S уже обработана, тогда могут произойти следующие случаи. В случае 1: ребро целиком лежит во внутренней области и точка P добавляется в результирующий многоугольник. В случае 2: в результирующий многоугольник добавляется точка пересечения Q. В случае 3: обе вершины лежат во внешней области и поэтому в результирующий многоугольник не добавляется ни одной точки. В случае 4: в результирующий многоугольник добавляются точка пересечения Q и точка P.
|
