14. Отсечение. Алгоритм разбиения средней точкой при отсечении отрезка. - p1xelse/CG GitHub Wiki

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

- для x и y

Необходимо задавать точность, которой будем задавать точку пересечения EPS (максимальная точность - корень из двух).

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

Пример

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

Мы должны определить интервал, в котором располагается искомое решение (P1P2)

Ищем Pср, если часть отрезка становится невидимой, то ее отбрасываем

После того, как 1 точка пересечения будет найдена, поменяем местами 1ую вершину и найденную точку пересечения и будем искать аналогичным образом 2ую точку пересечния.

Как будут определяться полностью невидимые отрезки, которые не являются тривиально невидимыми?

Найдем Рср1, отрезок РсрР4 не будет распознан, как полностью невидимый, продолжим с ним работу, ищем опять Рср2, нижняя часть отрезка-тривиально невидимая, вершина Р4 переезжает в Рср2 и так далее. Подводя итог, в процессе разбиения отрезка, либо мы убеждаемся в том, что части отрезка становятся невидимыми, либо может сложиться ситуация, когда отрезок стянется в точку и тогда нужно будет определить видимость/невидимость этой точки.

Описание алгоритма

Точка пересечения находится не аналитически, а численными методом

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