# Intersection of two line segments

I recently came across a code for finding whether two line segments intersect. I understood the concept. It was based on orientation. Like whether the rotation is clockwise, anticlockwise or collinear. The orientation function was this one.

int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) -(q.x - p.x) * (r.y - q.y);

if (val == 0) return 0;  // colinear

return (val > 0)? 1: 2; // clock or counterclock wise
}


There was a link given at the end of the solution.

http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf

In the 10th slide, we have the derivation for this formula. But I don't understand how this works. How slope can be used to find the direction of rotation. Why does this work? Can somebody explain me the intuition behind it in simple terms.

Thanks.

• Please refer the slides for complete solution if required. – vaidy_mit Jan 11 '14 at 12:15

In that code, the misnamed val is the twice the (signed) area of the triangle determined by $p,q,r$. See the Wikipedia explanation here. The area is zero iff the three points are collinear. The area is positive if the points are in counterclockwise order, negative if in clockwise order.