segment_intersect.cpp

#include <cmath>		// sqrt
#include <cassert>		// assert
#include <algorithm>	// max, min

using namespace std;

const double eps = 1e-6;

struct Cord{
	double x, y;
	Cord(double tx=0.0, double ty=0.0): x(tx), y(ty)
	{}
	Cord operator-(const Cord& c) const{
		return Cord(x-c.x,y-c.y);
	}
};

struct Segment{
	Cord m, n;
	Segment(Cord a, Cord b){
		m.x = a.x, m.y = a.y;
		n.x = b.x, n.y = b.y;
	}
	double minx() const {
		return min(m.x,n.x);
	}
	double miny() const {
		return min(m.y,n.y);
	}
	double maxx() const {
		return max(m.x,n.x);
	}
	double maxy() const {
		return max(m.y,n.y);
	}
};

struct Line{
	double a, b, c;
	Line():a(0.0),b(0.0),c(0.0)
	{}
	Line(const Cord& m, const Cord& n){
		a = n.y-m.y;
		b = m.x-n.x;
		c = (n.y-m.y)*m.x+(m.x-n.x)*m.y;
		if(a<0.0)
			a = -a, b = -b, c = -c;
	}
	void set(const Cord& m, const Cord& n){
		Line(m,n);
	}
};

double cross(const Cord& a, const Cord& b)
{
	return a.x*b.y-a.y*b.x;
}

double dist(const Cord& a, const Cord& b)
{
	Cord tmp = b-a;
	return sqrt(tmp.x*tmp.x + tmp.y*tmp.y);
}

inline bool dbeq(const double a, const double b)
{
	return fabs(a-b)<eps;
}

double scope(const Line& m)
{
	assert(!dbeq(m.b,0.0));
	return -m.a/m.b;
}

inline bool on_segment(const Segment& s, const Cord& qry)
{
	/*
	if(cross(p2-p1,qry-p1) != 0)
		return false;
	*/
	return s.minx() <= qry.x && qry.x <= s.maxx() && s.miny() <= qry.y && qry.y <= s.maxy();
}

/*
 * segment_intersect
 * @brief: test if the line segment [p1,p2] and [p3,p4] has intersect
 * @param: 4 coordinates p1, p2, p3, p4
 * @return: 0 for no intersect
 *          1 for 1 intersect point
 *          2 for intersect at edge (non-proper)
 */
int segment_intersect(const Segment& s1, const Segment& s2)
{
	double d1 = cross(s1.m-s2.m,s2.n-s2.m);
	double d2 = cross(s1.n-s2.m,s2.n-s2.m);
	double d3 = cross(s2.m-s1.m,s1.n-s1.m);
	double d4 = cross(s2.n-s1.m,s1.n-s1.m);

	if(d1*d2<0 && d3*d4<0)	return 1;

	// non-proper intersections
	if(dbeq(d1,0.0) && on_segment(s2,s1.m))	return 2;
	if(dbeq(d2,0.0) && on_segment(s2,s1.n))	return 2;
	if(dbeq(d3,0.0) && on_segment(s1,s2.m))	return 2;
	if(dbeq(d4,0.0) && on_segment(s1,s2.n))	return 2;

	return 0;
}

bool line_equal(const Line& m, const Line& n)
{
	if(dbeq(m.a,0.0) ^ dbeq(n.a,0.0))	return false;
	if(dbeq(m.b,0.0) ^ dbeq(n.b,0.0))	return false;
	if(dbeq(m.c,0.0) ^ dbeq(n.c,0.0))	return false;

	double ratea = !dbeq(n.a,0.0)?m.a/n.a:0.0;
	double rateb = !dbeq(n.b,0.0)?m.b/n.b:0.0;
	double ratec = !dbeq(n.c,0.0)?m.c/n.c:0.0;

	if(!dbeq(ratea,0.0) && !dbeq(rateb,0.0) && !dbeq(ratec,0.0))
		return dbeq(ratea,rateb) && dbeq(rateb,ratec);

	if(!dbeq(ratea,0.0) && !dbeq(rateb,0.0))
		return dbeq(ratea,rateb);
	if(!dbeq(rateb,0.0) && !dbeq(ratec,0.0))
		return dbeq(rateb,ratec);
	if(!dbeq(ratea,0.0) && !dbeq(ratec,0.0))
		return dbeq(ratea,ratec);

	return true;
}

bool parallell(const Line& m, const Line& n)
{
	// assert(!equal(m,n));
	if(dbeq(m.b,0.0) && dbeq(n.b,0.0))
		return true;
	if(dbeq(m.b,0.0) ^ dbeq(n.b,0.0))
		return false;
	return dbeq(scope(m),scope(n));
}

Cord intersect(const Line& m, const Line& n)
{
	double delta = m.a*n.b-n.a*m.b;

	assert( !dbeq(delta,0.0) );

	double deltax = m.c*n.b-n.c*m.b;
	double deltay = m.a*n.c-n.a*m.c;

	return Cord(deltax/delta,deltay/delta);
}

bool operator>=(const Cord& c, const Line& l)
{
	return c.x*l.a+c.y*l.b-l.c>=0;
}

double area(const Cord& c1, const Cord& c2, const Cord& c3)
{
	return fabs(c1.x*c2.y+c1.y*c3.x+c2.x*c3.y-c3.x*c2.y-c1.y*c2.x-c1.x*c3.y)/2.0;
}