Polygon Convex/Concave Test Function

[Desu 0]

I am trying to write a function that will test if a polygon (for use with the GDI graphics polygon functions) is concave or convex.

Func convex($poly)
    
    Dim $j
    Dim $k
    Dim $z
    Dim $flag = 0
    
    For $i = 1 To $poly[0][0]
        
        $j = Mod( $i+1, $poly[0][0] )
        $k = Mod( $i+2, $poly[0][0] )
        $z = ($poly[$j][0] - $poly[$i][0]) * ($poly[$k][1] - $poly[$j][1])
        $z -= ($poly[$j][1] - $poly[$i][1]) * ($poly[$k][0] - $poly[$j][0])

        If $z < 0 Then
            $flag = BitOR( $flag, 1 )
        ElseIf $z > 0 Then
            $flag = BitOR( $flag, 2 )
        EndIf
        If $flag = 3 Then 
            Return 0
        EndIf
        
    Next

    If $flag <> 0 Then
        Return 1
    Else
        Return 0
    EndIf

EndFunc

This is attempting to use the cross-product method to test the polygon. It should return 1 if convex and 0 if not. No matter what polygon I put into the function, including a simple triangle, the flag always gets set to 3 and it returns 0.

I cannot seem to figure out why. Anyone know or have a different/easier way of doing this same operation?

[omikron48 0]

Did you check if your execution of the algorithm is correct?

That way I see it, the reason you keep getting $flag set to 3 and a return of 0 is because somewhere during the course of your For loop, both the conditions '$z < 0' and '$z > 0' are satisfied.

EDIT: Upon further inspection and pondering, it appears that your execution is wrong.

$j = Mod( $i+1, $poly[0][0] )
$k = Mod( $i+2, $poly[0][0] )

This piece of code will only work if your array of coordinates have the first coordinate stored in a base-0 array. Unfortunately, the [0][0] position is occupied by the element count of the 2D array. That's what's throwing your calculation off. You either need adjust your code to compensate and skip the [0][x] element or make a new base-0 array contain only the vertices of your polygon then feed it into your looping test.

Edited May 29, 2010 by omikron48

[Desu 0]

Aha! Yep that was it. I just had to put the vertices into a new zero-based array. It works perfectly now. Thanks for the help omikron!