Computational Geometry

It’s my first tutorial so if u found any mistakes feel free to post it in a comment :D. Also some code may not seem clear i’ll try to post more tutorials later ūüėÄ .

Point On Segment

First line is to check if the segment ab is a point, if so check that p also the same point.

then get the cross product of ab and ap , if the cross product equals 0 then the 3 points are¬†co-linear, that’s the first condition, yet point p may by on the same line of ab but doesn’t lie on ab.

we check this case by getting the angle between vectors ab and ap  (dot(ab,ap)) then the angle between vectors ba and bp (dot(ba,bp)).

Recall : the dot product of 2 vectors > 0 the angle őł¬†between these 2 vectors is acute.

we used ” > -EPS ” to evade the errors in the double¬†representation.

typedef int type;
typedef complex<type> Point;

#define X real()
#define Y imag()
#define length(p)  (hypot( (p).X , (p).Y ))
#define rec(a,b)   ((b)-(a))
#define dot(a,b)   (((conj(a))*(b)).real())
#define cross(a,b) (((conj(a))*(b)).imag())
bool pointOnSegment(const Point &a, const Point &b,const Point&p){
    if (length(rec(a,b)) < EPS) return length(rec(a,p)) < EPS ;//case that 3 points are tha same
    return fabs(cross(rec(a,b),rec(a,p))) < EPS //3 points are colinear
            && dot(rec(a,b),rec(a,p)) > -EPS && dot(rec(b,a),rec(b,p)) > -EPS;//between a,b
}

Intersecting Segments

photo taken from saipanyam.net

bool intersectSegment(const Point &a, const Point &b,const Point&p,const Point &q){
    type d1 = cross(p-a,b-a);
    type d2 = cross(q-a,b-a);
    type d3 = cross(a-p,q-p);
    type d4 = cross(b-p,q-p);
    if(d1*d2 <-EPS  && d3*d4 <-EPS) return true;//d1,d2 have different directions and d3,d4 have different directions
    else if (d1<EPS && pointOnSegment(a,b,p)) return true;//p is colinear with ab
    else if (d2<EPS && pointOnSegment(a,b,q)) return true;//q is colinear with ab
    else if (d3<EPS && pointOnSegment(p,q,a)) return true;//a is colinear with pq
    else if (d4<EPS && pointOnSegment(p,q,b)) return true;//b is colinear with pq
    else return false;
}