Point of intersection of lines

Let us be given two straight lines given by their coefficients and . It is required to find their intersection point, or find out that the lines are parallel.

Solution

If two lines are not parallel, then they intersect. To find the intersection point, it is enough to compose a system of two equations of lines and solve it:

Using Cramer's formula, we immediately find a solution to the system, which will be the desired intersection point:

If the denominator is zero, i.e.

then the system of solutions has no (direct are parallel and do not coincide) or has infinitely many (direct match). If it is necessary to distinguish between these two cases, it is necessary to check that the coefficients of the lines are proportional with the same coefficient of proportionality as the coefficients and , for which it is enough to calculate two determinants, if they are both equal to zero, then the lines coincide:

Implementation

struct pt (double x, y;); struct line (double a, b, c;); constdouble EPS=1e-9; double det (double a, double b, double c, double d)(return a * d - b * c;) bool intersect (line m, line n, pt & res)(double zn = det (m.a, m.b, n.a , n.b);if(abs(zn)< EPS)returnfalse; res.x=- det (m.c, m.b, n.c, n.b)/ zn; res.y=- det (m.a, m.c, n.a, n.c)/ zn;returntrue;} bool parallel (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS;} bool equivalent (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS &&abs(det (m.a, m.c, n.a, n.c))< EPS &&abs(det (m.b, m.c, n.b, n.c))< EPS;}

Lesson from the series " Geometric Algorithms»

Hello dear reader.

Tip 1: How to find the coordinates of the point of intersection of two lines

Let's write three more new functions.

The LinesCross() function will determine if intersect whether two segment. In it, the relative position of the segments is determined using vector products. To calculate vector products, let's write a function - VektorMulti().

The RealLess() function will be used to implement the comparison operation “<” (строго меньше) для вещественных чисел.

Task1. Two segments are given by their coordinates. Write a program that determines Do these segments intersect? without finding the intersection point.

Solution
. The second is given by dots.

Consider a segment and points and .

The point lies to the left of the line, for which the vector product > 0, since the vectors are positively oriented.

The point is located to the right of the line, for it the vector product < 0, так как векторы отрицательно ориентированы.

In order for the points and , to lie on opposite sides of the line , it is sufficient that the condition< 0 (векторные произведения имели противоположные знаки).

Similar reasoning can be carried out for the segment and points and .

So if , then the segments intersect.

To check this condition, the LinesCross() function is used, and to calculate vector products, the VektorMulti() function is used.

ax, ay are the coordinates of the first vector,

bx, by are the coordinates of the second vector.

