3.3. Обобщение: отсечение отрезка выпуклым окном
В описанных выше алгоритмах предполагалось, что отсекающее окно является координатно ориентированным прямоугольником. Однако во многих случаях окно не таково. Например, предположим, что прямоугольное окно повернуто относительно системы координат. В этом случае неприменим ни один из ранее описанных алгоритмов.
Для начала рассмотрим отсечение параметрически заданного отрезка прямоугольным окном. Параметрическое уравнение отрезка от Р1 до Р2 имеет вид
P(t) = P1 + (P2 - P1)t 0 <= t <= 1 (3.1)
где t - параметр. Если ограничиться значениями 0 <= t <= 1, то получается именно отрезок, а не бесконечная прямая. Параметрическое описание отрезка не зависит от выбора системы координат. Это свойство делает параметрическое представление особенно полезным для определения пересечения отрезка со стороной произвольного выпуклого многоугольника. Проиллюстрируем этот метод сначала на примере регулярного прямоугольного окна.
В двумерной декартовой системе координат уравнение (3.1) сводится к паре одномерных параметрических уравнений вида:
x(t) = x1 + (х2 - x1)t 0 <= t <= 1 (3.2a)
y(t) = y1 + (y2 - y1)t 0 <= t <= 1 (3.2b)
В случае прямоугольного отсекающего окна одна из координат пересечения отрезка с каждой стороной известна. Нужно вычислить только вторую координату. Из уравнения (3.1) получаем: t = (Р(t) - Р1) / (P2 - P1). А из (3.2) следует, что значения t, соответствующие пересечениям со сторонами окна, равны:
| для левой стороны: t = | хл - х1 x2 - x1 |
0 <= t <= 1 | |
| для правой стороны: t = | хп - х1 x2 - x1 |
0 <= t <= 1 | |
| для нижней стороны: t = | yн - y1 y2 - y1 |
0 <= t <= 1 | |
| для верхней стороны: t = | yв - y1 y2 - y1 |
0 <= t <= 1 |
Здесь через хл, хп, yн, yв обозначены координаты левой, правой, нижней и верхней сторон окна соответственно. Если решения этих уравнений дают значения t за пределами интервала 0 <= t <= 1, то такие решения отвергаются, поскольку они соответствуют точкам, лежащим вне исходного отрезка.
Пример 3.4. Простой частично видимый отрезок.
Рассмотрим частично видимый отрезок от Р1(-3/2,-3/4) до Р2(3/2,1/2), отсекаемый окном с координатами сторон хл, хп, yн, yв, равными (-1,1,-1,1). Имеем значения t для точек пересечения отрезка
| с левой стороной: t = | хл - х1 x2 - x1 |
= | -1 - (-3/2) 3/2 - (-3/2) |
= | 1 6 |
|
| с правой стороны: t = | хп - х1 x2 - x1 |
= | 1 - (-3/2) 3/2 - (-3/2) |
= | 5 6 |
|
| c нижней стороны: t = | yн - y1 y2 - y1 |
= | -1 - (-3/4) 1/2 - (-3/4) |
= | -1 5 |
|
| (это число меньше 0 и поэтому отвергается) | ||||||
| c верхней стороны: t = | yв - y1 y2 - y1 |
= | 1 - (-3/4) 1/2 - (-3/4) |
= | 7 5 |
|
| (это число больше 1 и также отвергается) | ||||||
Видимый участок отрезка заключен в интервале 1/6 <= t <= 5/6.
Значения x и y координат точек пересечения получаются из параметричесикх уравнений. В частности, при t = 1/6 из уравнения (3.2) имеем:
x(1/6) = -3/2 + [3/2 - (-3/2)](1/6) = -1
что, разумеется, априори известно, поскольку х = -1 - это абсцисса левой стороны окна. Для координаты y имеем:
y(1/6) = -3/4 + [1/2 - (-3/4)](l/6) = -13/24
Аналогично при t = 5/6 имеем:
[х(5/6),y(5/6)] = [-3/2,-3/4] + [3/2 - (-3/2,1/2 - (-3/4)](5/6) = [1, 7/24]
Здесь вычисления значений х и y объединены. Опять, поскольку отрезок пересекает правую сторону окна, то координата х априори известна.
После изложенного примера может показаться, что предлагаемый метод прост и естествен. Однако существует ряд трудностей, которые лучше продемонстрировать на следующих примерах.
Пример 3.5. Частично видимый отрезок.
Рассмотрим отрезок от P1(-5/2, -1) до Р2(3/2, 2), а отсекающее окно опять имеет координаты сторон (-1,1,-1,1). Теперь точки пересечения задаются следующими значениями параметра:
tл = 3/8, tп = 7/8, tн = 0, tв = 2/3
и все эти четыре значения принадлежат интервалу 0 <= t <= 1.
Хорошо известно, что если отрезок прямой пересекает выпуклый многоугольник, то возникает не более двух точек пересечения. Следовательно, нужны только два из четырех значений параметра, вычисленных в примере 3.5. Упорядочение этих четырех значений по возрастанию t дает последовательность tн, tл, tв, tп. Искомыми являются значения tл = 3/8 и tв = 2/3, соответствующие точкам пересечения (-1, 1/8) и (1/6, 1). Эти значения совпадают tmaxmin и tminmax. Формальное вычисление этих значений сводится к простой классической задаче линейного программирования.