Designing a linear time algorithm to check whether an n-vertex polygon is convex

Question

And also i shouldn't assume that the polygon is non-intersecting

I know that a convex polygon is a non intersecting polygon with the property that all the angles are less than PI in another words , the orientation is always clockwise or anticlockwise.

So i am thinking to run the graham scan which is known to be a linear time algorithm and modify it .

SO here is my algorithm

we sort the vertices by orientation (using determinants)
Select the right most vertex in the Polygon P (call it r)
Let q and p be the next and second next vertex of Polygon P (based on orientation)
while(there is a vertex in the Polygon P)
  if orientation(p, q, r) == CW (clock wise , that means we changed directions)
     return false
  else
   r = p
   p = q
   q = next vertex
return true

is that algorithm accurate (returns false means its not convex)

Answer 1

Indeed, a check whether an angle is less or more than PI can be done in constant time using determinants. This totals to O (N).

If all the angles have the same orientation, we should still check whether the polygon is also not self-intersecting. Here, it will suffice to add up all supplementary angles and check whether the sum is 2 * PI. It will be fine to use floating point and check for approximate equality. This is also O (N).

However, we should visit the vertices in the order they follow on the polygon border. If you are given a polygon, you perhaps have that order already. On the other hand, if you are given just a set of points on the plane, a polygon with vertices in these points is not unique in the general case. So, there is no need to sort the vertices by anything: not only it is O (N log N), but we also lose important order information by doing so.

We can start from any vertex.

Answer 2

your algorithm does not work

(e.g. if the polygonal chain turns twice around the origin)

see http://hal.inria.fr/inria-00413179/en