15.2. РАЗРЕЗАНИЕ ПРОИЗВОЛЬНОГО ОТРЕЗКА ПРЯМОЙ ПРОИЗВОЛЬНЫМ ВЫПУКЛЫМ МНОГОУГОЛЬНИКОМ

Задача, обозначенная в названии данного раздела, характеризуется промежуточной степенью общности — крайние случаи соответствуют разрезанию произвольной прямой произвольным правильным прямоугольником (см. разд. 15.3) и разрезанию произвольной прямой произвольным невыпуклым многоугольником.

Задача. Если — вершины выпуклого плоского многоугольника П, требуется определить, какая часть отрезка прямой (заданного концевыми точками лежит внутри этого многоугольника.

Заметим, что «очевидное» решение, предусматривающее проверку принадлежности точек внутренней части многоугольника, неприемлемо, поскольку отрезок прямой может пересекать выпуклый многоугольник даже в том случае, если обе концевые точки отрезка лежат за пределами многоугольника. Допустимым является следующее решение, в основе которого лежат результаты разд. 14.4.

Вначале вычисляются значений величины

где — вектор координат вершины многоугольника и — вектор координат концевых точек прямой Полученные результаты могут соответствовать одному из следующих случаев.

1. Все значения — ненулевые и имеют один и тот же знак. Следовательно, все вершины многоугольника расположены по ну сторону отрезка прямой и никакая часть прямой не заключе на внутри многоугольника.

2. Одно из значений равно 0, а все остальные значения имеют один и тот же знак. Следовательно, прямая проходит через одну из вершин многоугольника, а все остальные его вершины расположены по одну сторону этой прямой. Данный случай вивалентен случаю 1.

3. Два значения равны 0, а все остальные значения имеют один и тот же знак. Поскольку многоугольник П — выпуклый, это может означать лишь то, что две соседние вершины много угольника лежат на отрезке прямой Следовательно, это — вы рожденный случай, рассмотренный в подразд. 14.4.2: одна из сторон многоугольника расположена на той же прямой, что и отрезок прямой

4. Одно или два значения равны 0, а остальные значения имеют разные знаки. Следовательно, отрезок прямой пересека многоугольник П, проходя через одну или две его вершины. Поскольку многоугольник П — выпуклый, знаки изменяются лишь дважды. Этот случай будет рассматриваться вместе со следующим.

5. Все имеют ненулевые значения и знаки их различны. Это означает, что при обходе многоугольника по периметру знак из меняется дважды. Для обозначения пар вершин, на которых про исходит перемена знака, будут использоваться символы . В случае 4 величина может принимать ненулевое значение в одной из вершин одной или обеих пар. Отрезок прямой, соединяющий вершины первой пары, обозначается через , а отрезок прямой, соединяющий вершины второй пары, — через Отметим, что не имеет значения, какая пара назначается пер вой, а какая — второй; то же самое относится к соответствующим обозначениям, если принятая процедура обработки точно выпол няется.

После установления пересечения прямой, содержащей отрезок рассматриваемого многоугольника (два последних случая), необходимо определить расположение точек относительно отрезков прямых т. е. знаки следующих четырех величин:

(расположение точки относительно отрезка прямой

(расположение точки относительно отрезка прямой

(расположение точки относительно отрезка прямой

(расположение точки относительно отрезка прямой ).

Рис. 15.1. (см. скан) Шесть возможных вариантов разрезания произвольного отрезка прямой произвольным многоугольником

При упорядочении ориентации сторон многоугольника по часовой стрелке величина имеет в уравнении (15.2) отрицательный знак, если точка лежит внутри многоугольника Значение равно О, если одна из точек лежит на одной из сторон многоугольника. Мы не будем рассматривать здесь этот вырожденный случай и предлагаем провести соответствующую модификацию алгоритма 15.1 в качестве упражнения (см. задачу 15.1). На рис. 15.1 приведены различные варианты расположения точек относительно двух прямых, а табл. 15.1 содержит знаки и результаты определения концевых точек воспроизводимого отрезка. В табл. 15 1 и алгоритме 15.1 используются следующие обозначения: концевые точки отрезка прямой, изображение которого должно быть воспроизведено; точка пересечения отрезков и

Таблица 15.1. (см. скан) Расположение произвольного отрезка прямой относительно произвольного многоугольника

Теоретически имеется 16 невырожденных вариантов (число различных наборов знаков у четырех переменных), однако в силу геометрических ограничений в действительности возможны лишь 9 случаев. В самом деле, невозможно, чтобы все значения были положительными, так как положительные полуплоскости для двух сторон расположены вне многоугольника. Аналогичным образом, невозможно, чтобы три имели положительные знаки. В результате остается 11 вариантов. Конфигурация означает, что точка находится внутри многоугольника, а точка расположена выше прямой и ниже прямой что невозможно. Аналогичным образом можно интерпретировать конфигурацию . В результате остается 9 вариантов, сведенных в табл. 15.1. Отметим, что, обращаясь к реальным геометрическим построениям, мы обнаруживаем лишь 6 случаев, которые представлены на рис. 15.1. Три из них можно маркировать двумя допустимыми способами — это случаи, представленные на рис. 15.1,б-г (второй вариант маркировки дан в скобках). Если допустить, что точка расположена ниже точки , то можно

ограничиться рассмотрением лишь 6 случаев, однако это допущение не следует принимать, когда является стороной многоугольника и упорядочение концевых точек не определяется значениями их координаты у.

Алгоритм 15.1 определяет знаки величин, задаваемых уравнениями (15.1) и (15.2), и использует решения, перечисленные в табл. 15.1. Первая часть алгоритма обеспечивает определение расположения прямой относительно вершин прямоугольника, а вторая часть — определение расположения концевых точек прямой. Переменным и присваиваются значения, соответствующие знакам соседних вершин многочлена которые находятся из уравнения (15.1). Если значения и и неодинаковые, то значит, две соответствующие вершины расположены с противоположных сторон прямой, содержащей отрезок Координаты таких вершин запоминаются на шаге 5, К — счетчик числа таких пересечений. Поскольку предполагается, что многоугольник выпуклый, их число может быть равно 0 или 2. Если по окончании цикла, включающего шаги 3—6, оказывается, что это число равно 0, то это означает отсутствие пересечения прямой, содержащей отрезок и многоугольника, и выполнение алгоритма прекращается (шаг 7). В противном случае осуществляются шаги 8—17.

На шаге 9 вычисляются значения величин, определяемых уравнениями (15.2), и на остальных шагах выполняются тесты, предусмотренные табл. 15.1. Случаи а) и д) — отрезок прямой лежит вне многоугольника — исследуются на шаге 10. Если условие, проверяемое на шаге 10, не выполняется, то обратившись к рис. 15 1 и табл. 15.1, можно установить, что при противоположных знаках прямая пересекает один из отрезков Аналогичным образом интерпретируется противоположность знаков Проверка этих условий проводится на шагах 14 и 15: сначала для затем для

Исходя из принципа двойственности, алгоритм разрезания можно использовать и для решения следующей задачи.

Задача. Задано прямых, являющихся сторонами выпуклого многоугольника. Требуется определить, лежит ли внутри этого многоугольника точка, заданная пересечением двух прямых.

Решение. Примените алгоритм, двойственный алгоритму 15.1.

Алгоритм 15.1. Разрезание произвольного отрезка прямой произвольным выпуклым многоугольником

Обозначения. Массив А имеет размерность и содержит тройки значений однородных координат вершин многоугольника. Координаты концевых точек отрезка прямой хранятся в массиве Р размерностью Размерности массивов В и С равны . Массив В используется для хранения первой из пары вершин, расположенных по разные стороны прямой, содержащей отрезок массив С содержит вторую вершину таких пар. определяются уравнениями (15.1), (15.2).

Алгоритм определяет концевые точки отрезка, расположенного внутри многоугольника.

(см. скан)