

二维计算几何基础

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.

Prerequisite

If you don’t know about the following:

• Geometry basics
• Cartesian coordinate system
• Vector (including vector product)
• Polar coordinate and polar coordinate system

Please read the vector and polar coordinate first.

Record of graphs

Point

In the plane rectangular coordinate system, points are represented by coordinates, such as $(5,2)$ , $(-1,0)$ and so on.

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.

Vector

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

Line and ray

Generally, when solving math problems, we use an analytic formula to represent a straight line. There are general formula $Ax+By+C=0$ , slope-intercept formula $y=kx+b$ , and intercept formula $\frac{x}{a}+\frac{y}{b}= 1$ ... Which one to choose?

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.

Line segment

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.

Polygen

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.

Curve

For some special curves, such as function images, we generally record their analytical expressions. For a circle, just record its center and radius directly.

Basic formula

The law of sines

In triangle $\triangle \text{ABC}$ , if the opposite sides of angle $A,B,C$ are $a,b,c$ , then has:

$$\frac{a}{\sin A}=\frac{b}{\sin B}=\frac{c}{\sin C}=2R$$

Among them, $R$ is the radius of the circumcircle of $\triangle \text{ABC}$ .

Law of cosines

In the triangle $\triangle \text{ABC}$ , if the opposite sides of the angles $A,B,C$ are $a,b,c$ respectively, then:

$$\begin{aligned} a^2&=b^2+c^2-2bc\cos A\\ b^2&=a^2+c^2-2ac\cos B\\ c^2&=a^2+b^2-2ab\cos C \end{aligned}$$

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.

Basic operations

Determine which side of the line a point is

We have a point $P$ on the line and the direction vector $\mathbf v$ of the line. We want to know which side of the line $Q$ is on.

We use the property of the vector product to calculate $\overrightarrow {PQ}\times \mathbf v$ . If the vector product is negative, then $Q$ is above the line; If the vector product is $0$ , then $Q$ is on the line, if the vector product is positive, then $Q$ is below the line.

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 $a,b$ intersect, the two end points of the $b$ line segment must be distributed on the two ends of the line where the $a$ line segment is located; similarly, the two end points of the $a$ line segment must be distributed on the line where the $b$ line segment is on both ends. We can directly judge the position relationship between the two end points of a line segment relative to the straight line where the other line segment is located. If they are different, the two line segments intersect, otherwise, they do not intersect. We can use the knowledge in 3.1 to help us judge the positional relationship between the line and the point.

This is the straddle experiment. If for two line segments $a,b$ , the two end points of the $b$ line segment are distributed on both sides of the line where the $a$ line segment is located, and the two endpoints of $a$ line segment are distributed on both sides of the straight line where the $b$ line segment is located. Let's say that the two line segments $a,b$ have passed the straddle experiment, that is, the two line segments intersect.

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 $0$ , the point is outside the curve. This algorithm is also called Nonzero-rule.

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 $0$ , then the point is outside the polygon, otherwise it is inside the polygon.

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 $0$ . Further, if the two straight lines are parallel and pass the same point, the two straight lines overlap.

Then, the problem is simplified as we have straight lines $AB,CD$ intersecting at one point, and want to find the intersection point $E$ .

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 $l$ , and then translate this point along the direction vector $l$ unit length is sufficient.

Consider constructing a triangle, using the law of sine to solve $l$ , you can use the vector product to construct the law of sine.

As can be seen from the above figure, $|\mathbf a\times \mathbf b|=|\mathbf a||\mathbf b|\sin \beta$ ， $|\mathbf u\times \mathbf b|=|\mathbf u||\mathbf b|\sin \theta$ .

thus we calculate the quotient:

$$T=\frac{|\mathbf u\times \mathbf b|}{|\mathbf a\times \mathbf b|}=\frac{|\mathbf u|\sin \theta}{|\mathbf a|\sin \beta}$$

It can be seen easily that, $|\frac{|\mathbf u|\sin \theta}{\sin \beta}|=l$ . If the value of the absolute value internal expression is positive, it means translation along the $\mathbf a$ direction, otherwise it is the opposite direction.

At the same time, we directly multiply $T$ by $\mathbf a$ , and the unit vector of the straight line will automatically appear, and no other elimination operations are required.

So, just add the point $P$ to $T\mathbf a$ to get the intersection 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 $p_1,p_2,\cdots ,p_n$ , and then choose an auxiliary point $O$ , remember the vector $\mathbf v_i=p_i-O$ , then the area of the polygon $S$ can be expressed as:

$$S=\frac{1}{2}|\sum_{i=1}^n \mathbf v_i\times \mathbf v_{i\bmod n+1}|$$

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.

Polar order

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

There are $n$ points in the plane, with three colors, and the color of each point is one of the three. Find the logarithm of disjoint tricolor triangles. $6\le n\le 3000$ .

Problem solution

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 $O$ , take this point as the extreme point, and the straight line passing this point and parallel to the $x$ axis as the polar axis, establish a polar coordinate system, and sort the remaining points from smallest to largest polar angle. Then count the number of each point above and below the polar axis.

Then enumerate the common tangent according to the points, remember that the enumerated point is $P$ , and the common tangent is the polar axis at the beginning. Now start statistics. There must be a common tangent crossing the point $O$ and the point $P$ . Because the common tangent line does not intersect the triangle, one party chooses the point above the common tangent line, and the other party must choose the point below it. Then use the principle of multiplication to count the number of plans.

After counting the common tangent, the point $P$ must have changed its up and down position relative to the common tangent, and other points will not move, so only its position information should be changed.

In this way, it can be found that the same pair of triangles is finally counted $4$ times, that is, the same common tangent will be enumerated twice, and the final answer should be divided by $4$ .

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 $O(n^2\log n)$ .

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.

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论