计算几何 I. 极角

参考资料

1. hankcs.com: POJ 1981 Circle and Points 题解
2. aswmtjdsj: POJ 1981 Circle and Points 【定长圆覆盖最多点问题】
3. zxy_snow: 极角排序

概念

In mathematics, the polar coordinate system is a two-dimensional coordinate system in which each point on a plane is determined by a distance from a reference point and an angle from a reference direction.

The reference point (analogous to the origin of a Cartesian system) is called the pole, and the ray from the pole in the reference direction is the polar axis. The distance from the pole is called the radial coordinate or radius, and the angle is called the angular coordinate, polar angle, or azimuth.
SOURCE

计算极角

在C++里，可用定义于<cmath>中的std::atan2函数计算极角。

std::atan2(y, x) computes the arc tangent of y/x using the signs of arguments to determine the correct quadrant.
If no errors occur, the arc tangent of y/x in the range [-π, +π] radians, is returned.
SOURCE

有的资料（例如参考资料1）说 atan2 的返回值范围是 $(-\pi, \pi]$，这是不准确的。另外，对于极角排序而言，某个极角是写成 $-\pi$ 还是写成 $\pi$ 并没有区别，因为这两个值恰是区间的两端。

用两个极角表示的一段圆弧

在一些计算几何问题中，我们需要求同一个圆上的若干段弧的交集或并集。这个问题类似于在直线上求区间的并或交。我们可以用弧的两端点对圆心的极角来表示一段圆弧。如果直接用 atan2 来求极角，会出现两个问题：

1. 实际问题中一般难以判断哪个点是起点，哪个点是终点（这里所谓“弧的起点、终点”对应于直线上区间的左、右端点）
2. atan2 求出的极角并不能正确地表示「跨过极角为 $\pi$ 的射线（极轴的反向）」的弧

为了解决问题1，我们不直接求弧端点的极角，转而求「弧的中点」对圆心的极角，再求出弧的圆心角的大小（一般求圆心角的一半更为方便），这样便无需考虑起点终点的问题，自然就将弧表示成区间了且区间长度就是弧的圆心角大小。

为了解决问题2，若所求出的「弧的中点的圆心角」为负值，就将其加上 $2\pi$。
（注意：参考资料2中的解法，并没有处理问题2，是有bug的）

这两个技巧都比较巧妙，请读者仔细体会。

习题

• POJ #1981
• hihoCoder #1064

极角排序

见参考资料3。