Jump to content

Recommended Posts

Posted

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?

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
Posted

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!

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
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...