Basics of Two-Dimensional Computational Geometry

We restrict the geometric problems to be solved here to the two-dimensional plane, which brings in the basic knowledge of two-dimensional computational geometry. In studying these problems, figures are usually placed in a Cartesian or polar coordinate system, making them much easier to work with.

Prerequisites

If you are not familiar with:

• Basic geometry
• The Cartesian coordinate system
• Vectors (including vector products)
• Polar coordinates and the polar coordinate system

please read Vectors and Polar coordinates first.

Representing figures

Points

In the Cartesian coordinate system, a point is represented by its horizontal and vertical coordinates, such as $(5,2)$ and $(-1,0)$. Since coordinates are ordered pairs, std::pair can be used to store them, or a struct can be defined.

In the polar coordinate system, a point is represented by its radius and polar angle; it can be stored in the same way as in Cartesian coordinates.

Vectors

Since the coordinate representation of a vector is the same as that of a point, a vector only needs to be stored like a point.

The same applies in the polar coordinate system.

Lines

Representing a line in polar coordinates is relatively difficult, so we discuss only the Cartesian-coordinate case.

Lines and rays

When solving mathematical problems, we generally use an equation to represent a line. A line can be written in several forms, including the general form $Ax+By+C=0$, the slope-intercept form $y=kx+b$, and the intercept form $\dfrac{x}{a}+\dfrac{y}{b}=1$, but these forms ultimately serve the purpose of obtaining an analytic solution to an equation. In computational geometry, representing a line with an equation can make a problem harder to solve.

In computational geometry, a line is usually represented by a point on the line and a direction vector, while a ray is represented by its endpoint and a direction vector. A direction vector is a nonzero vector parallel to the line, and is usually chosen to be a unit vector. There are two unit vectors parallel to a line, and either may be chosen according to the problem; for a ray, the direction vector is usually the one whose direction agrees with the ray's extension.

Line segments

To record a line segment, it is enough to record its two endpoints.

Polygons

Store the vertices of a polygon in an array in a fixed order. For a simple polygon, the vertices are generally recorded in clockwise or counterclockwise order.

As a special case, if all sides of a rectangle are parallel to the coordinate axes, it is enough to record the two vertices on one of its diagonals.

Curved figures

Some special curves, such as function graphs, are generally recorded by their equations. For a circle, simply record its center and radius.

Basic formulas

Law of sines

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

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

Here $R$ is the circumradius of $\triangle \text{ABC}$.

Law of cosines

In $\triangle \text{ABC}$, if the sides opposite angles $A,B,C$ are respectively $a,b,c$, 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 these formulas is omitted. They are all covered in the compulsory second volume of the standard high-school mathematics curriculum (the older textbook used compulsory volume five).

Basic operations

Determining which side of a line contains a point

Suppose we have a point $P$ on a line and the line's direction vector $\mathbf v$, and want to know which side of the line a point $Q$ lies on. Here, which side means relative to the direction vector: make the judgment while facing in the direction indicated by the vector.

Using the properties of the vector product, calculate $\mathbf v\times \overrightarrow {PQ}$. According to the right-hand rule, if the vector product is negative, $Q$ is on the right side of the line; if the vector product is $0$, $Q$ is on the line; if the vector product is positive, $Q$ is on the left side of the line.

Quick rejection and straddling tests

We now want to determine whether two line segments intersect.

First handle some special cases. If the two line segments are parallel, they naturally cannot intersect. This can be checked by determining whether the slopes of the lines containing the segments are equal.

If the two line segments coincide or partially overlap, or if their intersection is an endpoint of one of the segments, it is enough to check whether three points are collinear.

There are also some obviously disjoint cases, informally described as the two line segments being too far apart. Define the region of a line segment as the region occupied by the rectangle whose diagonal is that segment and whose sides are parallel to the coordinate axes. It is then clear that if two line segments have no common region, they cannot intersect.

For example, consider the following two line segments:

Their occupied regions look like this:

Thus we can quickly determine that these two line segments do not intersect.

This is the quick rejection test. The situation above is called failing the quick rejection test.

