14. Отсечение. Алгоритм разбиения средней точкой при отсечении отрезка. - chrislvt/CG GitHub Wiki
Принципиальное отличие от предыдущих алгоритмов - точка пересечения находится бинарным поиском. В данном алгоритме используется численный метод уточнения корня уравнения для нахождения точки пресечения отрезка с границей отсекателя.
- для x и y
Необходимо задавать точность, которой будем задавать точку пересечения EPS (максимальная точность - корень из двух).
Поиск точки пересечения выполняется как уточнение корня уравнения методом деления отрезка пополам. Можно задачу трактовать по-другому: нахождение самой далеко расположенной от вершины Р1, но еще видимой точки(допустим , ищем точку пересечения , ближнюю к Р2)
Пример
Договариваемся неизменной считать точку Р1 и искать каждый раз наиболее далеко расположенную от 1ой вершины точку отрезка, но еще видимую
Мы должны определить интервал, в котором располагается искомое решение (P1P2)
Ищем Pср, если часть отрезка становится невидимой, то ее отбрасываем
После того, как 1 точка пересечения будет найдена, поменяем местами 1ую вершину и найденную точку пересечения и будем искать аналогичным образом 2ую точку пересечния.
Как будут определяться полностью невидимые отрезки, которые не являются тривиально невидимыми?
Найдем Рср1, отрезок РсрР4 не будет распознан, как полностью невидимый, продолжим с ним работу, ищем опять Рср2, нижняя часть отрезка-тривиально невидимая, вершина Р4 переезжает в Рср2 и так далее. Подводя итог, в процессе разбиения отрезка, либо мы убеждаемся в том, что части отрезка становятся невидимыми, либо может сложиться ситуация, когда отрезок стянется в точку и тогда нужно будет определить видимость/невидимость этой точки.
Описание алгоритма
Точка пересечения находится не аналитически, а численными методом
Стоит отметить, что быстродействие будет при реализации лишь на аппаратном уровне (т.к. деление на 2 на аппаратном уровне может быть реализовано с помощью побитового сдвига вправо, что гораздо быстрее обычного деления)