awdec's Blog

圆基础

圆的表示：圆心、半径
圆的周长： $C = 2 π r$
圆的面积： $S = π r^{2}$

圆的关系问题

点与圆的关系

点在圆外
点在圆上
点在圆内

判定方法：点到圆心距离（平方）与圆的半径（平方）比较。

无精度误差。

直线与圆的关系

相离
相切
相交

判定方法：圆心到直线距离与圆的半径比较

可以做到无精度误差。

圆与圆的关系

令两圆半径分别为 $r_{1}$ 和 $r_{2}$ ，两圆圆心的距离为 $d$ 。

相同： $r_{1} = r_{2}$ 且 $d = 0$ 。
相离： $d > r_{1} + r_{2}$
外切： $d = r_{1} + r_{2}$
相交： $| r_{1} - r_{2} | < d < r_{1} + r_{2}$
内切： $d = | r_{1} - r_{2} |$
内含： $d < | r_{1} - r_{2} |$

交集问题

直线与圆的交点

前提：直线与圆不相离

直线： ${P, \vec{v}}$

圆： ${C, r}$

设圆心到直线距离为 $d$ ，投影为 $C^{'}$ ，则：交点： $\vec{O C^{'}} \pm \frac{\sqrt{r^{2} - d^{2}}}{| \vec{v} |} \vec{v}$ 。

圆与圆交点

前提：两圆不相同、不相离、不内含

两圆圆心连线与一圆心到交点连线夹角 $α$ 。

根据余弦定理： $\cos α = \frac{r_{1}^{2} + d^{2} - r_{2}^{2}}{2 r_{1} d}, \sin α = \sqrt{1 - \cos^{2} α}$

将两圆心连线对应向量进行伸缩旋转。

圆与多边形面积交

从圆心将多边形剖分成若干三角形，求三角形与圆的面积交。

多个圆的面积并

对于极角在 $θ_{l}$ 到 $θ_{r}$ 之间的一段圆弧。

$2 S = x_{0} r (\sin θ_{r} - \sin θ_{l}) - y_{0} r (\cos θ_{r} - \cos θ_{l}) + r^{2} (θ_{r} - θ_{l})$ 。

时间复杂度： $O (n^{2} \log n)$ 。

切线问题

过圆外一点圆的切线

$\cos α = \frac{r}{d}$
向量伸缩、旋转

两圆的公切线

相离： $4$ 条
外切： $3$ 条
相交： $2$ 条
内切： $1$ 条
内含： $0$ 条

外公切线

$\cos α = \frac{r_{1} - r_{2}}{d}$

内公切线

$\cos α = \frac{r_{1} + r_{2}}{d}$

圆的反演

给定反演中心点 $O$ 和反演半径 $R$ ，若平面上点 $P$ 和 $P^{'}$ 满足：

点 $P^{'}$ 在射线 $O P$ 上
$| \vec{O P} | \times | \vec{O P^{'}} | = R^{2}$

则称点 $P$ 和点 $P^{'}$ 互为反演点。

性质：

圆外的点的反演点在圆内，反之亦然
圆上的点的反演点为其自身
不过点 $O$ 的圆，其反演图形也是不过点 $O$ 的圆
过点 $O$ 的圆，其反演图形是不过点 $O$ 的直线
两个图形相切，则它们的反演图形也相切

最小圆覆盖

问题描述：给定平面上 $n$ 个点，求一个半径最小的圆，能覆盖所有的点。

引理：过三个不共线的点可以唯一确定一个圆。

定理：如果点 $p$ 不在点集 $S$ 的最小圆覆盖圆内，那么它一定在 ${p} \cup S$ 的最小覆盖圆上，即最小覆盖圆一定经过点 $p$ 。

时间复杂度： $O (n)$ 。

圆基础 ​

圆的关系问题 ​

点与圆的关系 ​

直线与圆的关系 ​

圆与圆的关系 ​

交集问题 ​

直线与圆的交点 ​

圆与圆交点 ​

圆与多边形面积交 ​

多个圆的面积并 ​

切线问题 ​

过圆外一点圆的切线 ​

两圆的公切线 ​

外公切线 ​

内公切线 ​

圆的反演 ​

最小圆覆盖 ​

圆基础