We limit the scope of the geometric problems within the two-dimensional plane, therefore two-dimensional computational geometry is used.
Want to solve plane geometry problems using computers? Well, actually we are not using computers to calculate the geometry problems from math books, but to solve some more complicated geometry-related problems.
In order to solve complex and abstract problems, we must choose appropriate research methods. For the computer, showing it geometric figures seems a bit far fetched.
We can put the graph to be studied in a rectangular coordinate system or a polar coordinate system, which will be much easier to solve.
If you don’t know about the following:
- Geometry basics
- Cartesian coordinate system
- Vector (including vector product)
- Polar coordinate and polar coordinate system
Record of graphs¶
In the plane rectangular coordinate system, points are represented by coordinates, such as
We can record its horizontal and vertical coordinates. Use
pair or open structure to record.
In the polar coordinate system, it can be represented using polar coordinates. Record its polar diameter and polar angle.
Since the vector coordinate is the same as the point coordinate, you only need to store the vector like a point (of course a point is not a vector).
In the polar coordinate system, it is the same like points.
Line and ray¶
Generally, when solving math problems, we use an analytic formula to represent a straight line. There are general formula
These formulas all have the same ending - substituting into the solution equation for evaluation.
However, solving equations seems really annoying. Is there a better way?
Consider the fact that we just want to know where this line is and its degree of inclination. So using a point on the straight line to roughly determine the position first, and then using a vector to indicate its inclination. Well, the straight line is already determined.
So what we record is: a point on the line and the direction vector of the line.
The line segment is easy to record: just record the left and right end points.
In the polar coordinate system, it is a bit Inconvenient to record the line, so most straight-line problems are solved in the plane rectangular coordinate system.
Open the array to record each vertex of the polygon in a certain order.
In particular, if the sides of the rectangle are parallel to a certain coordinate axis, we only record the vertices of the lower left corner and the upper right corner.
For some special curves, such as function images, we generally record their analytical expressions. For a circle, just record its center and radius directly.
The law of sines¶
Law of cosines¶
In the triangle
The proof of the above formula is omitted. All of them are from section 5, compulsory contents of high school mathematics of PEP edition A.
Determine which side of the line a point is¶
We have a point
We use the property of the vector product to calculate
You can draw a picture and feel it using the right hand rule.
Rapid rejection experiment and straddle experiment¶
We now want to determine whether the two line segments intersect.
First, we will judge some special cases. If the two line segments are parallel, naturally they cannot intersect. In this case, it is enough to judge whether the slopes of the straight lines where the line segments are located are equal.
Of course, if the two line segments overlap or partially overlap, you only need to determine whether there is a three-point collinear situation.
If the intersection of the two line segments is the end point of one of the line segments, it is enough to still judge whether there are three points collinear.
There are also situations that are obviously disjoint, which we verbally call "the two line segments are too far apart." But what is "far away" and how to judge it?
It is stipulated that the "area of a line segment" is the area occupied by a rectangle whose sides are parallel to a certain coordinate axis with this line segment as the diagonal, then it can be found that if the two line segments have no common area, the two The line segments must not intersect.
For example, there are the following two line segments:
The area they occupy is like this:
Therefore, it can be quickly determined that the two line segments do not intersect.
This is the rapid rejection experiment. The above situation is called failed the rapid rejection test.
Failing the rapid rejection experiment is a sufficient and unnecessary condition that the two line segments have no intersection, and we need further judgment.
Because the two line segments
This is the straddle experiment. If for two line segments
Note that when two line segments are collinear but do not intersect, the straddle experiment can also be passed. Therefore, an accurate judgment needs to be combined with the rapid rejection experiment.
Determine whether a point is inside an arbitrary polygon¶
In computational geometry, this problem is called PIP problem, and there are already some mature solutions. We are going to introduce them in turn.
Ray casting algorithm¶
You can see the most original ideas here.
We first judge some special cases, such as "this point is too far from the polygon". Consider a smallest rectangle that can completely cover the polygon. If the point is not in the rectangle, then the point must not be in the polygon. Such a rectangle is easy to find. You only need to know the minimum and maximum values of the abscissa and ordinate of the polygon. The two sets of coordinates are combined into four points, which are the four vertices of this rectangle.
There are also points on a certain side or vertex of the polygon, which can be very easy to judge.
We consider to draw a ray with this point as the end point. If this ray has an odd number of intersections with the polygon, then the point is inside the polygon, otherwise the point is outside. We abbreviate it as odd inside even outside. This algorithm is also called the Even-odd rule.
Because of jordan curve theorem, we know that each time this ray intersects an edge of the polygon, it switches the relationship between the inside and outside of the polygon, so counting the number of the parity of intersection is enough.
How to take such rays? The slope of the line where the ray is located can be randomly selected, and it is recommended to be an irrational number to avoid the ray coincides with a certain side of the polygon.
In the original code, the last point in the array that records the polygon is used as a point on the ray. In this way, if a ray crosses a certain side or vertex of the polygon, it can be specified that the ray passes through the same side of the ray. Just do a straddle experiment.
Winding number algorithm¶
The winding number is a mathematical concept, and it is the total number of times a closed curve in the plane goes around the point counterclockwise. It is easy to find that when the number of revolutions is equal to
How to calculate it? We connect this point with all the vertices of the polygon and calculate the sum of the angles between two adjacent sides. Note that the included angle here is directed. If the angle sum is
Find the intersection of two straight lines¶
First of all, we need to determine the intersection of two straight lines, just to judge whether the direction vectors of the two straight lines are parallel. If the direction vectors are parallel, then the two straight lines are parallel, and the number of intersection points is
Then, the problem is simplified as we have straight lines
If two lines intersect, there is only one intersection point. We record a point on the line and its direction vector, so we only need to know the distance between this point and the intersection point
Consider constructing a triangle, using the law of sine to solve
As can be seen from the above figure,
thus we calculate the quotient:
It can be seen easily that,
At the same time, we directly multiply
So, just add the point
Find the perimeter and area of any polygon¶
Find the perimeter of any polygon¶
Calculate directly, simplicity is a virtue.
Find the area of any polygon¶
Considering the geometric meaning of the modulus of the vector product, we can use the vector product to solve this problem.
Mark the points on the polygon counterclockwise as
Circle & straight line related¶
Find the intersection of a line and a circle¶
First judge the positional relationship between the straight line and the circle. If the line is separated from the circle, there is no point of intersection. If the line is tangent, the tangent line can be used to find the line where the tangent point and the radius are, and then it is transformed into finding the point of intersection of two straight lines.
If there are two intersections, you can use the pythagorean theorem to find the midpoint of the two intersections, and then add the half-chord along the straight line.
Find the intersection of two circles¶
First of all, we judge the positional relationship of the two circles. If they are outside or inside, there is no intersection. If they are tangent, the direction vector connecting the two circles can be calculated. Then use the radius of the two circles to calculate the translation distance. Finally, the center of the circle is along this direction vector can be translated.
If two circles intersect, there must be two intersection points, and they are symmetrical about the line connecting the centers of the two circles. Therefore, only one intersection is explained below, and the other intersection can be found in a similar way.
We first connect the center of a circle with the intersection point, and find the angle formed by the line between the two centers of the circle and the line. In this way, rotating the direction vector connecting the two circles by this angle is the direction vector of the radius formed by connecting the center of the circle and the intersection.
Finally, it is the same routine - the center of the circle is transitioned by the radius length along the direction vector.
Generally speaking, this kind of problem needs to enumerate a polar point first, then calculate the polar coordinates of other points, and solve the problem in the order of polar angles in the polar coordinate system.
Sample question "JOI Spring Camp 2014 Day4" Constellation of two people¶
If two triangles do not intersect, then two internal common tangents can be made. If they intersect or contain, the internal common tangent cannot be made. The common tangent of a triangle can be analogous to the common tangent of a circle.
First enumerate an origin point, denote it as
Then enumerate the common tangent according to the points, remember that the enumerated point is
After counting the common tangent, the point
In this way, it can be found that the same pair of triangles is finally counted
To analyze the time complexity of the algorithm: we enumerate an origin, and then sort the remaining points for each origin and count them linearly. So the time complexity is
Notes on coding¶
Since computational geometry often performs floating-point calculations of
double type, it brings problems about accuracy and time.
For some problems, such as finding the area of a triangle whose point coordinates are all integers, you can use its particularity to perform pure integer calculations to avoid using floating-point numbers to affect accuracy.
Since floating-point calculations are slower than integer calculations, you need to pay attention to the effect on time brought by program's constant factor.
buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.