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

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