3. Теперь покажите, что перекрытие имеет место, за исключением случаев, когда гс и td оба меньше нуля или оба больше единицы. Если перекрытие существует, то его концевые точки легко найти по значениям t и t..
с а
4. В заключение по заданным концевым точкам А - (0,6), в - (6,2), С - (3,4) и d - (9,0) определите виды возможных пересечений.
4.6.2. Алгоритм определения пересечения Напишите подпрограмму seglntersectO, которую можно было бы использовать в таком контексте: if(segIntersect(A. В, С. D. InterPt)) <do something> Такая подпрограмма принимает четыре точки, определяющие два отрезка, и возвращает 0, если эти отрезки не пересекаются, и 1, если пересекаются. Если отрезки пересекаются, то расположение точки пересечения помещается в InterPt. Подпрограмма возвращает -1 в случае, если порождающие прямые идентичны.
4.6.3. Тестирование полигона на простоту
Напомним, что полигон Р является простым, если в нем нет пересечений ребер, за исключением концевых точек смежных ребер. Напишите подпрограмму int isSimple(Polygon Р), которая решает задачу «в лоб»: проверяет, пересекаются ли какие-нибудь пары ребер, заданные списком вершин полигона, п возвращает 0, если это так, и 1, если нет. (Polygon - это соответствующий класс для описания полигона.) Это простой, но не самый эффективный алгоритм. (Более сложные проверки со специальной сортировкой ребер по х и по у описаны в [Moret, 142] и [Preparata, 172].)
Векторные инструменты для графики
4.6.4. Пересечения отрезков прямых
Для каждой из следующих пар отрезков АВ и CD определите, пересекаются ли они, и если да, то где:
1. А - (1,4), В- (7,1/2), С - (7/2,5/2), D = (7,5).
2. А = (1,4), В - (7,1/2), С - (5,0), D = (0,7).
3. Л = (0, 7), В - (7,0), С - (8, -1), D = (10, -3).
4.6.1. Приложение пересечения прямых: окружность, проходящая через три заданные точки Предположим, что дизайнер хочет иметь инструмент для рисования единственной окружности, проходящей через три заданные точки. Пользователь задает мышью на дисплее три точки А, В и С, например, как на рис. 4.34, а, и окружность рисуется автоматически, как показано на рис. 4.34, б. Единственная окружность, проходящая через три точки, носит название описанной окружности (circumscribed circle), или вневписанной окружности (excircle), около треугольника, определяемого этими точками. Что это за окружность? Нам необходима подпрограмма, которая может вычислять ее центр и радиус.