Cross points of circles

Calendar Clock iconCalendar Clock icon

geometry

Table of contents

# Explanation

Find cross points of 2 circles.

Example input:

C1(0,0),R12C2(0,3),R21C_1(0, 0), R_1 2 C_2(0, 3), R_2 1

# Code

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define EPS 0.0000000001
#define fequals(a,b) (fabs((a) - (b)) < EPS)

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (const Vector2 v) const { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (const Vector2 v) const { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (const double k) const { return Vector2(x * k, y * k); }
  Vector2 operator / (const double k) const { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 const v) { return x * v.x + y * v.y; }
  double cross (Vector2 const v) { return x * v.y - y * v.x; }
  
  bool parallel(Vector2 &other) {
    return fequals(0, cross(other));
  }
  
  bool orthogonal(Vector2 &other) {
    return fequals(0, dot(other));
  }
  
  bool operator < (const Vector2 &v) {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}
pair<Vector2, Vector2> crossPoints() {
  Vector2 baseVec = C2 - C1;
  double baseLen = baseVec.length();
  double cos_ = (baseLen*baseLen + R1*R1 - R2*R2) / (2 * baseLen * R1);
  double sin_ = sqrt(1 - cos_*cos_);
  // Counter-clockwise
  Vector2 a_(cos_ * baseVec.x + -sin_ * baseVec.y, sin_ * baseVec.x + cos_ * baseVec.y);
  // Clockwise
  Vector2 b_(cos_ * baseVec.x + sin_ * baseVec.y, -sin_ * baseVec.x + cos_ * baseVec.y);
  Vector2 a = C1 + a_ * R1 / baseLen;
  Vector2 b = C1 + b_ * R1 / baseLen;
  if (fabs(a.x) < EPS) a.x = 0.0;
  if (fabs(a.y) < EPS) a.y = 0.0;
  if (fabs(b.x) < EPS) b.x = 0.0;
  if (fabs(b.y) < EPS) b.y = 0.0;
  if (a < b) return make_pair(a, b);
  return make_pair(b, a);
}

# Wrong algorithm

This is still WIP. It doen't work for input like below.

0 0 10
0 10 8

Vector2 mid(Vector2 c1, double r1, Vector2 c2, double r2) {
  return c1 + (c2 - c1) * (r1 / (r1 + r2));
}

Vector2 perpen(Vector2 a, Vector2 b) {
  Vector2 c = b - a;
  double d = c.x;
  c.x = c.y;
  c.y = -d;
  return c;
}

Vector2 unitVec(Vector2 v) {
  return v / v.length();
}

pair<Vector2, Vector2> crossPoints() {
  Vector2 p = mid(C1, R1, C2, R2);
  cout << p << endl;
  Vector2 e = unitVec(perpen(C1, p));
  double len = sqrt(R1*R1 - (p - C1).norm());
  Vector2 x1 = p + e * len;
  Vector2 x2 = p + e * (-len);
  if (fabs(x1.x) < EPS) x1.x = 0.0;
  if (fabs(x1.y) < EPS) x1.y = 0.0;
  if (fabs(x2.x) < EPS) x2.x = 0.0;
  if (fabs(x2.y) < EPS) x2.y = 0.0;
  if (x1 < x2) return make_pair(x1, x2);
  return make_pair(x2, x1);
}

Shun

Github Circle icon

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

Comments