Efficient algorithms for testing simplicity of a 2D polygon given its vertices?

Question

I'm working on a project that requires me to test if a polygon is convex and I was able to write an algorithm that successfully tests for convexity for simple polygons but fails to provide the correct answers for some non-simple ones, like star-shaped ones.

For this reason I'm looking for an efficient algorithm to test for simplicity of a polynomial given its vertices, to run before testing for convexity. For now I was able to find this paper describing an algorithm for simplicity test but I'm failing to really understand how it should work. I tried an implementation based on this one but it doesn't work so apparently I misunderstood. Also it's not super efficient so I appreciate any other suggestion.

EDIT:

My convexity test

const nVertices: number = polygon.length; let res: number = 0; let isConvex: boolean = true;

        polygon.forEach( (thisVertex: Vertex, i: number) => {
            const thisV: Vertex = thisVertex;
            const nextV: Vertex = polygon[(i+1) % nVertices];
            const secondNextV: Vertex =  polygon[(i+2) % nVertices];
            const v: Vertex = [nextV[0] - thisV[0], nextV[1] - thisV[1]];

            if( i === 0 )
                res = secondNextV[0]*v[1] - secondNextV[1]*v[0] + v[0]*thisV[1] - v[1]*thisV[0];
            else {
                const newRes: number = secondNextV[0]*v[1] - secondNextV[1]*v[0] + v[0]*thisV[1] - v[1]*thisV[0];
                if ( (newRes > 0 && res < 0) || (newRes < 0 && res > 0) )
                    isConvex = false;
            }
        } )

Answer 1

I assume your polygon is drawn with respect to a fixed order of its vertices $v_0,…,v_{n-1}$, by which I mean that if you travel along the boundary you visit the vertices in the fixed order. Edit I also assume the polygon to be simple!

Now note that intuitively a polygon should be convex if and only if when traveling along the boundary all turns are made in the same direction. Hit me up, if you want a formal proof for this.

For this purpose we only need to know if we make a turn to the left or to the right. Given two vectors $v,w$ we can determine wether $w$ is to the left or to the right of $v$ by computing $\operatorname{sign}(v.x\cdot w.y - v.y\cdot w.x)$, positive meaning right and negative meaning left. The reason why this works is that the cross-product of three-dimensional vectors satisfies the right hand rule and for vectors in the x-y-plane only the third component will give nontrivial information, either pointing up or down.

Anyway we can use this to test for convexity. Just consider the following pseudo-code:

s = 0
for i=0 to n-1
    j = i+1 mod n
    k = i+1 mod n
    v = v_j - v_i
    w = v_k - v_i
    t = sign(v.xw.y - v.yw.x)
    if s = 0
        s = t
    if t != 0 and t != s
        return not convex
return convex

By using the for loop we go around the polygon. The vector $v$ is the next segment and the $w$ is the vertex which will follow the segment. We test whether it lies on the left or right of the segment and test whether it is the same for all segments.