Забележка. Това е един урок със задачите в компютърните науки (раздел алгоритми). Ако трябва да се реши проблема по компютърни науки, което не е тук - пише за него във форума. Най-вероятно неговото решение ще допълни хода с целите на науката.
Задача.
В самолета, двата сегмента са определени от целочислени координати. За да се определи дали те имат обща пресечна точка.
Решение.
За да се определи дали сегменти образуват уравненията на линиите, които принадлежат към определените сегменти пресичат. Ако системата е да отвежда тези уравнения има решение, тези линии имат пресечна точка. Ако точката на пресичане се намира между координатите на точките, принадлежащи към сегментите, сегментите пресичат.
Наименования.
1 означават като сегмент AB и да има координира (х1, у1) B (х2; y2)
Сегментът 2 е обозначен като CD и да има координатите C (х 3; Y 3) В (х4; У4)
Ако не - тогава сменяте двойката сегменти координати.
Етап 6. Проверете сегментите паралелно.
Ако k1 = k2. линии са успоредни и сегментите не могат да се пресичат. Решение стоп.
Ако линиите се пресичат точка,
k1 х + b1 = k2 х + b2
Етап 9 .Uchtem че точката на пресичане на линиите може да лежи извън сегменти, принадлежащи към тези линии. Така, ако сегментите пресичат, защото
x1 ≤ х2; x3 ≤ x4;
условия трябва да бъдат изпълнени:
x1 ≤ x4 и x4 ≤ x2
или
x1 ≤ x3 и x3 ≤ x2
Ако едно от двете условия е вярно, сегментите имат точка на пресичане, или - сегментите не се припокриват.
Свързани статии