X-PDF

Взаимное расположение двух отрезков

Поделиться статьей

 

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

 

Предположим, что концевые точки одного из отрезков имеют координаты (х11) и (х22), а концевые точки другого — (х33) и (х44). Пусть общее уравнение первой прямой, проходя­щей через точки (х11) и (х22) имеет вид А1x + B1y+C1 = 0, а уравнение второй прямой, проходящей через точки (х33) и (х44), выглядит так: А2x + B2y+C2 = 0,

 

 

 

Определим расположение точек (х33) и (х44) относительно первой прямой. Если они расположены по одну сторону от прямой, то отрезки не могут пересекать­ся. Аналогично можно определить положение точек (х11) и (х22) относительно другой прямой.

Таким образом,
отрезки пересекаются, если значения пары выражений Z11x3 + B1y3+C1 и Z21x4 + B1y4+C1 разные знаки или Z1*Z2=0, а также пары Z3= А2x1+ B2y1+C2 и Z4= А2x2+ B2y2+C2 имеют разные знаки или Z3*Z4=0.

отрезки не пересекаются, если значения пар выражений Z1 и Z2 или Z3 и Z4 имеют одинаковые знаки.

 

Приведенный выше алгоритм не учитывает крайней ситуации, когда два отрезка лежат на одной прямой:

Представленная информация была полезной?
ДА
59%
НЕТ
41%
Проголосовало: 778

(x3-x1)(y2-y1)-(y3-y1)(x2-x1)=0 и (x4-x1)(y2-y1)-(y4-y1)(x2-x1)=0

 

На рис.4 отрезки, лежащие на одной прямой, не пересекаются, а на рис. 5 — пересекаются.

Для того чтобы определить взаимное расположение таких отрезков, поступим следующим образом. Обозначим k1 = min (x1 . х2) . k2 = max(x1 . x2) . k3 = min(x3 . x4) . k4 = max(x3 . x4).

Здесь k1 является левой, a k2 — правой точкой проекции первого отрезка (отрезка, заданного координатами (x1 .y1), (x2 . у2)) на ось Ох. Аналогично k3 является левой, и k4 — правой точкой проекции второго отрезка (отрезка, заданного координатами (x3 .y3), (x4 . у4)) на ось Ох. Ана­логично ищем проекции на ось Оу.

 

Отрезки, лежащие на одной прямой, будут пере­секаться тогда, когда их проекции на каждую ось пересекаются. Следует заметить, что если проек­ции двух произвольных отрезков пересекаются, то это не значит, что и сами отрезки пересека­ются, что видно на ри­сунке.

 

Для определения взаимного расположения проекций на ось Ох воспользуемся следующим фактом (см. рис. 4 и 5): координата левой точки пересечения проекций Lx равна max(k1 . k3), т. е. максимальной из координат левых точек проекций. Рассуждая аналогично для пра­вых точек проекций, получим, что координата правой точки Rx пересечения равна min (k2, k4). Для того чтобы отрезки пересекались, необходимо, чтобы левая коорди­ната пересечения проекций была не больше правой координаты пересечения отрезков (такой случай имеет место на рис. 4, когда Lx = x3, a Rx = x2). Поэтому услови­ем пересечения проекций является выполнение нера­венства Lx&lt .=Rx.

Аналогично можно вычислить величины Ly и Ry, взяв соответствующие проекции на ось Оу.

Следует отметить, что длина пересечения проекций в этом случае равна величине Rx — Lx (если Rx — Lx = 0, то проекции имеют только общую точку).

 


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
59%
НЕТ
41%
Проголосовало: 778

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

Поделиться статьейЭтические проблемы современной науки являются чрезвычайно актуальными и значимыми. В связи с экспоненциальным ростом той силы, которая попадает в


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

Поделиться статьейВключает 30 родов, около 1000 видов. Распространение: горные и умеренные области Северного полушария . многие виды произрастают в горах


Поделиться статьей

Вопрос 1. Понятие цены, функции и виды. Порядок ценообразования

Поделиться статьей

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


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет