Lesson from the series “Geometric algorithms”

Hello dear reader!

Today we will start learning algorithms related to geometry. The fact is that there are quite a lot of Olympiad problems in computer science related to computational geometry, and solving such problems often causes difficulties.

Over the course of several lessons, we will consider a number of elementary subtasks on which the solution of most problems in computational geometry is based.

In this lesson we will create a program for finding the equation of a line, passing through given two points. To solve geometric problems, we need some knowledge of computational geometry. We will devote part of the lesson to getting to know them.

Insights from Computational Geometry

Computational geometry is a branch of computer science that studies algorithms for solving geometric problems.

The initial data for such problems can be a set of points on a plane, a set of segments, a polygon (specified, for example, by a list of its vertices in clockwise order), etc.

The result can be either an answer to some question (such as does a point belong to a segment, do two segments intersect, ...), or some geometric object (for example, the smallest convex polygon connecting given points, the area of ​​a polygon, etc.) .

We will consider problems of computational geometry only on the plane and only in the Cartesian coordinate system.

Vectors and coordinates

To apply the methods of computational geometry, it is necessary to translate geometric images into the language of numbers. We will assume that the plane is given a Cartesian coordinate system, in which the direction of rotation counterclockwise is called positive.

Now geometric objects receive an analytical expression. So, to specify a point, it is enough to indicate its coordinates: a pair of numbers (x; y). A segment can be specified by specifying the coordinates of its ends; a straight line can be specified by specifying the coordinates of a pair of its points.

But our main tool for solving problems will be vectors. Let me therefore recall some information about them.

Segment AB, which has a point A is considered the beginning (point of application), and the point IN– end, called a vector AB and is denoted by either or by a bold lowercase letter, for example A .

To denote the length of a vector (that is, the length of the corresponding segment), we will use the modulus symbol (for example, ).

An arbitrary vector will have coordinates equal to the difference between the corresponding coordinates of its end and beginning:

,

here are the points A And B have coordinates respectively.

For calculations we will use the concept oriented angle, that is, an angle that takes into account the relative position of the vectors.

Oriented angle between vectors a And b positive if the rotation is from the vector a to vector b is performed in a positive direction (counterclockwise) and negative in the other case. See Fig.1a, Fig.1b. It is also said that a pair of vectors a And b positively (negatively) oriented.

Thus, the value of the oriented angle depends on the order in which the vectors are listed and can take values ​​in the interval .

Many problems in computational geometry use the concept of vector (skew or pseudoscalar) products of vectors.

The vector product of vectors a and b is the product of the lengths of these vectors and the sine of the angle between them:

.

Cross product of vectors in coordinates:

The expression on the right is a second-order determinant:

Unlike the definition given in analytical geometry, it is a scalar.

The sign of the vector product determines the position of the vectors relative to each other:

a And b positively oriented.

If the value is , then a pair of vectors a And b negatively oriented.

The cross product of nonzero vectors is zero if and only if they are collinear ( ). This means that they lie on the same line or on parallel lines.

Let's look at a few simple problems that are necessary when solving more complex ones.

Let's determine the equation of a straight line from the coordinates of two points.

Equation of a line passing through two different points specified by their coordinates.

Let two non-coinciding points be given on a straight line: with coordinates (x1; y1) and with coordinates (x2; y2). Accordingly, a vector with a start at a point and an end at a point has coordinates (x2-x1, y2-y1). If P(x, y) is an arbitrary point on our line, then the coordinates of the vector are equal to (x-x1, y – y1).

Using the vector product, the condition for collinearity of vectors and can be written as follows:

Those. (x-x1)(y2-y1)-(y-y1)(x2-x1)=0

(y2-y1)x + (x1-x2)y + x1(y1-y2) + y1(x2-x1) = 0

We rewrite the last equation as follows:

ax + by + c = 0, (1)

c = x1(y1-y2) + y1(x2-x1)

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

Problem 1. The coordinates of two points are given. Find its representation in the form ax + by + c = 0.

In this lesson we learned some information about computational geometry. We solved the problem of finding the equation of a line from the coordinates of two points.

In the next lesson we will create a program to find the intersection point of two lines given by our equations.

