Geometry


Geometry template extension

const double pi=M_PI;
#define area(a,b,c) ((b-a)^(c-a))
#define sqDist(a,b) (sqr(a.x-b.x)+sqr(a.y-b.y))
#define dist(a,b) sqrt(sqDist(a,b))


Geometric structures/classes used in my codes

struct point{
    #define DT int /// Datatype
    DT x,y; 
    point():x(0),y(0){} /// default constructor
    point(DT _x,DT _y):x(_x),y(_y){} /// constructor
    
    bool operator < (point b) ; /// smaller than operator
    bool operator == (point b) ; /// equal to operator
    point operator - (point b) ; /// returns a vector from `this` to `b`
    DT operator * (point b) ; /// Dot product of `this` and `b`
    DT operator ^ (point b) ; /// Cross product of `this` and `b`
	point pointBetween(point q,double m1,double m2);
	/// returns a point from the joining segment of 'this' and 'q'
	/// the distance ratio of which from 'this' and 'q' is m1:m2
};

bool point::operator < (point b) {
	/// smaller than operator
	if(!sgn(x,b.x)) return sgn(y,b.y)<0;
	return sgn(x,b.x)<0;
}

bool point::operator == (point b) {
	/// equal to operator
	return !sgn(x,b.x) && !sgn(y,b.y);
}

point point::operator - (point b){ 
	/// returns a vector from `this` to `b`
	return point(x-b.x,y-b.y);
}

__typeof(point::x) point::operator * (point b){ 
	/// Dot product
	return x*b.x+y*b.y;
}

__typeof(point::x) point::operator ^ (point b){ 
	/// Cross product
	return x*b.y-y*b.x;
}

point point::pointBetween(point q,double m1,double m2){
	/// returns a point from the joining segment of 'this' and 'q'
	/// the distance ratio of which from 'this' and 'q' is m1:m2
    return point( ( m1 * q.x + m2 * x ) / ( m1 + m2 ) , ( m1 * q.y + m2 * y ) / ( m1 + m2 ) );
}
struct line{
    #define DT int /// Datatype
    DT a,b,c;
    
    line(){a=b=c=0;} /// default constructor
    line(point p,point q):a(p.y-q.y),b(q.x-p.x),c(p.x*q.y-q.x*p.y){} /// constructor
    
    bool operator < (line B); /// smaller than operator
    
    void normalize(); /// generalizes the line coefficients 'a','b','c'    
    line perpendicular(point p);
 	/// returns the perpendicular line
	/// which goes through point 'p'
};

void line::normalize(){ 
	/// generalizes the line coefficients 'a','b','c'
	__typeof(a) g=gcd(a,gcd(b,c)); 
	a/=g, b/=g, c/=g;
	int sign=(a<0 || (!a && b<0))?-1:1;
	a*=sign, b*=sign, c*=sign;
}

line line::perpendicular(point p){
	/// returns the perpendicular line
	/// which goes through point 'p'
	line ret;
	ret.a=b, ret.b=-a;
	ret.c=-p.x*ret.a-p.y*ret.b;
	return ret;
}

bool line::operator < (line B) {
	/// smaller than operator
	if(!sgn(a,B.a)) {
		return sgn(b,B.b)==0?sgn(c,B.c)<0:sgn(b,B.b)<0;
	}
	return sgn(a,B.a)<0;
}
struct segment{
	point A,B;
	segment():A(point(0,0)),B(point(0,0)){}
	segment(point _A,point _B):A(_A),B(_B){}
	bool inside(point c); /// checks if a point is inside the enclosing rectangle
	bool intersect(segment Q) ; /// checks if 'this' intersect with 'Q'
};

bool segment::inside(point c){
	/// checks if a point is inside the enclosing rectangle
	return (min(A.x,B.x)<=c.x && c.x<=max(A.x,B.x) && min(A.y,B.y)<=c.y && c.y<=max(A.y,B.y));
}

bool segment::intersect(segment Q){
	/// checks if 'this' intersect with 'Q'
	__typeof(A.x) d1=area(Q.A,Q.B,A);
	__typeof(A.x) d2=area(Q.A,Q.B,B);
	__typeof(A.x) d3=area(A,B,Q.A);
	__typeof(A.x) d4=area(A,B,Q.B);
	if( ((d1>0 && d2<0) || (d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0))  ) return true;
	if(!d1 && Q.inside(A)) return true;
	if(!d2 && Q.inside(B)) return true;
	if(!d3 && inside(Q.A)) return true;
	if(!d4 && inside(Q.B)) return true;
	return false;
}


Polygon

Area of a 2D polygon
Convex hull of 2D points
Intersections

Go Back

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s