An algorithm for finding if the set of points describes a convex hull

Question

I would like to check if a set of N points describes a convex polygon or not

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

Here are some approaches I was thinking about:

---

1.Convex Hull algorithm:

If the set is equal to its convex hull, then it is convex. The complexity of such an algorithm is O (n * LN (N)). But I had a feeling that it was like smashing a butterfly on a wheel.

---

3. Angle view:

Then I thought about checking if the angles of two consecutive vectors would not exceed 180 °. But since my points are not ordered, I need to check all the combinations of three points with goals and do it like O (n3) complexity. (There must be a way to do better than this)

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

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

So, for this solution, I may need a good algorithm for selecting points.

---

3. looking at the baricenter:

I think that checking that the barycenter of all three consecutive points is inside the shape will tell me if the shape is convex.

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

for this solution, I can select points from left to right without problems. if the complexity of checking whether G is in shape is O (N), then the total complexity will be the same as O (N2).

Could you advise me a good algorithm to solve this problem or improve the solutions that I think of.

Thanks in advance

Answer 1

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

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

Today it is widely recognized that the easiest / best way to solve this problem is to use the Melkman 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 complex as a regular convex hull (since you can just take any ordinary convex hull problem and connect the dots arbitrarily to get some meaningless polygon).

Answer 2

I thought starting from Wikipedia on Grahams Scan :

Do everything before, including "sort the points by the 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 sorting and convexity testing are well suited for parallelization and can be combined for further acceleration if necessary.