Пересечение отрезков 2 класс

Как найти точку пересечения отрезков

добавлено: 11 Jun 2008 10:22
редактировано: 20 Jun 2011 1:15

Пересечение двух отрезков

Даны два отрезка и (они могут вырождаться в точки). Требуется найти их пересечение: оно может быть пустым (если отрезки не пересекаются), может быть одной точкой, и может быть целым отрезком (если отрезки накладываются друг на друга).

Алгоритм

Работать с отрезками будем как с прямыми: построим по двум отрезкам уравнения их прямых, проверим, не параллельны ли прямые. Если прямые не параллельны, то всё просто: находим их точку пересечения и проверяем, что она принадлежит обоим отрезкам (для этого достаточно проверить, что точка принадлежит каждому отрезку в проекции на ось и на ось по отдельности). В итоге в этом случае ответом будет либо "пусто", либо единственная найденная точка.

Более сложный случай — если прямые оказались параллельными (сюда же относится случай, когда один или оба отрезка выродились в точки). В этом случае надо проверить, что оба отрезка лежат на одной прямой (или, в случае когда они оба вырождены в точку — что эта точка совпадает). Если это не так, то ответ — "пусто". Если это так, то ответ — это пересечение двух отрезков, лежащих на одной прямой, что реализуется достаточно просто — надо взять максимум из левых концов и минимум из правых концов.

В самом начале алгоритма напишем так называемую "проверку на bounding box" — во-первых, она необходима для случая, когда два отрезка лежат на одной прямой, а во-вторых, она, как легковесная проверка, позволяет алгоритму работать в среднем быстрее на случайных тестах.

Реализация

Приведём здесь полную реализацию, включая все вспомогательные функции по работе с точками и прямыми.

Главной здесь является функция , которая пересекает два переданных ей отрезка, и если они пересекаются хотя бы по одной точке, то возвращает , а в аргументах и возвращает начало и конец отрезка-ответа (в частности, когда ответ — это единственная точка, возвращаемые начало и конец будут совпадать).

constdouble EPS =1E-9;   struct pt double x, y;   bool operator<const pt & pconstreturn x < p.x-EPS ||absx-p.x< EPS && y < p.y- EPS;;   struct line double a, b, c;   line line pt p, pt q a = p.y- q.y; b = q.x- p.x; c =- a * p.x- b * p.y; norm;   void normdouble z =sqrta*a + b*b;ifabsz> EPS a /= z, b /= z, c /= z;   double dist pt pconstreturn a * p.x+ b * p.y+ c;;   #define det(a,b,c,d) (a*d-b*c)   inlinebool betw double l, double r, double xreturn minl,r<= x + EPS && x <= maxl,r+ EPS;   inlinebool intersect_1d double a, double b, double c, double difa > b swap a, b;ifc > d swap c, d;return max a, c<= min b, d+ EPS;   bool intersect pt a, pt b, pt c, pt d, pt & left, pt & rightif! intersect_1d a.x, b.x, c.x, d.x||! intersect_1d a.y, b.y, c.y, d.yreturnfalse; line m a, b; line n c, d;double zn = det m.a, m.b, n.a, n.b;ifabszn< EPSifabsm.distc> EPS ||absn.dista> EPSreturnfalse;ifb < a swap a, b;ifd < c swap c, d; left = max a, c; right = min b, d;returntrue;else left.x= right.x=- det m.c, m.b, n.c, n.b/ zn; left.y= right.y=- det m.a, m.c, n.a, n.c/ zn;return betw a.x, b.x, left.x&& betw a.y, b.y, left.y&& betw c.x, d.x, left.x&& betw c.y, d.y, left.y;

Урок из серии «Геометрические алгоритмы»

Здравствуйте,  дорогой читатель.

Напишем еще три новые функции.

Функция LinesCross() будет определять, пересекаются ли два отрезка. В ней взаимное расположение отрезков определяется с помощью векторных произведений.

Пересечение двух отрезков

Для вычисления векторных произведений напишем  функцию VektorMulti().

Функция RealLess() будет использоваться для реализации операции сравнения  < (строго меньше) для вещественных чисел.

Задача1. Два отрезка заданы своими координатами. Составить программу, которая определяет, пересекаются ли эти отрезки, не находя точку пересечения.

Решение
Пусть даны два отрезка. Первый задан точками . Второй задан точками .


Взаимное расположение отрезков можно проверить с помощью векторных произведений:


Рассмотрим отрезок и точки и .

Точка лежит слева от прямой , для нее векторное произведение > 0, так как векторы положительно ориентированы.

Точка расположена справа от прямой, для нее векторное произведение < 0, так как векторы отрицательно ориентированы.

Для того чтобы точки и , лежали по разные стороны от прямой , достаточно, чтобы выполнялось условие < 0 ( векторные произведения имели противоположные  знаки).

Аналогичные рассуждения можно провести для отрезка и точек и .

Итак, если , то отрезки пересекаются.

Для проверки этого условия используется функцию LinesCross(), а для вычисления векторных произведений – функция VektorMulti().

Векторное произведение двух векторов вычисляется по формуле:

где:

ax, ay координаты первого вектора,

bx, by координаты второго вектора.