Program geometry4; (Do 2 segments intersect?) Const _Eps: Real=1e-4; (calculation precision) var x1,y1,x2,y2,x3,y3,x4,y4: real; var v1,v2,v3,v4: real;function RealLess(Const a, b: Real): Boolean; (Strictly less than) begin RealLess:= b-a> _Eps end; (RealLess)function VektorMulti(ax,ay,bx,by:real): real; (ax,ay - a coordinates bx,by - b coordinates) begin vektormulti:= ax*by-bx*ay; end;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): boolean; (Do the segments intersect?) begin v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=vectormulti(x4-x3,y4-y3,x2-x3,y2-y3); v3:=vectormulti(x2-x1,y2-y1,x3-x1,y3-y1); v4:=vectormulti(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.

Program execution results:

Enter the coordinates of the segments: -1 1 2 2.52 2 1 -1 3
Yes.

We have written a program that determines whether the segments given by their coordinates intersect.

In the next lesson, we will write an algorithm that can be used to determine whether a point lies inside a triangle.

Dear reader.

You have already read several lessons from the Geometric Algorithms series. Is everything available written? I will be very grateful if you leave a review about these lessons. Perhaps something else needs to be improved.

Sincerely, Vera Gospodarets.

Let two segments be given. The first one is given by dots P 1 (x 1 ;y 1) and P 2 (x 2 ;y 2). The second is given by dots P 3 (x 3 ;y 3) and P 4 (x 4 ;y 4).

The relative position of the segments can be checked using vector products:

Consider the segment P 3 P 4 and points P1 and P2.

Dot P1 lies to the left of the line P 3 P 4, for it the vector product v1 > 0, since the vectors are positively oriented.
Dot P2 located to the right of the line, for it the vector product v2< 0 , since the vectors are negatively oriented.

To point P1 and P2 lie on opposite sides of a straight line P 3 P 4, it is sufficient that the condition v 1 v 2< 0 (vector products had opposite signs).

Similar reasoning can be carried out for the segment P 1 P 2 and points P3 and P4.

So if v 1 v 2< 0 and v 3 v 4< 0 , then the segments intersect.

The cross product of two vectors is calculated by the formula:

where:
ax, ay are the coordinates of the first vector,
bx, by are the coordinates of the second vector.

The equation of a straight line passing through two different points given by their coordinates.

Let two non-coinciding points be given on a straight line: P1 with coordinates ( x1;y1) and P2 with coordinates (x 2 ; y 2).

Line intersection

Accordingly, the vector with the origin at the point P1 and end at a point P2 has coordinates (x 2 -x 1, y 2 -y 1). If a P(x, y) is an arbitrary point on the line, then the coordinates of the vector P 1 P equal (x - x 1, y - y 1).

With the help of the cross product, the condition of collinarity of vectors P 1 P and P 1 P 2 can be written like this:
|P 1 P,P 1 P 2 |=0, i.e. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
or
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

The last equation is rewritten as follows:
ax + by + c = 0, (1)
where
a \u003d (y 2 -y 1),
b \u003d (x 1 -x 2),
c \u003d x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

So, the straight line can be given by an equation of the form (1).

How to find the point of intersection of lines?
The obvious solution is to solve the system of equations of lines:

ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2 (2)

Enter designations:

Here D is the determinant of the system, and D x ,D y are the determinants obtained by replacing the column of coefficients for the corresponding unknown with a column of free terms. If a D ≠ 0, then system (2) is definite, that is, it has a unique solution. This solution can be found using the following formulas: x 1 \u003d D x / D, y 1 \u003d D y / D, which are called Cramer's formulas. A little reminder of how the second order determinant is calculated. The determinant distinguishes between two diagonals: the main and secondary. The main diagonal consists of elements taken in the direction from the upper left corner of the determinant to the lower right corner. Side diagonal - from the upper right to the lower left. The second order determinant is equal to the product of the elements of the main diagonal minus the product of the elements of the secondary diagonal.

Let two segments be given. The first one is given by dots P 1 (x 1 ;y 1) and P 2 (x 2 ;y 2). The second is given by dots P 3 (x 3 ;y 3) and P 4 (x 4 ;y 4).

The relative position of the segments can be checked using vector products:

Consider the segment P 3 P 4 and points P1 and P2.

Dot P1 lies to the left of the line P 3 P 4, for it the vector product v1 > 0, since the vectors are positively oriented.
Dot P2 located to the right of the line, for it the vector product v2< 0 , since the vectors are negatively oriented.

To point P1 and P2 lie on opposite sides of a straight line P 3 P 4, it is sufficient that the condition v 1 v 2< 0 (vector products had opposite signs).

Similar reasoning can be carried out for the segment P 1 P 2 and points P3 and P4.

So if v 1 v 2< 0 and v 3 v 4< 0 , then the segments intersect.

The cross product of two vectors is calculated by the formula:

where:
ax, ay- coordinates of the first vector,
bx, by- coordinates of the second vector.

The equation of a straight line passing through two different points given by their coordinates.

Let two non-coinciding points be given on a straight line: P1 with coordinates ( x1;y1) and P2 with coordinates (x 2 ; y 2). Accordingly, the vector with the origin at the point P1 and end at a point P2 has coordinates (x 2 -x 1, y 2 -y 1). If a P(x, y) is an arbitrary point on the line, then the coordinates of the vector P 1 P equal (x - x 1, y - y 1).

With the help of the cross product, the condition of collinarity of vectors P 1 P and P 1 P 2 can be written like this:
|P 1 P ,P 1 P 2 |=0, i.e. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
or
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

The last equation is rewritten as follows:
ax + by + c = 0, (1)
where
a \u003d (y 2 -y 1),
b \u003d (x 1 -x 2),
c \u003d x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

So, the straight line can be given by an equation of the form (1).

How to find the point of intersection of lines?
The obvious solution is to solve the system of equations of lines:

ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2 (2)

Enter designations:

Here D is the determinant of the system, and D x ,D y are the determinants resulting from replacing the column of coefficients for the corresponding unknown with a column of free terms. If a D ≠ 0, then system (2) is definite, that is, it has a unique solution. This solution can be found using the following formulas: x 1 \u003d D x / D, y 1 \u003d D y / D, which are called Cramer's formulas. A little reminder of how the second order determinant is calculated. The determinant distinguishes between two diagonals: the main and secondary. The main diagonal consists of elements taken in the direction from the upper left corner of the determinant to the lower right corner. Side diagonal - from the upper right to the lower left. The second order determinant is equal to the product of the elements of the main diagonal minus the product of the elements of the secondary diagonal.