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

Kerwon

Quick suggestion for method 1: Rather than actually building the convex hull, just run the algorithm and terminate as soon/if it discards any points. – Shovelhead

I'm gonna have a look at that.thanks – Kerwon

Missed the edit window on my comment. 'the algorithm' = Grahams Scan (It does more or less what your method 2 suggests btw). Also, I know this won't improve the asymptotic running time, but it makes the problem very easy to parallelize. – Shovelhead

I've got the impression that if you've got no information on your N points (are they ordered?) then you can't get anything better than N*log(N). If I can come up with a proof, I'll be happy to share it with you, but right now, it's more a feeling thant a proof. – Oxidate

@user786653: To do that, you still have to sort the items, so you end up doing the same amount of work (asymptotically speaking). However, it would still be a good optimization to perform in practice, even though you are best shaving off less than a constant factor. – Fears

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).

Fears

Thanks a lot I am gona have look at this algorithm carefully – Kerwon

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.

Shovelhead