Отсечения отрезка выпуклым многоугольником

 

Та часть отрезков, которая не была выявлена как видимая или невидимая, подвергается анализу общим алгоритмом задачи отсечения. Общий алгоритм решения задачи отсечения базируется на определении точки пересечения отрезка Р₁Р₂, для которого решается эта задача, с ребром многоугольника. С этой целью определим положение всех вершин многоугольника относительно прямой, продолжающей отрезок Р₁Р₂, путем вычисления следующих определителей третьего порядка

S_i = | A_i Р₁ Р₂ |, I = 1, 2,..., n.

Значения n определителей S_i могут быть больше, меньше нуля или равны ему. Все возможные сочетания этих значений разобьем на два случая.

Первый случай: все значения определителей S_i имеют один знак или равны нулю, т.е. вершины расположены по одну сторону отрезка Р₁Р₂ или лежат на нем. При этом возможны следующие варианты.

Вариант 1. Все значения S_i не равны нулю (S_i 0) - отрезок полностью невидим (все вершины расположены по одну сторону отрезка и не соприкасаются с ним).

Вариант 2. Одно значение определителя S_i равно нулю (S_i = 0) - прямая, продолжающая отрезок Р₁Р₂, проходит через вершину A_i. В этом случае надо решить задачу принадлежности этой вершины отрезку Р₁Р₂ путем определения принадлежности вершины A_i внутренней области регулярного окна в виде прямоугольника, построенного на диагонали Р₁Р₂. Если она принадлежит отрезку, то у этого отрезка видимой является только точка A_i.

Вариант 3. Два значения определителя равны нулю (S_i = 0 и S_j = 0) - прямая, продолжающая отрезок Р₁Р₂, совпадает с гранью ребра A_iA_j. Здесь необходимо исследовать взаимное расположение отрезка Р₁Р₂ и ребра A_iA_j. При этом возможны варианты полной видимости отрезка, когда

x_min (P₁Р₂) > x_min (A_iA_j) и x_max (P₁Р₂) < x_max (A_iA_j),

а также полной невидимости, когда либо

x_max (P₁Р₂) < x_min (A_iA_j),

либо

x_min (P₁Р₂) > x_max (A_iA_j).

В случае выполнения равенства, в приведенных выше условиях, будет видна только одна точка отрезка P₁Р₂ - точка P₂ = A_i или точка P₁ = A_j соответственно. Кроме этого, возможны и частичные перекрытия отрезков, что можно выяснить аналогичными сравнениями координат. Причем здесь приведен анализ точек по координатам x. Но можно выполнить исследования и по координатам y.

Второй случай: определители S_i имеют разные знаки, т.е. прямая, продолжающая отрезок P₁Р₂, пересекает многоугольник. При этом пересечение возможно только в двух точках. Так как многоугольник выпуклый, то при последовательном обходе его вершин знаки определителей S_i могут менять свое значение на противоположное только два раза. Пусть эта смена знака происходит для смежных пар вершин A_j и A_{j +1}, A_k и A_k+1 (рис. 3.8).

Для определения видимой части отрезка P₁Р₂ необходимо определить положение точек P₁ и Р₂ относительно отрезков A_jA_{j +1}, A_kA_k+1. Для этого требуется выполнить анализ четырех определителей при обходе ребер многоугольника по часовой стрелке:

S_1j = | P₁ A_j A_j+1 |, S_2j = | P₂ A_j A_j+1 |,

 

S_1k = | P₁ A_k A_k+1 |, S_2k = | P₂ A_k A_k+1 |.

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

Рассмотрение всех возможных сочетаний значений этих определителей дает 64 варианта (4³). Исключение случая нахождения концевой точки отрезка на одном из ребер многоугольника существенно уменьшает число вариантов до 16. Однако практически достаточно рассмотреть только четыре из них. Рассмотрим эти варианты.

Вариант 1. Отрезок лежит вне многоугольника. В этом случае он полностью невидим. Данное расположение отрезка соответствует следующим сочетаниям знаков определителей:

	S1j	S1k	S2j	S2k
Вариант 1.1.	+	-	+	-
Вариант 1.2.	-	+	-	+

Эти варианты показаны на рис. 3.9. Вариант 1.1 соответствует положению отрезка слева от многоугольника, а 1.2 - справа. Следует отметить, что ориентация отрезка на противоположное не влияет на результат его невидимости.

Вариант 2. Отрезок лежит полностью внутри многоугольника. В этом случае отрезок является полностью видимым (рис. 3.10.)

Знаки определителей будут иметь следующий вид:

 

	S1j	S1k	S2j	S2k
Вариант 2.1.	-	-	-	-

Вариант 3. Точки P₁, Р₂ лежат по разные стороны многоугольника. В этом случае отрезок является частично видимым. Поэтому следует определить две точки пересечения отрезка с ребрами многоугольника. Видимая часть отрезка будет находиться между ними (рис. 3.11).

Знаки определителей для этого случая приводятся ниже. При этом изменение ориентации отрезка на противоположный дает такое же изменение знаков.

 

	S1j	S1k	S2j	S2k
Вариант 3.1.	+	-	-	+
Вариант 3.2.	-	+	+	-

 

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

Знаки определителей для этих случаев имеют следующий вид:

	S1j	S1k	S2j	S2k
Вариант 4.1.	-	+	-	-
Вариант 4.2.	+	-	-	-
Вариант 4.3.	-	-	-	+
Вариант 4.4.	-	-	+	-

В соответствии с рассмотренными вариантами можно построить общий алгоритм определения видимой части отрезка.