Definition. Any straight line on the plane can be specified by a first-order equation

Ax + Wu + C = 0,

Moreover, the constants A and B are not equal to zero at the same time. This first order equation is called general equation of a straight line. Depending on the values ​​of constants A, B and C, the following special cases are possible:

C = 0, A ≠0, B ≠ 0 – the straight line passes through the origin

A = 0, B ≠0, C ≠0 (By + C = 0) - straight line parallel to the Ox axis

B = 0, A ≠0, C ≠ 0 (Ax + C = 0) – straight line parallel to the Oy axis

B = C = 0, A ≠0 – the straight line coincides with the Oy axis

A = C = 0, B ≠0 – the straight line coincides with the Ox axis

The equation of a straight line can be presented in different forms depending on any given initial conditions.

Equation of a straight line from a point and normal vector

Definition. In the Cartesian rectangular coordinate system, a vector with components (A, B) is perpendicular to the straight line given by the equation Ax + By + C = 0.

Example. Find the equation of the line passing through the point A(1, 2) perpendicular to (3, -1).

Solution. With A = 3 and B = -1, let’s compose the equation of the straight line: 3x – y + C = 0. To find the coefficient C, we substitute the coordinates of the given point A into the resulting expression. We get: 3 – 2 + C = 0, therefore, C = -1 . Total: the required equation: 3x – y – 1 = 0.

Equation of a line passing through two points

Let two points M 1 (x 1, y 1, z 1) and M 2 (x 2, y 2, z 2) be given in space, then the equation of the line passing through these points is:

If any of the denominators is equal to zero, the corresponding numerator should be equal to zero. On the plane, the equation of the line written above is simplified:

if x 1 ≠ x 2 and x = x 1, if x 1 = x 2.

The fraction = k is called slope direct.

Example. Find the equation of the line passing through points A(1, 2) and B(3, 4).

Solution. Applying the formula written above, we get:

Equation of a straight line from a point and slope

If the total Ax + Bu + C = 0, lead to the form:

and designate , then the resulting equation is called equation of a straight line with slopek.

Equation of a straight line from a point and a direction vector

By analogy with the point considering the equation of a straight line through a normal vector, you can enter the definition of a straight line through a point and the directing vector of the straight line.

Definition. Each non-zero vector (α 1, α 2), the components of which satisfy the condition A α 1 + B α 2 = 0 is called a directing vector of the line

Ax + Wu + C = 0.

Example. Find the equation of a straight line with a direction vector (1, -1) and passing through the point A(1, 2).

Solution. We will look for the equation of the desired line in the form: Ax + By + C = 0. In accordance with the definition, the coefficients must satisfy the conditions:

1 * A + (-1) * B = 0, i.e. A = B.

Then the equation of the straight line has the form: Ax + Ay + C = 0, or x + y + C / A = 0. for x = 1, y = 2 we obtain C/ A = -3, i.e. required equation:

Equation of a line in segments

If in the general equation of the straight line Ах + Ву + С = 0 С≠0, then, dividing by –С, we get: or

The geometric meaning of the coefficients is that the coefficient A is the coordinate of the point of intersection of the line with the Ox axis, and b– the coordinate of the point of intersection of the straight line with the Oy axis.

Example. The general equation of the line x – y + 1 = 0 is given. Find the equation of this line in segments.

C = 1, , a = -1, b = 1.

Normal equation of a line

If both sides of the equation Ax + By + C = 0 are multiplied by the number which is called normalizing factor, then we get

xcosφ + ysinφ - p = 0 –

normal equation of a line. The sign ± of the normalizing factor must be chosen so that μ * C< 0. р – длина перпендикуляра, опущенного из начала координат на прямую, а φ - угол, образованный этим перпендикуляром с положительным направлением оси Ох.

Example. The general equation of the line 12x – 5y – 65 = 0 is given. It is required to write various types of equations for this line.

equation of this line in segments:

equation of this line with slope: (divide by 5)

; cos φ = 12/13; sin φ= -5/13; p = 5.

It should be noted that not every straight line can be represented by an equation in segments, for example, straight lines parallel to axes or passing through the origin of coordinates.

