How to check if two given line segments intersect I was trying to understand convex hull problem..i came across a method to check intersection of line segment. Suppose the points are $p_1, q_1$ and $p_2, q_2$. One case says that the line segments will intersect if

  
*
  
*$(p1,q1,p2)$ and $(p1,q1,q2)$ have different
  orientations and
  
*$(p2,q2,p1)$ and $(p2,q2,q1)$ have different
  orientations
  

I am not able to understand the meaning of orientation? How can different orientations lets us decide that the segment will intersect? Can some one explain it, please?
I am reading it from here 8th page
 A: 
How can different orientations lets us decide that the segment will intersect?

If $p_1$, $q_1$, and $x$ are points in the plane, the "orientation" of $(p_1, q_1, x)$ is counterclockwise if $x$ lies in the open half-plane to the left of the segment $p_1q_1$, and is clockwise if $x$ lies in the right half-plane, see page 5 of the PDF file you linked. The first of the conditions

  
*
  
*$(p_1,q_1,p_2)$ and $(p_1,q_1,q_2)$ have different orientations and
  
*$(p_2,q_2,p_1)$ and $(p_2,q_2,q_1)$ have different orientations
  

expresses the fact that $p_2$ and $q_2$ lie "on opposite sides" of the segment $p_1q_1$ (i.e., in different open half planes). Similarly, the second condition says $p_1$ and $q_1$ lie "on opposite sides" of the segment $p_2q_2$. If both conditions hold, then each segment crosses the line defined by the other segment, which means the segments intersect.
If that doesn't clarify, it may help (psychologically, if not logically) to draw a couple of segments that do not cross, and to convince yourself that at least one segment lies entirely within one of the open half-planes defined by the other segment.
A: If $(a\mid b)$ and $(c\mid d)$ are endpoints of one segment, and
if $(e\mid f)$ and $(g\mid h)$ are endpoints of the other, and
if $(i\mid j)$ is the intersection of the two lines that contain the segments,
then the two segments intersect
if $((a\leqslant i \leqslant c) \vee (a\geqslant i \geqslant c))\wedge$
$((b \leqslant j \leqslant d) \vee (b \geqslant j \geqslant d)) \wedge$
$((e \leqslant i \leqslant g) \vee (e \geqslant i \geqslant g)) \wedge$
$((f \leqslant j \leqslant h)\vee(f \geqslant j \geqslant h))$.