Failing the quick rejection test is a sufficient but not necessary condition for two line segments to have no intersection, so we need to make a further determination.

If two line segments $a,b$ intersect, the two endpoints of segment $b$ must lie on opposite sides of the line containing segment $a$; similarly, the two endpoints of segment $a$ must lie on opposite sides of the line containing segment $b$. We can directly determine the positions of the two endpoints of one line segment relative to the line containing the other: if the positions differ, the two line segments intersect; otherwise, they do not. As described in the previous section, the positional relationship between a line and a point can be determined using a vector product.

This is the straddling test. For two line segments $a,b$, if the two endpoints of segment $b$ lie on opposite sides of the line containing segment $a$, and the two endpoints of segment $a$ lie on opposite sides of the line containing segment $b$, then we say that the two line segments $a,b$ pass the straddling test, that is, they intersect.

Note that two collinear but non-intersecting line segments can also pass the straddling test, so an accurate determination still requires combining it with the quick rejection test.

Determining whether a point lies inside a polygon

In computational geometry, this problem is called the PIP problem, and several established methods are available. They are introduced below in turn.

Ray casting algorithm

The most original version of the idea can be found here.

First handle some special cases, such as the point being too far from the polygon. Similar to determining whether two line segments intersect, consider the smallest rectangle that completely contains the polygon. If the point is outside this rectangle, it certainly is not inside the polygon. This rectangle is easy to find: take the minimum and maximum x- and y-coordinates of the polygon, and pair them to obtain the four vertices of the rectangle.

It is likewise very easy to determine whether a point lies on an edge or vertex of the polygon. For each edge, check whether the point lies on the edge or at one of its vertices.

Draw a ray from the point as its endpoint. If this ray has an odd number of intersections with the polygon, the point is inside the polygon; otherwise, it is outside. We abbreviate this as odd inside, even outside. This algorithm is also called the even-odd rule.

By the Jordan curve theorem, we know that each time the ray intersects an edge of the polygon, its inside/outside relationship with the polygon switches once, so it is enough to count the parity of the number of intersections.

For the selected ray, the slope of the line containing it can be chosen randomly. An irrational number is recommended to avoid the ray coinciding with an edge of the polygon.

In the original code, the last point in the array recording the polygon is used as a point on the ray. During counting, if the ray passes through an edge or vertex of the polygon, we can stipulate that the point passed by the ray lies on the same side of the ray, and then perform the straddling test.

Note

The ray casting algorithm applies only to simple polygons. It does not apply to polygons with self-intersecting edges, because the Jordan curve theorem does not apply, so containment cannot be determined.

Winding number algorithm

The winding number is a mathematical concept: it is the total number of times a closed curve in the plane winds counterclockwise around a point. It is easy to see that when the winding number is $0$, the point is outside the curve. This algorithm is also called the nonzero rule.

How is it calculated? Connect the point to every vertex of the polygon and calculate the sum of the angles between adjacent sides. Note that these angles are oriented. If the sum of the angles is $0$, the point is outside the polygon; otherwise, it is inside.

Finding the intersection of two lines

First, we need to determine whether the two lines intersect; it is enough to check whether their direction vectors are parallel. If the direction vectors are parallel, the two lines are parallel and have $0$ intersection points. Furthermore, if two parallel lines pass through the same point, they coincide.

The problem is then reduced to two lines $AB,CD$ intersecting at a point, and finding the intersection point $E$.

If the two lines intersect, there is only one intersection point. We have recorded a point on the line and its direction vector, so we only need to know the distance $l$ from this point to the intersection, and then translate the point by $l$ units along the direction vector.

Consider constructing a triangle and use the law of sines to solve for $l$; the law of sines can be expressed using vector products.

As shown above, $|\mathbf a\times \mathbf b|=|\mathbf a||\mathbf b|\sin \beta$, $|\mathbf u\times \mathbf b|=|\mathbf u||\mathbf b|\sin \theta$.

Taking the quotient gives:

