Естественные науки

О пересечении отрезков

Даны декартовы координаты концов отрезков АВ и СD. Требуется определить, по возможности простым способом, пересекаются ли они, не прибегая при этом ни к черчению графиков на координатной системе, ни к совместному решению уравнений соответствующих прямых.
Камшат Мейрамбеккызы
Камшат Мейрамбеккызы
85 855
Я б тут тоже не стал с Муму сексом заниматься. Первым делом подмывает, конечно, загуглить классический алгоритм, но я просто помню, что для этой конкретной задачи быстрее его самому придумать)

Достаточно проверить, что концы одного лежат в разных полуплоскостях отн. другого и наоборот.

Берем уравнение прямой, проходящей через две точки, меняем в нем деление на умножение по правилу пропорции (благо случай всего лишь двумерен) и смотрим, что получилось со знаками...
НС
Нурис Сыздыков
34 449
Лучший ответ
Камшат Мейрамбеккызы Вот именно: Вершины одного отрезка должны лежать на разных п/плоскостях другого, или, что одно и то же, 4-хугольник ACBD (а не ABCD!) должен быть выпуклым.
Я до сих пор не понимаю, как это в дополнении неравенства печатал половинчатыми. Должно быть:
Условия пересечения: если (уС-уА) /(хС-хА) >= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) <= (yB-yD)/(xB-xD);
и наоборот, если (уС-уА) /(хС-хА) <= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) >= (yB-yD)/(xB-xD)
Отрезки - не прямые, они пересекаются только в определенном инервале.
Условия пересечения отрезков a(ax1;ay1;ax2;ay2) и b(bx1;by1;bx2;by2) примерно такие:

bx1< ax1< bx2 или ax1< bx2 < ax2
signum(ay1-by1) ≠ signum(ay2-by2)

Если отрезки совпадают, может быть signum(ay1-by1) = signum(ay2-by2) = 0

Вертикальные отрезки я тут не расматривал, если они не взаимоортогональны, можно просто повернуть всю систему.
Татьяна Анфалова
Татьяна Анфалова
89 325
Камшат Мейрамбеккызы Постараюсь проверить завтра
Камшат Мейрамбеккызы Для отрезков а (2, 2, 6, 5) и b(0, 3, 4, 4) все вроде ваши неравенства соблюдаются, но тем не менее отрезки не пересекаются.
Камшат Мейрамбеккызы Ой, какая ерунда вышла в дополнении! Неужели я так напечатал? Должно быть:
Условия пересечения: если (уС-уА) /(хС-хА) >= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) <= (yB-yD)/(xB-xD);
и наоборот, если (уС-уА) /(хС-хА) <= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) >= (yB-yD)/(xB-xD).
То есть не выражая математические объекты ни графически, ни математически? А как тогда, изобразить их в танце? Это как просить спеть песню не прибегая к звукам.
ДМ
Дарья Михалап
55 037
Камшат Мейрамбеккызы Я написал не "ни математически", а "по возможности простым способом, не решая систему уравнений прямых...". А решение системы, можете сами убедиться, даёт довольно сложное выражение. Притом ещё потребуется выяснить, расположена ли точка пересечения на самих отрезках или на их продолжениях. А вроде можно найти простые соотношения между упомянутыми координатами.
Камшат Мейрамбеккызы Ой, какая ерунда вышла в дополнении! Неужели я так напечатал? Должно быть:
Условия пересечения: если (уС-уА) /(хС-хА) >= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) <= (yB-yD)/(xB-xD);
и наоборот, если (уС-уА) /(хС-хА) <= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) >= (yB-yD)/(xB-xD).
|AB| + |CD| > |AC| + |BD| вроде должно быть условием пересечения AB c CD.
Улжан Нургалиева
Улжан Нургалиева
68 663
Камшат Мейрамбеккызы Вроде не удовлетворяет для А (0; 3), В (3; 0), С (2; 2), D(3, 3)
Отрезки задают пряугольники со сторонами || осям.
1. Если прямоугольники (по координатам) не пересекаются, то и отрезки не пересекаются.
2. Дальнейший анализ - неск способами только области пересечения прямоугольников. Без труда можно самому алгоритмы составить.
При становлении машинной графики было интересно. Инж дисциплина есть, где такие задачи рассмотрены, "Вычислительная геометрия".
Таня Назарова
Таня Назарова
87 724
Камшат Мейрамбеккызы "Отрезки задают пряугольники со сторонами || осям". Не понял. Вот отрезки АВ: А (0; 3) - В (3; 1) и СЕ: С (1; 0) - Е (2; 2,5). О каких прямоугольниках речь? И как узнать, пересекаются ли они, не прибегая к черчению, что и указано в условиях вопроса?
Камшат Мейрамбеккызы Ой, какая ерунда вышла в дополнении! Неужели я так напечатал? Должно быть:
Условия пересечения: если (уС-уА) /(хС-хА) >= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) <= (yB-yD)/(xB-xD);
и наоборот, если (уС-уА) /(хС-хА) <= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) >= (yB-yD)/(xB-xD).
Если мне не изменяет память, есть классическое решение через произведение векторов, которое, к тому же, дает координаты точки пересечения. Давно это было, сперва сам изобретал велосипед, потом подглядел красоту в книжке по компьютерной графике.
Николай Нестеров
Николай Нестеров
75 704
нуу техническиесли координаты одной из осей не меняются например: (1,1/,1,2/,1,3/,1,4 и тд и хоть 6,1,6/,2,6/,3,6,4/ и тд по той же оси
Жанболат Каналин
Жанболат Каналин
56 954
Камшат Мейрамбеккызы Ой, какая ерунда вышла в дополнении! Неужели я так напечатал? Должно быть:
Условия пересечения: если (уС-уА) /(хС-хА) >= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) <= (yB-yD)/(xB-xD);
и наоборот, если (уС-уА) /(хС-хА) <= (yB-yC)/(xB-xC), то д. б. (уD-уА) /(хD-хА) >= (yB-yD)/(xB-xD).

Похожие вопросы