Checking convexity from outside

Question

Is there any method or algorithm to determine convex (or non-convexity) property of a region from outside (perimeter) ?

One way is plotting tangent line in each point of perimeter and discuss how many times this line intersect the perimeter points. If no intersect shown (for all points of perimeter ) we can conclude region is convex. In otherwise region is non-convex.

Second way is determine interior angel of each point of perimeter and discuss if it's bigger than 180 or not. The region is non-convex if at least one point in perimeter exist it's interior angel bigger than 180.

Are there another simpler ways?

Any ideas or solution would be appreciated, thanks.

Answer 1

You tagged your question mathematica. So one solution would be taking the polynomial representation of your shape, let Mathematica compute its convex hull, and check whether the number of points in that convex hull equals the number of points in your polygon. If it does, the polygon must have been convex. If not, and you left the AllPoints parameter at its default, then you have a non-convex polygon. This solution is easy to code, but might require more time during execution as some other methods: convex hull will require $O(n\log n)$, whereas convexity checking using interior angles can be done in $O(n)$.

By the way, to decide whether an interior angle is greater or smaller than 180°, you don't need to actually compute that angle. It is sufficient to check whether the triangle formed by three consecutive vertices is oriented clockwise or counter-clockwise. In a convex polygon, all triangles will have the same orientation. You can read that orientation from the sign of the determinant

$$\begin{vmatrix} x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \\ 1 & 1 & 1 \end{vmatrix}$$

This is what I'm doing in my code. It is also equivalent to the various alternatives to Determine which side of a line a point lies, as pointed out in the answer by andand.

Answer 2

Define a closed half-space as all points on one side of a hyperplane, including the hyperplane itself. For closed convex sets of Euclidean space we have the following result:

A set $S\subset\mathbb{R}^n$ is closed and convex if and only if $S$ is the intersection of closed half-spaces.

We can write this in an equivalent form involving points outside of $S$:

A set $S\subset\mathbb{R}^n$ is closed and convex if and only if for every point $P\notin S$, there exists a closed half-space $H$ containing $S$ but not containing $P$.