反演变换

计算几何 / inverse

本地源文件：docs/geometry__inverse.md

反演变换

引入

反演变换适用于题目中存在多个圆/直线之间的相切关系的情况．利用反演变换的性质，在反演空间求解问题，可以大幅简化计算．

定义

给定反演中心点 𝑂O 和反演半径 𝑅R．若平面上点 𝑃P 和 𝑃′P′ 满足：

  • 点 𝑃′P′ 在射线 ⟶𝑂𝑃OP→ 上
  • |𝑂𝑃| ⋅|𝑂𝑃′| =𝑅2|OP|⋅|OP′|=R2

则称点 𝑃P 和点 𝑃′P′ 互为反演点．

解释

下图所示即为平面上一点 𝑃P 的反演：

Inv1

性质

  1. 圆 𝑂O 外的点的反演点在圆 𝑂O 内，反之亦然；圆 𝑂O 上的点的反演点为其自身．
  1. 不过点 𝑂O 的圆 𝐴A，其反演图形也是不过点 𝑂O 的圆．

Inv2

  • 记圆 𝐴A 半径为 𝑟1r1，其反演图形圆 𝐵B 半径为 𝑟2r2，则有：

𝑟2=12(1|𝑂𝐴|−𝑟1−1|𝑂𝐴|+𝑟1)𝑅2r2=12(1|OA|−r1−1|OA|+r1)R2 证明

Inv3

根据反演变换定义：

|𝑂𝐶|⋅|𝑂𝐶′|=(|𝑂𝐴|+𝑟1)⋅(|𝑂𝐵|−𝑟2)=𝑅2|𝑂𝐷|⋅|𝑂𝐷′|=(|𝑂𝐴|−𝑟1)⋅(|𝑂𝐵|+𝑟2)=𝑅2|OC|⋅|OC′|=(|OA|+r1)⋅(|OB|−r2)=R2|OD|⋅|OD′|=(|OA|−r1)⋅(|OB|+r2)=R2

消掉 |𝑂𝐵||OB|，解方程即可．

  • 记点 𝑂O 坐标为 (𝑥0,𝑦0)(x0,y0)，点 𝐴A 坐标为 𝑥1,𝑦1x1,y1，点 𝐵B 坐标为 𝑥2,𝑦2x2,y2，则有：

𝑥2=𝑥0+|𝑂𝐵||𝑂𝐴|(𝑥1−𝑥0)𝑦2=𝑦0+|𝑂𝐵||𝑂𝐴|(𝑦1−𝑦0)x2=x0+|OB||OA|(x1−x0)y2=y0+|OB||OA|(y1−y0)

其中 |𝑂𝐵||OB| 可在上述求 𝑟2r2 的过程中计算得到．

  1. 过点 𝑂O 的圆 𝐴A，其反演图形是不过点 𝑂O 的直线．因为圆 𝐴A 上无限接近点 𝑂O 的一点，其反演点离点 𝑂O 无限远．

Inv4

  1. 两个图形相切且存在不为点 𝑂O 的切点，则他们的反演图形也相切．

例题

「ICPC 2013 杭州赛区」Problem of Apollonius

题目大意

求过两圆外一点，且与两圆相切的所有的圆．

解法

首先考虑解析几何解法，似乎很难求解．

考虑以需要经过的点为反演中心进行反演（反演半径任意），所求的圆的反演图形是一条直线（应用性质 33），且与题目给出两圆的反演图形（性质 22）相切（性质 44）．

于是题目经过反演变换后转变为：求两圆的所有公切线．

求出公切线后，反演回原平面即可．

示例代码

---|---

## 练习

[「ICPC 2017 南宁赛区网络赛」Finding the Radius for an Inserted Circle](https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-A1283)

[「CCPC 2017 网络赛」The Designer](https://acm.hdu.edu.cn/showproblem.php?pid=6158)

## 参考资料与拓展阅读

  * [Inversive geometry - Wikipedia](https://en.wikipedia.org/wiki/Inversive_geometry)

  * [圆的反演变换 - ACdreamers 的博客](https://blog.csdn.net/acdreamers/article/details/16966369)

* * *

>  __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/geometry/inverse.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/geometry/inverse.md "edit.link.title")
>  __本页面贡献者：[Enter-tainer](https://github.com/Enter-tainer), [H-J-Granger](https://github.com/H-J-Granger), [StudyingFather](https://github.com/StudyingFather), [countercurrent-time](https://github.com/countercurrent-time), [hyp1231](https://github.com/hyp1231), [NachtgeistW](https://github.com/NachtgeistW), [Ir1d](https://github.com/Ir1d), [Tiphereth-A](https://github.com/Tiphereth-A), [383494](https://github.com/383494), [AngelKitty](https://github.com/AngelKitty), [CCXXXI](https://github.com/CCXXXI), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [Early0v0](https://github.com/Early0v0), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [HeRaNO](https://github.com/HeRaNO), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [sshwy](https://github.com/sshwy), [Suyun514](mailto:suyun514@qq.com), [weiyong1024](https://github.com/weiyong1024), [GavinZhengOI](https://github.com/GavinZhengOI), [Gesrua](https://github.com/Gesrua), [Ghost-LZW](https://github.com/Ghost-LZW), [iamtwz](https://github.com/iamtwz), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [lychees](https://github.com/lychees), [Menci](https://github.com/Menci), [Peanut-Tang](https://github.com/Peanut-Tang), [SukkaW](https://github.com/SukkaW)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用