найти выпуклые и вогнутые углы многоугольника

Я пытаюсь определить, является ли угол вогнутым или выпуклым в произвольном многоугольнике. Я сделал функцию ниже, которая вычисляет угол между всеми парами ребер. однако никто никогда не знает, является ли это внутренним или внешним угловым углом, который он возвращает. Я понятия не имею, как это сделать. Любая помощь приветствуется!!!!

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
person timkado    schedule 17.11.2012    source источник

Ответы (3)


arrow_upward
0
arrow_downward

Немного подробнее о том, что вы пытаетесь сделать, может быть полезно. При этом кажется, что алгоритм для создания выпуклой оболочки может быть полезен. Например, следующий, который, вероятно, является лучшим балансом эффективности и простоты реализации:

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

Как только вы узнаете, какие точки являются частью выпуклой оболочки, остальное должно быть немного более прямолинейным.

person Nuclearman    schedule 18.11.2012
comment
Да, и если сам выпуклый корпус недостаточно хорош, что возможно для больших полигонов или полигонов нечетной формы. Использование перекрестного произведения должно помочь определить, являются ли углы выпуклыми или вогнутыми. Использование углов, вероятно, не лучший способ сделать это. - person Nuclearman; 18.11.2012

arrow_upward
3
arrow_downward

Вот некоторый код для работы с вогнутыми и выпуклыми углами:

// 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';
}
person w-f    schedule 03.09.2014

arrow_upward
0
arrow_downward

Самый простой способ сделать это — оценить детерминанты вектора.

Во-первых, мы убеждаемся, что полигон расположен по часовой стрелке/против часовой стрелки (используя метод шнурков).

Пойдем по часовой стрелке. Это означает, что все ваши внутренние углы можно считать нарисованными против часовой стрелки между соответствующими соседними сторонами.

Скажем, для определенного угла ABC между сторонами AB и BC мы можем вычислить определитель между векторами BA и BC (формула ad - bc).

Если определитель ‹= 0, вы выбираете вогнутый угол (т.е. 360 - угол между векторами). Если det больше 0, берем выпуклый угол. Надеюсь это поможет

person Tejas Chavan    schedule 23.07.2019