Example. The straight line cuts off equal positive segments on the coordinate axes. Write an equation of a straight line if the area of ​​the triangle formed by these segments is 8 cm 2.

Solution. The equation of the straight line has the form: , ab /2 = 8; ab=16; a=4, a=-4. a = -4< 0 не подходит по условию задачи. Итого: или х + у – 4 = 0.

Example. Write an equation for a straight line passing through point A(-2, -3) and the origin.

Solution. The equation of the straight line is: , where x 1 = y 1 = 0; x 2 = -2; y2 = -3.

Angle between straight lines on a plane

Definition. If two lines are given y = k 1 x + b 1, y = k 2 x + b 2, then the acute angle between these lines will be defined as

.

Two lines are parallel if k 1 = k 2. Two lines are perpendicular if k 1 = -1/ k 2.

Theorem. The lines Ax + Bу + C = 0 and A 1 x + B 1 y + C 1 = 0 are parallel when the coefficients A 1 = λA, B 1 = λB are proportional. If also C 1 = λC, then the lines coincide. The coordinates of the point of intersection of two lines are found as a solution to the system of equations of these lines.

Equation of a line passing through a given point perpendicular to a given line

Definition. A straight line passing through the point M 1 (x 1, y 1) and perpendicular to the straight line y = kx + b is represented by the equation:

Distance from point to line

Theorem. If a point M(x 0, y 0) is given, then the distance to the line Ax + Bу + C = 0 is determined as

.

Proof. Let point M 1 (x 1, y 1) be the base of a perpendicular dropped from point M to a given straight line. Then the distance between points M and M 1:

(1)

The coordinates x 1 and y 1 can be found by solving the system of equations:

The second equation of the system is the equation of a line passing through a given point M 0 perpendicular to a given line. If we transform the first equation of the system to the form:

A(x – x 0) + B(y – y 0) + Ax 0 + By 0 + C = 0,

then, solving, we get:

Substituting these expressions into equation (1), we find:

The theorem has been proven.

Example. Determine the angle between the lines: y = -3 x + 7; y = 2 x + 1.

k 1 = -3; k 2 = 2; tgφ = ; φ= π /4.

Example. Show that the lines 3x – 5y + 7 = 0 and 10x + 6y – 3 = 0 are perpendicular.

Solution. We find: k 1 = 3/5, k 2 = -5/3, k 1* k 2 = -1, therefore, the lines are perpendicular.

Example. Given are the vertices of the triangle A(0; 1), B (6; 5), C (12; -1). Find the equation of the height drawn from vertex C.

Solution. We find the equation of side AB: ; 4 x = 6 y – 6;

2 x – 3 y + 3 = 0;

The required height equation has the form: Ax + By + C = 0 or y = kx + b. k = . Then y = . Because the height passes through point C, then its coordinates satisfy this equation: from where b = 17. Total: .

Answer: 3 x + 2 y – 34 = 0.

Properties of a straight line in Euclidean geometry.

An infinite number of straight lines can be drawn through any point.

Through any two non-coinciding points a single straight line can be drawn.

Two divergent lines in a plane either intersect at a single point or are

parallel (follows from the previous one).

In three-dimensional space, there are three options for the relative position of two lines:

• lines intersect;

• lines are parallel;

• straight lines intersect.

Straight line— algebraic curve of the first order: a straight line in the Cartesian coordinate system

is given on the plane by an equation of the first degree (linear equation).

General equation of a straight line.

Definition. Any straight line on the plane can be specified by a first-order equation

Ax + Wu + C = 0,

and constant A, B are not equal to zero at the same time. This first order equation is called general

equation of a straight line. Depending on the values ​​of the constants A, B And WITH The following special cases are possible:

. C = 0, A ≠0, B ≠ 0- a straight line passes through the origin

. A = 0, B ≠0, C ≠0 (By + C = 0)- straight line parallel to the axis Oh

. B = 0, A ≠0, C ≠ 0 (Ax + C = 0)- straight line parallel to the axis Oh

. B = C = 0, A ≠0- the straight line coincides with the axis Oh

. A = C = 0, B ≠0- the straight line coincides with the axis Oh

The equation of a straight line can be presented in different forms depending on any given

initial conditions.

