14. Отсечение. Алгоритм разбиения средней точкой при отсечении отрезка.

Отсечение

См тут

Алгоритм разбиения средней точкой

• Отличие в том, что точка пересечения находится не аналитически, а фактически определяется численным методом (используется метод уточнения корня уравнения - деление отрезка пополам).
• Pср = (P1 + P2) / 2.
• Необходимо задавать точность epsilon.

Нахождение точки пересечения отрезка с границей отсекателя, можно рассматривать как нахождение самой удаленной, но ещё видимой точки. Можем сразу определить интервал, где лежит исходный корень уравнения

• Ищем Pср, если часть отрезка невидима - то отбрасываем, таким образом находим точку первую пересечения
• После того, как нашли первую точку пересечения, на первую вершину ставим точку пересечния, на вторую - оставшуюся вершину. Аналогично находим вторую точку пересечения.
• Целесообразно проанализировать видимость второй точки. Если она видима, то одна вершина найдена. Значит надо искать только второе пересечение.

Идентификация невидимых отрезков

Отрезок (P3 - P4) нельзя отбросить, как тривиально невидимый, сразу (хотя он полностью невидимый), потому что с помощью подсчёта суммы кодов отрезка можно отбросить только отрезки, у которых обе вершины находятся по невидимую сторону относительно одной из граней. Однако после первого деления на 2 части получится, что одна часть невидима относительно левой стороны, а другая - относительно нижней. На этом шаге уже можно будет отбросить обе части отрезка, как тривиально невидимые (и соответственно признать, что и сам отрезок целиком является тривиально невидимым)

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

Оценка эффективности

Сам по себе алгоритм простой.
Но! Весь процесс итерационный, и он может заятнуться.
Почему алгоритм имеет право на жизнь?
Середину отрезка мы находим делением на два, а это быстро в ЭВМ. Поэтому алгоритм будет работать быстро, даже если и уступит первым алгоритмам, то ненамного. 8 Куровых из 10

Псевдокод

1. Ввод P1, P2, Хл, Хп, Yн, Yв, eps
2. I = 1
3. Формирование кодов концов отрезка, сумм кодов концов отрезка
4. Если S1 = 0, S2 = 0, то визуализация отрезка и переход в конец.
5. Вычисление произведения кодов концов отрезка
6. Если P != 0, то переходим в конец
7. R = P1.
8. Если I > 2, то проверить произведение кодов концов отрезка
     если произведение = 0, отрезок видимый, иначе невидимый, i = i + 1, переход к п. 3.
9. если S2 = 0, то одна точка пересечения найдена, то P1 = P2, P2 = R
     i = i + 1
     переход к п. 3
10. Если |p2 - p1| > eps, то 
    Pcp = (P1 + P2) / 2, T = P1, P1 = Pср
    Определение кодов конца отрезка и вычисление логического произведения
    Если P != 0, P1 = T, P2 = Pср. Повторить этот же пункт
11. Одна вершина найдена. P1 = P2, P2 = R, i = i+ 1Ю, переход к п.3.
12. Конец.

Следующий вопрос: 15. Отсечение. Алгоритм Кируса Бека отсечения отрезка.

Предыдущий вопрос: 13. Отсечение. Алгоритм Сазерленда Коэна отсечения отрезка.