计算封闭多边形的内部平分线

Question

我有一个逆时针方向的多边形。我想弄清楚每个相邻边的平分线是什么。我想出了一个解决方案，但我想知道这是否是最有效的方法...

我需要检查内角。它比pi大还是小？我需要这样做，因为我需要翻转传入向量或传出向量。

问题基本上是：是否有更有效的方法来确定内角是否 > pi（或 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

为每对相邻边创建方向向量并构建单元法线。我使用左法线 - 适用于 CCW 多边形，图片显示 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

Answer 2

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

此函数 returns 与上一个函数中的等分线长度相同，无需额外的 getIntersection 函数。

计算封闭多边形的内部平分线

Calculate interior bisectors in closed polygon

geometry

angle