Рассчитать внутренние биссектрисы в замкнутом многоугольнике

Question

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

Мне нужно проверить внутренний угол.Это больше или меньше, чем пи.Я должен сделать это, потому что мне нужно перевернуть либо входящий вектор, либо исходящий вектор.

Вопрос в основном заключается в следующем: есть ли более эффективный способ определить, является ли внутренний угол> пи (или 180 градусов)?

Процедура в javascript, которую я сейчас имею, такова:

export const getBisectors = (polygon) => {
    //get bisectors, including length based on the unit normal vectors of the edges (inward)
    let bisectors = [];
    let prevPoint = polygon[polygon.length - 1];

    polygon.forEach((p, i) => {
        let nextPoint = i === polygon.length - 1 ? polygon[0] : polygon[i + 1];

        //vector going to p
        let v1 = normalizeVector({ x: p.x - prevPoint.x, y : p.y - prevPoint.y });
        let radIn = Math.acos(v1.x);
        if (v1.y < 0) radIn = TwoPI - radIn;

        // vector to next point
        let v2 = normalizeVector({ x: nextPoint.x - p.x, y : nextPoint.y - p.y });
        let radOut = Math.acos(v2.x);
        if (v2.y < 0) radOut = TwoPI - radOut;

        let rotation = radIn - radOut;
        if (rotation < 0) rotation += TwoPI; 

        if (rotation > Math.PI) {
            //invert outgoing
            v2 = multiply(v2, -1);
        } else {
            //invert incoming
            v1 = multiply(v1, -1);
        }
        let bisector = addVectors(v1, v2);

        bisectors.push({bisector: bisector, p : p  });
        prevPoint = p;
    });
    return bisectors;
}

После частичного ответа я получил следующий метод:

export const getIntersection = (p1, v1, p2, v2) => {
    //find s
    //p1 + s * v1 == p2 + t * v2
    var denominator = cross(v1, v2);

    if (Math.abs(denominator) < epsilon) {
        return p1;
    }

    var s = (p2.x * v2.y + p1.y * v2.x - p2.y * v2.x - p1.x * v2.y) / denominator;
    return {x : p1.x + s * v1.x, y : p1.y + s * v1.y};
}

function getBisector(prevPoint, point, nextPoint) {
    let v1 = { x: point.x - prevPoint.x, y : point.y - prevPoint.y };
    let n1 = normalizeVector( { x: v1.y, y : -( v1.x ) } )
    let n2 = normalizeVector( { x: (nextPoint.y - point.y), y : -(nextPoint.x - point.x) } )

    let bisector = addVectors(n1, n2);    
    let i = getIntersection(point, bisector, addVectors(prevPoint, n1), v1);

    return {x : i.x - point.x, y : i.y - point.y};
}

и некоторые примеры:

Answer 1

let v1 = normalizeVector({ x: p.x - prevPoint.x, y : p.y - prevPoint.y });
let v2 = normalizeVector({ x: nextPoint.x - p.x, y : nextPoint.y - p.y });

k = v1.x * v2.y - v1.y * v2.x;

if (k < 0){
   //the angle is greater than pi, invert outgoing, 
   //ready to get interior bisector 
   v2 = multiply(v2, -1);  
}
else{
   //the angle is less than pi, invert incoming, 
   v1 = multiply(v1, -1);
}

bisector = normalizeVector({ x: v1.x + v2.x, y : v1.y + v2.y });

Etit: Вот еще более быстрый код для генерации внутреннего биссектриса без использования каких-либо нормалей: код Matlab, который я тестировал.Он генерирует единичные биссектрисы, указывающие внутри многоугольника.

function  B = bisectors(P)

   %P is 2 x n matrix, column P(:,j) is a vertex of a polygon in the plane,
   %P is the ordered set of vertices of the polygon

   [~,n] = size(P); 
   B = zeros(2,n);

   for j=1:n

       if j == 1
          v_in = P(:,1) - P(:,n);
          v_out = P(:,2) - P(:,1);
       elseif j == n
          v_in = P(:,j) - P(:,j-1);
          v_out = P(:,1) - P(:,j);
       else
          v_in = P(:,j) - P(:,j-1);
          v_out = P(:,j+1) - P(:,j);
       end

       v_in = v_in/sqrt(v_in'*v_in); %normalize edge-vector
       v_out = v_out/sqrt(v_out'*v_out); %normalize edge-vector

       % bisector of the complementary angle at the vertex j, 
       % pointing counter clockwise and displacing the vertex so that
       % the resulting polygon is 1 unit inwards in normal direction:
       bisector = v_in + v_out; 
       bisector = bisector/abs(bisector'*v_in);

       % 90 degree counter clockwise rotation of complementary bisector:
       B(1,j) = - bisector(2);
       B(2,j) = bisector(1);

   end

end

И в вашей записи:

function getBisector(prevPoint, point, nextPoint) {

    let v1 = normalizeVector({ x : point.x - prevPoint.x, y : point.y - prevPoint.y });
    let v2 = normalizeVector({ x : nextPoint.x - point.x, y : nextPoint.y - point.y });


    let bisectorPerp = addVectors(v1, v2); 
    bisectorPerp = bisectorPerp / absoluteValue(dot(v1, bisectorPerp));   

    return {x : - (bisectorPerp.y), y : bisectorPerp.x};
}

Эта функция возвращает биссектрисы той же длины, что и в вашей последней функции, без необходимости использования дополнительной функции getIntersection.

Answer 2

Для каждой пары соседних ребер задайте векторы направления и постройте нормали единиц измерения.Я использовал левые нормали - подходит для многоугольника против часовой стрелки, рисунок показывает angle > Pi, расчеты одинаковы для меньших углов.

a = P[i] - P[i-1]
b = P[i+1] - P[i]

na = (-a.y, a.x)  //left normal
na = na / Length(na)

nb = (-b.y, b.x)   
nb = nb / Length(nb)

bisector = na + nb  

Если вам нужно сделать вершину со смещением d:

bis = bisector / Length(bisector)

сделать длину биссектрисы, чтобы обеспечить необходимое расстояние как

l = d / Sqrt(1 + dotproduct(na,nb))

И найти смещенную вершину многоугольника:

P' = P + l * bis