Algorithm to find if a set of point describes a convex enveloppe

Question

I Would like to check if a set of N points describe a convex polygon or not

I was wondering if there is a good algorithm for that ?

Here is some approaches I thought of:

---

1.Convex Hull algorithm :

If the set is equal to his convex hull then it's convex. The complexity of such algorithm are O(n*LN(N)). But I had the feeling it was like breaking a butterfly upon a wheel.

---

3.Looking at the angles :

Then I thought of checking if the angles of 2 consecutive vectors never exceed 180°. But since my points are not ordered I need to check all the combinations of 3 consecutives points and that makes like an O(n3) complexity.(There should be a way to do better than that)

I try selecting points from right to left for example but the results are not always the one expected:

For example in this case I find a convex shape if I take from left to right:

So for this solution I might need a good algorithm to select the points.

---

3. looking at the barycenter :

I think that checking if the baricenter of all 3 consecutives point is inside the shape will tell me if the shape is convex of not.

Here is what I mean (G is the baricenter of each triangle):

for this solution I can select the points from left to right without problems. if the complexity of checking if G is in the shape is O(N) then the overall complexity would be somthing like O(N2).

Can you please advise me on a good algorithm to solve this problem or improve the solutions I am thinking of

Thanks in advance

Answer 1

If your input is a simple polygon, you can do it in linear time, but it is not at all obvious. There is a long history of incorrect solutions to this problem that you can read about on the following webpage:

http://cgm.cs.mcgill.ca/~athens/cs601/

Today, it is widely accepted that the simplest/best way to solve this problem is to use Melkman's algorithm:

http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm#Melkman%20Algorithm

If you don't have a simple polygon, then in the worst case it is as hard as the regular convex hull (since you can just take any ordinary convex hull problem and connect the points arbitrarily to get some nonsense polygon).

Answer 2

I was thinking starting from Wikipedia on Grahams Scan:

Do everything up to and including "sort points by polar angle with points[1]".

then:

for i = 3 to N:
    if ccw(points[i-2], points[i-1], points[i]) < 0: # Note this inequality might need checking
        return NotConvex
return Convex

Both the sorting and the checking of convexity lend themselves well to parallelization and could be merged for even further speed-up if needed.