Equation of a straight line from a point and a normal vector.

Definition. In a Cartesian rectangular coordinate system, a vector with components (A, B)

perpendicular to the line given by the equation

Ax + Wu + C = 0.

Example. Find the equation of a line passing through a point A(1, 2) perpendicular to the vector (3, -1).

Solution. With A = 3 and B = -1, let’s compose the equation of the straight line: 3x - y + C = 0. To find the coefficient C

Let's substitute the coordinates of the given point A into the resulting expression. We get: 3 - 2 + C = 0, therefore

C = -1. Total: the required equation: 3x - y - 1 = 0.

Equation of a line passing through two points.

Let two points be given in space M 1 (x 1 , y 1 , z 1) And M2 (x 2, y 2, z 2), Then equation of a line,

passing through these points:

If any of the denominators is zero, the corresponding numerator should be set equal to zero. On

plane, the equation of the straight line written above is simplified:

If x 1 ≠ x 2 And x = x 1, If x 1 = x 2 .

Fraction = k called slope direct.

Example. Find the equation of the line passing through points A(1, 2) and B(3, 4).

Solution. Applying the formula written above, we get:

Equation of a straight line using a point and slope.

If the general equation of a line Ax + Wu + C = 0 lead to:

and designate , then the resulting equation is called

equation of a straight line with slope k.

Equation of a straight line from a point and a direction vector.

By analogy with the point considering the equation of a straight line through the normal vector, you can enter the task

a straight line through a point and a directing vector of a straight line.

Definition. Every non-zero vector (α 1 , α 2), whose components satisfy the condition

Aα 1 + Bα 2 = 0 called directing vector of a straight line.

Ax + Wu + C = 0.

Example. Find the equation of a straight line with a direction vector (1, -1) and passing through the point A(1, 2).

Solution. We will look for the equation of the desired line in the form: Ax + By + C = 0. According to the definition,

coefficients must satisfy the following conditions:

1 * A + (-1) * B = 0, i.e. A = B.

Then the equation of the straight line has the form: Ax + Ay + C = 0, or x + y + C / A = 0.

at x = 1, y = 2 we get C/A = -3, i.e. required equation:

x + y - 3 = 0

Equation of a straight line in segments.

If in the general equation of the straight line Ах + Ву + С = 0 С≠0, then, dividing by -С, we get:

or where

The geometric meaning of the coefficients is that the coefficient a is the coordinate of the intersection point

straight with axis Oh, A b- coordinate of the point of intersection of the line with the axis Oh.

Example. The general equation of a straight line is given x - y + 1 = 0. Find the equation of this line in segments.

C = 1, , a = -1, b = 1.

Normal equation of a line.

If both sides of the equation Ax + Wu + C = 0 divide by number which is called

normalizing factor, then we get

xcosφ + ysinφ - p = 0 -normal equation of a line.

The sign ± of the normalizing factor must be chosen so that μ*C< 0.

r- the length of the perpendicular dropped from the origin to the straight line,

A φ - the angle formed by this perpendicular with the positive direction of the axis Oh.

Example. The general equation of the line is given 12x - 5y - 65 = 0. Required to write different types of equations

this straight line.

The equation of this line in segments:

The equation of this line with the slope: (divide by 5)

Equation of a line:

cos φ = 12/13; sin φ= -5/13; p = 5.

It should be noted that not every straight line can be represented by an equation in segments, for example, straight lines,

parallel to the axes or passing through the origin.

The angle between straight lines on a plane.

Definition. If two lines are given y = k 1 x + b 1 , y = k 2 x + b 2, then the acute angle between these lines

will be defined as

Two lines are parallel if k 1 = k 2. Two lines are perpendicular

If k 1 = -1/ k 2 .

Theorem.

Direct Ax + Wu + C = 0 And A 1 x + B 1 y + C 1 = 0 parallel when the coefficients are proportional

A 1 = λA, B 1 = λB. If also С 1 = λС, then the lines coincide. Coordinates of the point of intersection of two lines

are found as a solution to the system of equations of these lines.

The equation of a line passing through a given point perpendicular to a given line.

Definition. Line passing through a point M 1 (x 1, y 1) and perpendicular to the line y = kx + b

