# Explanation

Let 2 segments $S1(p_0, p_1), $S2(p_2, p_3)$ and their cross point $p$ .
S1 can be seen as base of 2 triangles.
2 triangles with vertices $p_2$ and $p_3$ and the common base S1.
Let the heights $h_1$ and $h_2$ .

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

2 heights satisfies the proportion below.

|\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 = |\vec{p_2 p}| = \frac{|\vec{p_2 p_3}| \times h_1}{h_1 + h_2}

\vec{p_2 p} = \vec{p_2 p_3} \times l

p = p_2 + \vec{p_2 p}

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

# Code

C++

// 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;
}

Shun

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!

Cross point of 2 segments

# Explanation

# Code

Comments