3

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.

Ayman Hourieh
  • 39,603
vaidy_mit
  • 631

1 Answers1

1

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.

Joseph O'Rourke
  • 30,327
  • Oh,thank you sir ! Now i understood.By the way,what the slope indicates ? This is a general question.Through slope,what can be conveyed about the line formed by two points ? – vaidy_mit Jan 12 '14 at 10:36
  • @vaidy_mit: Slope plays no role in the code you displayed. So I do not understand your question. – Joseph O'Rourke Jan 12 '14 at 16:13
  • No,did you refer the slides ? They have mentioned it as slopes.Can you please check it again ? – vaidy_mit Jan 13 '14 at 11:34
  • I did not look at the slides. It would be more appropriate for you to post a sharper question. Sorry. – Joseph O'Rourke Jan 13 '14 at 11:52