Inversive Geometry

Introduction

Inversion transformation is applicable when the problem involves multiple tangent relationships among circles/lines. By solving the problem in the inversion space using the properties of inversion transformation, computations can be greatly simplified.

Definition

Given an inversion center point \(O\) and an inversion radius \(R\). If points \(P\) and \(P'\) on the plane satisfy:

• Point \(P'\) lies on the ray \(\overrightarrow{OP}\)
• \(|OP| \cdot |OP'| = R^2\)

Then points \(P\) and \(P'\) are called inverse points of each other.

Explanation

The following diagram shows the inversion of a point \(P\) on the plane:

Properties

1. The inverse point of a point outside circle \(O\) lies inside circle \(O\), and vice versa; the inverse point of a point on circle \(O\) is itself.

2. A circle \(A\) not passing through point \(O\) has an inverse figure that is also a circle not passing through point \(O\).

   

   • Let the radius of circle \(A\) be \(r_1\), and the radius of its inverse circle \(B\) be \(r_2\). Then:

     \[ r_2 = \frac{1}{2}\left(\frac{1}{|OA| - r_1} - \frac{1}{|OA| + r_1}\right) R^2 \]
   Proof

   

   According to the definition of inversion transformation:

   \[ \begin{aligned} |OC|\cdot|OC'| &= (|OA|+r_1)\cdot(|OB|-r_2) = R^2 \\ |OD|\cdot|OD'| &= (|OA|-r_1)\cdot(|OB|+r_2) = R^2 \end{aligned} \]

   Eliminate \(|OB|\) and solve the equations.

   • Let the coordinates of point \(O\) be \((x_0, y_0)\), point \(A\) be \((x_1, y_1)\), and point \(B\) be \((x_2, y_2)\). Then:

     \[ \begin{aligned} x_2 &= x_0 + \frac{|OB|}{|OA|} (x_1 - x_0) \\ y_2 &= y_0 + \frac{|OB|}{|OA|} (y_1 - y_0) \end{aligned} \]

     where \(|OB|\) can be calculated during the process of finding \(r_2\) above.

3. A circle \(A\) passing through point \(O\) has an inverse figure that is a line not passing through point \(O\). This is because a point on circle \(A\) infinitely close to point \(O\) has an inverse point infinitely far from point \(O\).

   

4. If two figures are tangent and the tangent point is not point \(O\), then their inverse figures are also tangent.

Example Problems

「ICPC 2013 Hangzhou Site」Problem of Apollonius

Problem Summary

Find all circles that pass through a given point outside two given circles and are tangent to both circles.

Solution

First consider an analytic geometry approach, which seems difficult to solve.

Consider performing an inversion with the point that must be passed through as the inversion center (inversion radius arbitrary). The inverse figure of the desired circle is a line (using property \(3\)), and it is tangent to the inverse figures of the two given circles (property \(2\)) (property \(4\)).

Thus, after inversion transformation, the problem becomes: find all common tangents of the two circles.

After finding the common tangents, invert them back to the original plane.

Sample Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

constexpr double EPS = 1e-8;   // precision constant
const double PI = acos(-1.0);  // π
constexpr int N = 4;

// Point definition
struct Point {
  double x, y;

  Point(double x = 0, double y = 0) : x(x), y(y) {}

  bool operator<(Point A) const { return x == A.x ? y < A.y : x < A.x; }
};

// Vector definition
using Vector = Point;

// Vector addition
Vector operator+(Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }

// Vector subtraction
Vector operator-(Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }

// Scalar multiplication
Vector operator*(Vector A, double p) { return Vector(A.x * p, A.y * p); }

// Scalar division
Vector operator/(Vector A, double p) { return Vector(A.x / p, A.y / p); }

// Comparison with zero
int dcmp(double x) {
  if (fabs(x) < EPS) return 0;
  return x < 0 ? -1 : 1;
}

// Dot product
double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; }

// Vector length
double Length(Vector A) { return sqrt(Dot(A, A)); }

// Cross product
double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }

// Projection of point onto line
Point GetLineProjection(Point P, Point A, Point B) {
  Vector v = B - A;
  return A + v * (Dot(v, P - A) / Dot(v, v));
}

// Circle
struct Circle {
  Point c;
  double r;

  Circle() : c(Point(0, 0)), r(0) {}

  Circle(Point c, double r = 0) : c(c), r(r) {}

  // Returns point coordinates given polar angle
  Point point(double a) { return Point(c.x + cos(a) * r, c.y + sin(a) * r); }
};

// Common tangents of two circles. Returns number of tangents, -1 means infinitely many.
// a[i] and b[i] are the tangent points on circle A and B for the i-th tangent.
int getTangents(Circle A, Circle B, Point* a, Point* b) {
  int cnt = 0;
  if (A.r < B.r) {
    swap(A, B);
    swap(a, b);
  }
  double d2 =
      (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
  double rdiff = A.r - B.r;
  double rsum = A.r + B.r;
  if (dcmp(d2 - rdiff * rdiff) < 0) return 0;  // contained

  double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
  if (dcmp(d2) == 0 && dcmp(A.r - B.r) == 0) return -1;  // infinitely many
  if (dcmp(d2 - rdiff * rdiff) == 0) {  // internally tangent, one tangent
    a[cnt] = A.point(base);
    b[cnt] = B.point(base);
    ++cnt;
    return 1;
  }
  // External common tangents
  double ang = acos(rdiff / sqrt(d2));
  a[cnt] = A.point(base + ang);
  b[cnt] = B.point(base + ang);
  ++cnt;
  a[cnt] = A.point(base - ang);
  b[cnt] = B.point(base - ang);
  ++cnt;
  if (dcmp(d2 - rsum * rsum) == 0) {  // one internal common tangent
    a[cnt] = A.point(base);
    b[cnt] = B.point(PI + base);
    ++cnt;
  } else if (dcmp(d2 - rsum * rsum) > 0) {  // two internal common tangents
    double ang = acos(rsum / sqrt(d2));
    a[cnt] = A.point(base + ang);
    b[cnt] = B.point(PI + base + ang);
    ++cnt;
    a[cnt] = A.point(base - ang);
    b[cnt] = B.point(PI + base - ang);
    ++cnt;
  }
  return cnt;
}

// Point O is outside circle A, find the inverse circle B of A, R is inversion radius
Circle Inversion_C2C(Point O, double R, Circle A) {
  double OA = Length(A.c - O);
  double RB = 0.5 * ((1 / (OA - A.r)) - (1 / (OA + A.r))) * R * R;
  double OB = OA * RB / A.r;
  double Bx = O.x + (A.c.x - O.x) * OB / OA;
  double By = O.y + (A.c.y - O.y) * OB / OA;
  return Circle(Point(Bx, By), RB);
}

// Invert a line to a circle passing through O, R is inversion radius
Circle Inversion_L2C(Point O, double R, Point A, Vector v) {
  Point P = GetLineProjection(O, A, A + v);
  double d = Length(O - P);
  double RB = R * R / (2 * d);
  Vector VB = (P - O) / d * RB;
  return Circle(O + VB, RB);
}

// Returns true if points A and B are on the same side of the line
bool theSameSideOfLine(Point A, Point B, Point S, Vector v) {
  return dcmp(Cross(A - S, v)) * dcmp(Cross(B - S, v)) > 0;
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    Circle A, B;
    Point P;
    scanf("%lf%lf%lf", &A.c.x, &A.c.y, &A.r);
    scanf("%lf%lf%lf", &B.c.x, &B.c.y, &B.r);
    scanf("%lf%lf", &P.x, &P.y);
    Circle NA = Inversion_C2C(P, 10, A);
    Circle NB = Inversion_C2C(P, 10, B);
    Point LA[N], LB[N];
    Circle ansC[N];
    int q = getTangents(NA, NB, LA, LB), ans = 0;
    for (int i = 0; i < q; ++i)
      if (theSameSideOfLine(NA.c, NB.c, LA[i], LB[i] - LA[i])) {
        if (!theSameSideOfLine(P, NA.c, LA[i], LB[i] - LA[i])) continue;
        ansC[ans++] = Inversion_L2C(P, 10, LA[i], LB[i] - LA[i]);
      }
    printf("%d\n", ans);
    for (int i = 0; i < ans; ++i) {
      printf("%.8f %.8f %.8f\n", ansC[i].c.x, ansC[i].c.y, ansC[i].r);
    }
  }

  return 0;
}

Exercises

「ICPC 2017 Nanning Site Online Contest」Finding the Radius for an Inserted Circle

「CCPC 2017 Online Contest」The Designer

References and Further Reading

• Inversive geometry - Wikipedia

• Inversion Transformation of Circles - ACdreamers' Blog

---

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