Sign in to follow this  
Followers 0
Desu

Polygon Convex/Concave Test Function

3 posts in this topic

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?

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

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 by omikron48

Share this post


Link to post
Share on other sites

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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0