Geometry


Definitions and concepts

A vector is a directional line that is defined 2 coordinates.


Multiplying a vector by a number k is changing its length by k times. When \(k < 0\) the vector will expand.

The length of a vector is calculated by the formula \(\sqrt {x^2 + y^2} \). 

Normalized vector - a vector of unit length, obtained by dividing a vector by its length.

The sum of vectors is obtained by constructing a second vector from the end of the first, and putting the vector into the resulting point.

If x1, y1, x 2, y2 - coordinates of the first and second vectors, respectively, then their sum is a vector with coordinates \((x_1 + x_2) \)and \((y_1 + y_2) \).

Vector difference - the sum where the second vector is reversed (multiplied by -1).

Dot product of vectors - number, projection of one vector onto another multiplied by its length. In the simplest case of ordinary Euclidean space, "geometric" space is sometimes used. definition of the scalar product of non-zero vectors a and b as the product of the lengths of these vectors and the cosine of the angle between them: 
\(a \cdot b = |a| \cdot |b| \cdot cos \alpha\).

For the dot product by a vector, the following formula holds true:
\(a \cdot b = x_1 \cdot x_2 + y_1 \cdot y_2\), 
where x1, y1, x2, y2 - coordinates of the first and second vector, respectively, allows you to determine whether the second vector lies in the same half-plane as the first one.

Cross product of vectors - a vector in three-dimensional space perpendicular to both vectors, equal in length to the oriented area of ​​the parallelogram built on these vectors. The product of the lengths of the vectors by the sine of the angle between them, and the sign of this sine depends on the order of the operands:   alpha\) 

If calculated using coordinates:
\(a\ x\ b = x_1 \cdot y_2 + x_2 \cdot y_1\),
where x1, y1, x2, y2 - coordinates of the first and second vector, respectively, allows you to determine which side of the line on which the first vector lies, the second vector is located. Also allows you to find the oriented area of ​​triangles and parallelograms.

The rotation of a vector is performed using the black magic of the secret adepts of Lobachevsky geometry.
To rotate a vector by \(\alpha\) counterclockwise (\(\alpha <= 2 \cdot \ pi\), get used to the angles in radians), you need to multiply the vector by this matrix:
\(\begin{bmatrix} \cos \alpha & -sin \alpha \\ \sin \alpha & cos \alpha \end{bmatrix}\)< /p>

What does it mean to multiply a vector by a matrix? Let's say the coordinates of our vector are x and y, then the product of this vector and our matrix will be equal to the vector with the coordinates x' and y':
\(x' = x \cdot cos \alpha - y \cdot sin \alpha \\ y' = x \cdot sin \alpha + y \cdot cos\alpha\)

So we get a new vector of exactly the same length, but already rotated by angle A counterclockwise.

Training problem

Clock change

The line can be defined in 5 different ways:
1) equation \( y = kx + b\); the very first equation of a straight line that is taught in school is convenient for building and calculating manually, but its use in a program is very inconvenient;
2) by 2 points lying on it - actually quite convenient, but has a rather narrow application;
3) by the normal vector of a straight line and a point - the normal vector to a straight line is a vector perpendicular to it, more about it below;
4) along the directing vector of the straight line and the point - the directing vector is a vector lying on the straight line and perpendicular to the normal vector (well, logical), about it below;
5) equation of a straight line \(ax + by + c = 0\); the classical equation of a straight line, in most cases the most universal. Now about him.

Coordinates of the normal vector of such a line: \((a; b)\) or \( (-a; -b)\).

Coordinates of the direction vector of such a line: \((-b; a)\) or \ ((b; -a)\).

Lines are parallel if:
\({a1 \over b1} = {a2 \over b2}\).

Distance from a point to a line (be careful: the distance can be negative, it all depends on which side of the line the point lies):
\({(a \cdot x_1 + b \cdot y_1 + c) \over \sqrt{a^2 + b^2}}\),
where x1, y1 are the coordinates of the point.

Constructing a line from a normal vector and a point, or a direction vector and a point, comes down to building a line from 2 points, so let's look at it (it is also the most commonly used).< /p>

If x1, y1, x 2, y2 - coordinates of the first and second points respectively, then

\(a = y_1 - y_2\)

\(b = x_2 - x_1\)

\(c = x_1 \cdot y_2 - x_2 \cdot y_1\)

Training problem

Lazy Vasya and the release of Half-Life 3

Intersection

Point of intersection of lines

a1, b1, c1 - coefficients of the first line,
a2, b2, c2 - coefficients of the second line,
x, y - intersection point.

\(x = {-(c1 \cdot b2 - c2 \cdot b1) \over (a1 \cdot b2 - a2 \cdot b1)} \\ y = {-(a1 \ cdot c2 - a2 \cdot c1) \over (a1 \cdot b2 - a2 \cdot b1)} \)

We already know how to check lines for intersection (they are not parallel), and find their point of intersection.

Now let's learn how to do this with segments. 

First, let's learn how to simply check them for intersection.

Segments intersect if the ends of one are on opposite sides of the other and vice versa (this is easily checked by the cross product). The only case when this will not work - the segments lie on one straight line. For it, you need to check for the intersection of the so-called. bounding box (bounding box of the segment) - check for the intersection of the projection of the segments on the X and Y.

axes.

Now that we know how to check segments for intersection, let's learn how to find the point (or segment) of their intersection:
- if they do not intersect, then it is clear that such a point does not exist;
- otherwise, we will construct straight lines on which these segments lie.

If they are parallel, then the segments lie on the same line, and we need to find the intersection segment - from the maximum of the left borders of the segments to the minimum of the right borders (the point is less than the other point, if it is to the left, in case of equality X-coordinates - if it is lower).

If the lines are not parallel, then find the point of their intersection and return it.

Training problem

Pickup Master