find convex an concave corners in a polygon

Question

I am trying to detect if a corner is concave or convex in an arbitrary polygon. I made the function below that computes the angle between all edge-pairs. however one never knows if the if it is the inner or the outer corner angle that it returns. I have no idea how to go about this. Any help appreciated!!!!

function findConvexCorner (pt){
var isCornerConvex = [];
for (var i =0; i < pt.length ;i++)
{
    var lastPt = pt.length -1;
    if (i==0){
        var vec1 = vec3.createXYZ( pt[lastPt].x - pt[i].x , pt[lastPt].y - pt[i].y ,0.0);
        var vec2 = vec3.createXYZ( pt[i].x - pt[i+1].x , pt[i].y - pt[i+1].y ,0.0);
        vec3.normalize(vec1);vec3.normalize(vec2);
            isCornerConvex.push(Math.acos(vec3.dot(vec1,vec2))*180/Math.PI);}
    else if(i == lastPt){
        var vec2 = vec3.createXYZ( pt[i-1].x - pt[i].x , pt[i-1].y - pt[i].y ,0.0);
        var vec1 = vec3.createXYZ( pt[0].x - pt[i].x , pt[0].y - pt[i].y ,0.0);
        vec3.normalize(vec1);vec3.normalize(vec2);
            isCornerConvex.push(Math.acos(vec3.dot(vec1,vec2))*180/Math.PI);}
    else{
        var vec1 = vec3.createXYZ( pt[i-1].x - pt[i].x , pt[i-1].y - pt[i].y ,0.0);
        var vec2 = vec3.createXYZ( pt[i+1].x - pt[i].x , pt[i+1].y - pt[i].y ,0.0);
        vec3.normalize(vec1);vec3.normalize(vec2);
            isCornerConvex.push(Math.acos(vec3.dot(vec1,vec2))*180/Math.PI);}
}
console.log("Angle: "+ isCornerConvex);
}

Answer 1

A bit more detail about what your trying to do might be helpful. That being said, seems like an algorithm for generating the convex hull might be useful. Such as the following, which is probably the best balance of efficiency and ease of implementation:

http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

Once you know which points are part of the convex hull, the rest should be a bit more straight forward.

Answer 2

Here's some code to work out concave vs convex corners:

// this assumes nextEdge and previousEdge are vectors pointing out of a vertex and to the next one
var angle = ((Math.atan2(nextEdge.x, nextEdge.y) - Math.atan2(previousEdge.x, previousEdge.y) + Math.PI * 2) % (Math.PI * 2)) - Math.PI;

if (angle > 0) {
   corner.type = 'convex';
} else if (angle < 0) {
    corner.type = 'concave';
} else {
    corner.type = 'straight';
}

Answer 3

An easy way to do this is by assessing vector determinants.

First, we make sure that the polygon is clockwise/anti-clockwise (using shoelace method).

Let's go with clockwise. That means all your interior angles can be considered to be drawn anti-clockwise between respective adjacent sides.

Say for a particular angle ABC between sides AB and BC, we can calculate the determinant between vectors BA and BC (ad - bc formula).

If the determinant is <= 0, you go for the concave angle (ie. 360 - angle between vectors). If det is greater than 0, we take the convex angle. Hope this helps