javascript - find convex an concave corners in a polygon - Stack Overflow

admin管理员组

文章数量:1415139

I am trying to detect if a corner is concave or convex in an arbitrary polygon. I made the function below that putes 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);
}

I am trying to detect if a corner is concave or convex in an arbitrary polygon. I made the function below that putes 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);
}

• javascript
• polygon
• convex
• concave

Share Improve this question Follow asked Nov 17, 2012 at 0:23 timkadotimkado 2,06222 gold badges2020 silver badges3030 bronze badges

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 3

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

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

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

本文标签： javascriptfind convex an concave corners in a polygonStack Overflow