$$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 that $\left|\dfrac{|\mathbf u|\sin \theta}{\sin \beta}\right|=l$. If the expression inside the absolute value is positive, this represents a translation in the direction of $\mathbf a$; otherwise, it represents a translation in the opposite direction.

At the same time, multiplying $T$ directly by $\mathbf a$ automatically produces the unit vector of the line, so no other cancellation operation is needed.

Therefore, from point $B$, we only need to subtract $T\mathbf a$ to obtain the intersection point.

Finding the perimeter and area of an arbitrary polygon

Finding the perimeter of an arbitrary polygon

Calculate it directly; simplicity is a virtue.

Finding the area of an arbitrary polygon

Consider the geometric meaning of the magnitude of a vector product; we can use the vector product to calculate it.

Mark the points of the polygon counterclockwise as $p_1,p_2,\cdots ,p_n$, then choose an arbitrary auxiliary point $O$ and let the vector $\mathbf v_i=p_i-O$. The area $S$ of the polygon can be written as:

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

Circles and lines

Finding the intersection of a line and a circle

First determine the positional relationship between the line and the circle. If the line and circle are disjoint, there is no intersection. If they are tangent, we can use the tangent to find the point of tangency and the line containing the radius, then reduce the problem to finding the intersection of two lines.

If there are two intersection points, we can use the Pythagorean theorem to find their midpoint, and then add the half-chord length along the direction of the line.

Finding the intersection of two circles

First determine the positional relationship between the two circles. If they are externally disjoint or one contains the other, there is no intersection. If they are tangent, we can calculate the direction vector of the line joining the two centers, use the two radii to calculate the translation distance, and finally translate one center along this direction vector.

If the two circles intersect, there must be two intersection points, symmetric about the line joining the two centers. We explain only how to find one intersection point below; the other can be found similarly.

First connect the center of one circle to an intersection point, and find the angle between the line joining the two centers and this connection. Rotating the direction vector of the line joining the two centers by this angle gives the direction vector of the radius connecting the center to the intersection point. Translate the center by one radius in the direction of this vector to obtain an intersection point.

Polar-angle ordering

In general, problems of this kind require first enumerating a pole, then calculating the polar coordinates of the other points, and solving the problem in order of polar angle.

“JOISC 2014 Day 4” Constellation of Two People

There are $n$ points in the plane, with three colors, and each point has one of the three colors. Find the number of pairs of non-intersecting tricolored triangles. $6\le n\le 3000$.

Solution

If two triangles do not intersect, two internal common tangents can always be constructed; if they intersect or one contains the other, internal common tangents cannot be constructed. The common tangents of triangles can be understood by analogy with the common tangents of circles.

First enumerate an origin, denoted by $O$. Take this point as the pole, use the line through this point parallel to the $x$-axis as the polar axis, establish a polar coordinate system, and sort the remaining points by increasing polar angle. Then count the number of points of each color above and below the polar axis.

Then enumerate common tangents according to the points, and let the point currently being enumerated be $P$. Initially, the common tangent is the polar axis. Begin counting. There must be a common tangent passing through $O$ and $P$. Since the common tangent does not intersect either triangle, one side must choose points above the common tangent, and the other side must choose points below it. The multiplication principle can then be used to count the number of choices.

After counting, rotate the common tangent. Point $P$ must change its position from one side of the common tangent to the other, while all other points remain stationary, so only its positional information needs to be changed. It can then be seen that the same pair of triangles is counted $4$ times in total: the same common tangent is enumerated twice, so the final answer should be divided by $4$.

Let us analyze the complexity of the algorithm. We enumerate an origin, and then, for each origin, sort the remaining points and count them in linear time. Therefore, the time complexity is $O(n^2\log n)$.

Notes on writing code

Computational geometry frequently performs floating-point calculations with the double type, which introduces precision and time issues.

For some problems, such as finding the area of a triangle whose point coordinates are all integers, we can exploit this special property to perform the calculation entirely with integers, avoiding the effect of floating-point numbers on precision.

Since reading and calculating with floating-point numbers are both slower than with integers, we need to pay attention to the effect of the program's constant factors on the time limit.