Program geometr4; {Пересекаются ли 2 отрезка?} Const _Eps: Real=1e-4; {точность вычслений} var x1,y1,x2,y2,x3,y3,x4,y4: real; var v1,v2,v3,v4: real;function RealLess(Const a, b: Real): Boolean; {Строго меньше} begin RealLess := b-a> _Eps end; {RealLess}function VektorMulti(ax,ay,bx,by:real): real; {ax,ay — координаты a bx,by — координаты b } begin vektormulti:= ax*by-bx*ay; end;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): boolean; {Пересекаются ли отрезки?} begin v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=vektormulti(x4-x3,y4-y3,x2-x3,y2-y3); v3:=vektormulti(x2-x1,y2-y1,x3-x1,y3-y1); v4:=vektormulti(x2-x1,y2-y1,x4-x1,y4-y1); if RealLess(v1*v2,0) and RealLess(v3*v4,0) {v1v2<0 и v3v4<0, отрезки пересекаются} then LinesCross:= true else LinesCross:= false end; {LinesCross}begin {main} writeln(‘Введите координаты отрезков: x1,y1,x2,y2,x3,y3,x4,y4’); readln( x1,y1,x2,y2,x3,y3,x4,y4); if LinesCross(x1,y1,x2,y2,x3,y3,x4,y4) then writeln (‘Да’) else writeln (‘Нет’) end.

Результаты выполнения программы:

Введите координаты отрезков: -1  1 2 2.52 2 1 -1 3
Да.

Мы написали программу, определяющую, пересекаются ли отрезки, заданные своими координатами.

На следующем уроке мы составим алгоритм, с помощью которого можно будет определить, лежит ли точка внутри треугольника.

Уважаемый читатель. Вы уже познакомились с несколькими уроками из серии «Геометрические алгоритмы». Все ли доступно написано? Я буду Вам очень признательна, если Вы оставите отзыв об этих уроках. Возможно, что-то нужно еще доработать.

С уважением, Вера Господарец.

Поделиться с друзьями

добавлено: 11 Jun 2008 10:22
редактировано: 20 Jun 2011 1:15

Пересечение двух отрезков

Даны два отрезка и (они могут вырождаться в точки).

Найти точку пересечения двух отрезков

Требуется найти их пересечение: оно может быть пустым (если отрезки не пересекаются), может быть одной точкой, и может быть целым отрезком (если отрезки накладываются друг на друга).

Алгоритм

Работать с отрезками будем как с прямыми: построим по двум отрезкам уравнения их прямых, проверим, не параллельны ли прямые. Если прямые не параллельны, то всё просто: находим их точку пересечения и проверяем, что она принадлежит обоим отрезкам (для этого достаточно проверить, что точка принадлежит каждому отрезку в проекции на ось и на ось по отдельности). В итоге в этом случае ответом будет либо "пусто", либо единственная найденная точка.

Более сложный случай — если прямые оказались параллельными (сюда же относится случай, когда один или оба отрезка выродились в точки). В этом случае надо проверить, что оба отрезка лежат на одной прямой (или, в случае когда они оба вырождены в точку — что эта точка совпадает). Если это не так, то ответ — "пусто". Если это так, то ответ — это пересечение двух отрезков, лежащих на одной прямой, что реализуется достаточно просто — надо взять максимум из левых концов и минимум из правых концов.

В самом начале алгоритма напишем так называемую "проверку на bounding box" — во-первых, она необходима для случая, когда два отрезка лежат на одной прямой, а во-вторых, она, как легковесная проверка, позволяет алгоритму работать в среднем быстрее на случайных тестах.

Реализация

Приведём здесь полную реализацию, включая все вспомогательные функции по работе с точками и прямыми.

Главной здесь является функция , которая пересекает два переданных ей отрезка, и если они пересекаются хотя бы по одной точке, то возвращает , а в аргументах и возвращает начало и конец отрезка-ответа (в частности, когда ответ — это единственная точка, возвращаемые начало и конец будут совпадать).

constdouble EPS =1E-9;   struct pt double x, y;   bool operator<const pt & pconstreturn x < p.x-EPS ||absx-p.x< EPS && y < p.y- EPS;;   struct line double a, b, c;   line line pt p, pt q a = p.y- q.y; b = q.x- p.x; c =- a * p.x- b * p.y; norm;   void normdouble z =sqrta*a + b*b;ifabsz> EPS a /= z, b /= z, c /= z;   double dist pt pconstreturn a * p.x+ b * p.y+ c;;   #define det(a,b,c,d) (a*d-b*c)   inlinebool betw double l, double r, double xreturn minl,r<= x + EPS && x <= maxl,r+ EPS;   inlinebool intersect_1d double a, double b, double c, double difa > b swap a, b;ifc > d swap c, d;return max a, c<= min b, d+ EPS;   bool intersect pt a, pt b, pt c, pt d, pt & left, pt & rightif! intersect_1d a.x, b.x, c.x, d.x||! intersect_1d a.y, b.y, c.y, d.yreturnfalse; line m a, b; line n c, d;double zn = det m.a, m.b, n.a, n.b;ifabszn< EPSifabsm.distc> EPS ||absn.dista> EPSreturnfalse;ifb < a swap a, b;ifd < c swap c, d; left = max a, c; right = min b, d;returntrue;else left.x= right.x=- det m.c, m.b, n.c, n.b/ zn; left.y= right.y=- det m.a, m.c, n.a, n.c/ zn;return betw a.x, b.x, left.x&& betw a.y, b.y, left.y&& betw c.x, d.x, left.x&& betw c.y, d.y, left.y;

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *