展开凸多边形的填充

Question

我有一个凸多边形P1的N点.该多边形可以是任何形状或比例(只要它仍然是凸的).

我需要P2使用原始多边形几何计算另一个多边形,但是"扩展"给定数量的单位.算法可以用于扩展凸多边形？

Answer 1

要展开凸多边形,请绘制与每条边平行的线和给定数量的单位.然后使用新线的交点作为扩展多边形的顶点.最后的javascript/canvas遵循此功能细分:

第1步:弄清楚哪一边是"外面"

顶点(点)的顺序很重要.在凸多边形中,它们可以按顺时针(CW)或逆时针(CCW)顺序列出.在CW多边形中,将其中一个边缘逆时针旋转90度以获得朝外的法线.在CCW多边形上,改为CW.

如果事先不知道顶点的转弯方向,请检查第二条边从第一条边开始转动.在凸多边形中,其余边将继续沿同一方向转动:

1. 找到第一条边的CW法线.我们还不知道它是向内还是向外.

2. 使用我们计算的法线计算第二条边的点积.如果第二个边缘变为CW,则点积将为正.否则它将是负面的.

数学:

// in vector terms:
v01 = p1 - p0                      // first edge, as a vector
v12 = p2 - p1                      // second edge, as a vector
n01 = (v01.y, -v01.x)              // CW normal of first edge
d = v12 * n01                      // dot product

// and in x,y terms:
v01 = (p1.x-p0.x, p1.y-p0.y)       // first edge, as a vector
v12 = (p2.x-p1.x, p2.y-p1.y)       // second edge, as a vector
n01 = (v01.y, -v01.x)              // CW normal of first edge
d = v12.x * n01.x + v12.y * n01.y; // dot product: v12 * n01

if (d > 0) {
    // the polygon is CW
} else {
    // the polygon is CCW
}

// and what if d==0 ?
// -- that means the second edge continues in the same
// direction as a first.  keep looking for an edge that
// actually turns either CW or CCW.

码:

function vecDot(v1, v2) {
    return v1.x * v2.x + v1.y * v2.y;
}

function vecRot90CW(v) {
    return { x: v.y, y: -v.x };
}

function vecRot90CCW(v) {
    return { x: -v.y, y: v.x };
}

function polyIsCw(p) {
    return vecDot(
        vecRot90CW({ x: p[1].x - p[0].x, y: p[1].y - p[0].y }),
        { x: p[2].x - p[1].x, y: p[2].y - p[1].y }) >= 0;
}

var rot = polyIsCw(p) ? vecRot90CCW : vecRot90CW;

第2步:找到与多边形边平行的线

现在我们知道哪一侧出来了,我们可以精确地计算与每个多边形边缘平行的线.这是我们的策略:

1. 对于每条边,计算其向外的法线

2. 归一化法线,使其长度变为一个单位

3. 将法线乘以我们希望扩展多边形来自原始距离的距离

4. 将乘法法线添加到边的两端.这将在平行线上给出两点.这两点足以定义平行线.

码:

// given two vertices pt0 and pt1, a desired distance, and a function rot()
// that turns a vector 90 degrees outward:

function vecUnit(v) {
    var len = Math.sqrt(v.x * v.x + v.y * v.y);
    return { x: v.x / len, y: v.y / len };
}

function vecMul(v, s) {
    return { x: v.x * s, y: v.y * s };
}

var v01 = { x: pt1.x - pt0.x, y: pt1.y - pt0.y };  // edge vector
var d01 = vecMul(vecUnit(rot(v01)), distance);     // multiplied unit normal
var ptx0 = { x: pt0.x + d01.x, y: pt0.y + d01.y }; // two points on the
var ptx1 = { x: pt1.x + d01.x, y: pt1.y + d01.y }; //     parallel line

第3步:计算平行线的交点

- 这些将是扩展多边形的顶点.

数学:

通过两点P1,P2的线可以描述为:

P = P1 + t * (P2 - P1)

两行可以描述为

P = P1 + t * (P2 - P1)
P = P3 + u * (P4 - P3)

他们的交叉点必须在两条线上:

P = P1 + t * (P2 - P1) = P3 + u * (P4 - P3)

这可以按摩看起来像:

(P2 - P1) * t + (P3 - P4) * u = P3 - P1

以x,y表示的是:

(P2.x - P1.x) * t + (P3.x - P4.x) * u = P3.x - P1.x
(P2.y - P1.y) * t + (P3.y - P4.y) * u = P3.y - P1.y

由于点P1,P2,P3和P4是已知的,因此以下值也是如此:

a1 = P2.x - P1.x    a2 = P2.y - P1.y
b1 = P3.x - P4.x    b2 = P3.y - P4.y
c1 = P3.x - P1.x    c2 = P3.y - P1.y

这缩短了我们的方程式:

a1*t + b1*u = c1
a2*t + b2*u = c2    

求解牛逼得到我们:

t = (b1*c2 - b2*c1)/(a2*b1 - a1*b2)

这让我们找到了交叉点P = P1 + t * (P2 - P1).

码:

function intersect(line1, line2) {
    var a1 = line1[1].x - line1[0].x;
    var b1 = line2[0].x - line2[1].x;
    var c1 = line2[0].x - line1[0].x;

    var a2 = line1[1].y - line1[0].y;
    var b2 = line2[0].y - line2[1].y;
    var c2 = line2[0].y - line1[0].y;

    var t = (b1*c2 - b2*c1) / (a2*b1 - a1*b2);

    return {
        x: line1[0].x + t * (line1[1].x - line1[0].x),
        y: line1[0].y + t * (line1[1].y - line1[0].y)
    };
}

第4步:处理特殊情况

有许多值得注意的特殊情况.留给读者的练习......

1. 当两个边缘之间存在非常尖锐的角度时,展开的顶点可能与原始顶点非常远.如果超出某个阈值,您可能需要考虑剪切扩展边缘.在极端情况下,角度为零,这表明扩展顶点处于无穷大,导致算术中除以零.小心.

2. 当前两条边位于同一条线上时,您无法通过查看它们来判断它是CW还是CCW多边形.看看更多的边缘.

3. 非凸多边形更有趣......并且这里没有解决.

完整的示例代码

将它放在支持画布的浏览器中.我在Windows上使用了Chrome 6.三角形及其扩展版本应该具有动画效果.

canvas { border: 1px solid #ccc; }

示例代码免责声明:

• 为了清楚起见,样本牺牲了一些效率.在您的代码中,您可能只想计算每个边的扩展并行一次,而不是在此处计算两次

• 画布的y坐标向下增长,这反转了CW/CCW逻辑.事情继续发挥作用,因为我们只需要在与多边形相反的方向上转动向外法线 - 并且两者都被翻转.