represented by the equation:

Distance from a point to a line.

Theorem. If a point is given M(x 0, y 0), then the distance to the straight line Ax + Wu + C = 0 defined as:

Proof. Let the point M 1 (x 1, y 1)- the base of a perpendicular dropped from a point M for a given

direct. Then the distance between points M And M 1:

(1)

Coordinates x 1 And at 1 can be found as a solution to the system of equations:

The second equation of the system is the equation of a straight line passing through a given point M 0 perpendicularly

given straight line. If we transform the first equation of the system to the form:

A(x - x 0) + B(y - y 0) + Ax 0 + By 0 + C = 0,

then, solving, we get:

Substituting these expressions into equation (1), we find:

The theorem has been proven.

The equation of a line passing through a given point in a given direction. Equation of a line passing through two given points. The angle between two straight lines. The condition of parallelism and perpendicularity of two straight lines. Determining the point of intersection of two lines

1. Equation of a line passing through a given point A(x 1 , y 1) in a given direction, determined by the slope k,

y - y 1 = k(x - x 1). (1)

This equation defines a pencil of lines passing through a point A(x 1 , y 1), which is called the beam center.

2. Equation of a line passing through two points: A(x 1 , y 1) and B(x 2 , y 2), written like this:

The angular coefficient of a straight line passing through two given points is determined by the formula

3. Angle between straight lines A And B is the angle by which the first straight line must be rotated A around the point of intersection of these lines counterclockwise until it coincides with the second line B. If two straight lines are given by equations with a slope

y = k 1 x + B 1 ,

Equation of a line passing through two points. In the article" " I promised you to look at the second way to solve the presented problems of finding the derivative, given a graph of a function and a tangent to this graph. We will discuss this method in , don't miss it! Why in the next one?

The fact is that the formula for the equation of a straight line will be used there. Of course, we could simply show this formula and advise you to learn it. But it’s better to explain where it comes from (how it is derived). This is necessary! If you forget it, you can quickly restore itwill not be difficult. Everything is described in detail below. So, we have two points A on the coordinate plane(x 1;y 1) and B(x 2;y 2), a straight line is drawn through the indicated points:

Here is the direct formula itself:

*That is, when substituting specific coordinates of points, we get an equation of the form y=kx+b.

**If you simply “memorize” this formula, then there is a high probability of getting confused with the indices when X. In addition, indices can be designated in different ways, for example:

That's why it's important to understand the meaning.

Now the derivation of this formula. It's very simple!

Triangles ABE and ACF are similar in acute angle (the first sign of similarity of right triangles). It follows from this that the ratios of the corresponding elements are equal, that is:

Now we simply express these segments through the difference in the coordinates of the points:

Of course, there will be no error if you write the relationships of the elements in a different order (the main thing is to maintain consistency):

The result will be the same equation of the line. This is all!

That is, no matter how the points themselves (and their coordinates) are designated, by understanding this formula you will always find the equation of a straight line.

The formula can be derived using the properties of vectors, but the principle of derivation will be the same, since we will be talking about the proportionality of their coordinates. In this case, the same similarity of right triangles works. In my opinion, the conclusion described above is more clear)).

View output using vector coordinates >>>

Let a straight line be constructed on the coordinate plane passing through two given points A(x 1;y 1) and B(x 2;y 2). Let us mark an arbitrary point C on the line with coordinates ( x; y). We also denote two vectors:

It is known that for vectors lying on parallel lines (or on the same line), their corresponding coordinates are proportional, that is:

— we write down the equality of the ratios of the corresponding coordinates:

Let's look at an example:

Find the equation of a straight line passing through two points with coordinates (2;5) and (7:3).

You don’t even have to build the straight line itself. We apply the formula:

It is important that you grasp the correspondence when drawing up the ratio. You can't go wrong if you write:

Answer: y=-2/5x+29/5 go y=-0.4x+5.8

In order to make sure that the resulting equation is found correctly, be sure to check - substitute the coordinates of the data in the condition of the points into it. The equations should be correct.

That's all. I hope the material was useful to you.

Best regards, Alexander.

P.S: I would be grateful if you tell me about the site on social networks.