Задача 21.
Даны N, N>1, прямоугольников, для которых предполагается, что:
А). Стороны любого прямоугольника параллельны координатным осям и прямоугольник задается концами одной из диагоналей.
В). Каждый прямоугольник имеет общие внутренние точки с хотя бы одним из остальных и не имеет общих вершин, сторон или частей сторон ни с одним из остальных прямоугольников.
Составить программу, которая решает следующие задачи:
1. С помощью последовательности точек определить внешний контур фигуры F, являющейся объединением прямоугольников - ломаную замкнутую кривую. Пример на чертеже.
2. Определить содержит ли фигура F "дырки" ,т.е. замкнутые фигуры, которые ей не принадлежат.
3. Разложить фигуру на наименьшее возможное число не пересекающихся прямоугольников, которые могут иметь общие стороны или части сторон , а их объединение дает фигуру F.
4. Вычислить периметр и площадь фигуры F.
Примечание.
1. Задачи 3,4 решаются только для фигур, которые не содержат "дырки".
2. Полное решение содержит:
-анализ (обоснование) решения
-текст программы с соответствующими комментариями
-выполнение текстового примера, который будет дан при приемке работы
Объединение прямоугольников Ai Bi Ci Di,i=1,2,3,4 есть
фигура F=A2 B2 X1 B1 X2 B4 C4 D4 X3 X4 C2 D2
фигура F содержит единственную "дырку" PQRS
|
Решение задачи 21.
Припишем сторонам каждого из N прямоугольников ориентацию: левая сторона считается идущей снизу вверх (ориентацию обозначим 1), верхняя - слева направо (2), правая - сверху вниз (3), нижняя - слева направо (ориентация 4). Найдем точки пересечения N прямоугольников. Обозначим это множество точек S. Добавим в S угловые точки всех прямоугольников. Каждой из точек S припишем пару, состоящую из двух ориентаций, соответствующих ориентациям тех ребер, пересечением которых точка является.
Найдем в множестве S точку с максимальной ординатой. Так как таких точек несколько, то возьмем среди них точку P0 с минимальной абсциссой. Эта точка лежит на верхней части контура объединения прямоугольников и является левым верхним углом какого-то прямоугольника. Печатаем P0. Будем двигаться от P0 вниз по ребру, пока не встретим одну из точек S (это будет либо точка - угол прямоугольника, либо точка - пересечение сторон). Обозначим эту точку P1. Ей приписана пара ориентаций (O1,O2), одна из ориентаций (пусть, например, O1) есть 3 (это то ребро, по которому мы пришли в P1). Печатаем P1 - очередную вершину контура, и двигаемся из точки P1 (по ребру какого-то прямоугольника) в направлении O2, пока не достигнем еще какой-нибудь вершины из S. Обозначим ее P2. У нее пара ориентаций (O1',O2'). Пусть, например, O2'=O2, тогда мы из очередной вершины контура P2 будем двигаться в направлении O1', и т.д., пока не достигнем вершины P0. Контур выписан.
Определим, есть ли в контуре "дырки". Занесем в массив A[1..2,1..2*N] в строку 1 все ординаты вершин прямоугольников без повторений и отсортируем этот массив по первой строке по возрастанию. Предположим, что в массиве A хранится всего S различных ординат: A[1,1], ... ,A[1,s]. Сначала все A[2,i]=0, i=1, ... , s.
Определим массив B[1..4,1..N]. В первой строке массива B располагаются в порядке неубывания x - координаты левых нижних и правых верхних вершин всех N прямоугольников:
B[1,i] - x - координата какой-то вершины P
B[2,i] и B[3,i] соответственно - ординаты нижней и верхней вершин той вертикальной стороны прямоугольника, на которой лежит P.
B[4,i]=0, если эта вертикальная сторона прямоугольника левая и 1, если правая.
Воспользуемся методом сканирующей прямой:
Будем брать по возрастанию индекса i элементы B[1,i] массива B, и увеличивать на 1 все элементы A[2,j] такие, что
B[2,i]<=A[1,j]<B[3,i] (A[2,j] будет равно количеству прямоугольни-
ков, содержащих внутри себя или на границе отрезок A[1,j]<=y<=A[2,j], x=B[1,i]). Если какое-то A[2,j]=0, то это означает, что прямоугольники при x=B[1,i] не покрывают интервал y=(A[1,j],A[1,j+1]).
Если мы найдем такие i,l и k, что при x=B[1,i] интервал (A[1,l],A[1,k+1]) не покрыт многоугольниками (т.е. A[2,l] = = A[2,l+1] = ... = A[2,k]=0), а интервалы (A[1,l-1], A[1,l]) и (A[1,k+1],A[1,k+2]) покрыты (т.е. A[2,l-1]>0 и A[2,k+1]>0), и точка (x,y)=(B[1,i],A[1,l]) не принадлежит внешнему контуру фигуры объединения прямоугольников, то у фигуры есть по крайней мере одна дырка. Чтобы, при необходимости, выписать контур дырки, поступим как и в случае нахождения внешнего контура - пойдем по ребрам, образующим контур.
Пункт 3 задачи решается перебором.
Для решения пункта 4 см. задачу 5.
|
