Cross point of 2 segments

Calendar Clock iconCalendar Clock icon

geometry

Table of contents

# Explanation

Let 2 segments $S1(p_0, p_1), S2(p2,p3)S2(p_2, p_3) and their cross point pp.
S1 can be seen as base of 2 triangles.
2 triangles with vertices p2p_2 and p3p_3 and the common base S1.
Let the heights h1h_1 and h2h_2.

A height of a triangle can be calculated with its area and length of its base.
Length of base is p0p1|\vec{p_0 p_1}|.
The area can be calculated by using cross product p0p1\crossp0p2\vec{p_0 p_1} \cross \vec{p_0 p_2}.

2 heights satisfies the proportion below.

p2p:p2p3=h1:h1+h2|\vec{p_2 p}| : |\vec{p_2 p_3}| = h_1 : h_1 + h_2

Transform it from the point of view of length.

l=p2p=p2p3×h1h1+h2l = |\vec{p_2 p}| = \frac{|\vec{p_2 p_3}| \times h_1}{h_1 + h_2}

p2p=p2p3×l\vec{p_2 p} = \vec{p_2 p_3} \times l

p=p2+p2pp = p_2 + \vec{p_2 p}

Don't forget that the resultign coordinates can include errors.

# 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;
}
Vector2 crossPoint(Vector2 &p0, Vector2 &p1, Vector2 &p2, Vector2 &p3) {
  Vector2 baseSeg = p1 - p0;
  Vector2 crossSeg = p3 - p2;
  double h1 = fabs(baseSeg.cross(p2 - p0)) / (baseSeg.length() * 2);
  double h2 = fabs(baseSeg.cross(p3 - p0)) / (baseSeg.length() * 2);
  Vector2 p = p2 + crossSeg * h1 / (h1 + h2);
  if (fabs(p.x) < EPS) p.x = 0.0;
  if (fabs(p.y) < EPS) p.y = 0.0;
  return p;
}

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