javascriptpolygonconvexconcave

find convex an concave corners in a polygon


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);
}

problem


Solution

  • 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.