kelvin@cs.utexas.edu (Kelvin Thompson) (05/05/89)
In article <5397@cs.utexas.edu>, atc@cs.utexas.edu (Alvin T. Campbell III) writes: } I recently had to solve the winding-sense problem myself. } } [...] } } Now for the method. Assume that we have a polygon with n } vertices, numbered v1, v2, ..., vn. First, we find the vertex, } vtop, with the largest y-coordinate. The angle of the polygon } at this vertex is guaranteed to be convex. Now we take the } cross-product of the vectors (vaft, vtop) and (vtop, vbef), } where vaft is the vertex following vtop, and vbef is the vertex } preceding vtop. If the cross-product is negative, the vertices } are counter-clockwise. Otherwise, the vertices are clockwise. A.T., can't this break down if the top M verticies of the polygon are all exactly horizontally co-linear? To be triple-safe, you ought to check that the cross product is non-zero. If it is zero, you need to search for a non-horizontal neighbor. -- -- Kelvin Thompson, Lone Rider of the Apocalypse kelvin@cs.utexas.edu {...,uunet}!cs.utexas.edu!kelvin