凸多边形的展开填充

Question

我有一个由 N 点组成的凸多边形 P1。该多边形可以是任何形状或比例（只要它仍然是凸的）。

我需要使用原始多边形几何形状计算另一个多边形P2，但“扩展”了给定数量的单位。扩展凸多边形的算法可能是什么？

Answer 1

看看笔直的骷髅。正如这里暗示的那样，非凸多边形存在许多棘手的问题，您已经巧妙地幸免于难！

Answer 2

要扩展凸多边形，请绘制一条平行于每条边并远离给定单位数的线。然后使用新线的交点作为扩展多边形的顶点。最后的 javascript/canvas 遵循以下功能细分：

第 1 步：找出哪一侧是“out”

顶点（点）的顺序很重要。在凸多边形中，它们可以按顺时针 (CW) 或逆时针 (CCW) 顺序列出。在 CW 多边形中，将其中一条边逆时针旋转 90 度以获得朝外的法线。在 CCW 多边形上，将其转向CW。

如果事先未知顶点的转动方向，请检查第二条边如何从第一条边转向。在凸多边形中，剩余的边将继续朝同一方向转动：

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

2. 计算第二条边与我们计算的法线的点积。如果第二个边沿顺时针旋转，则点积将为正。否则将为负数。

数学：

// 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 得到：

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

$(function() {
      var canvas = document.getElementById('canvas');  
      if (canvas.getContext) {  
          var context = canvas.getContext('2d');  

          // math for expanding a polygon

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

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

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

          function expandPoly(p, distance) {
              var expanded = [];
              var rot = polyIsCw(p) ? vecRot90CCW : vecRot90CW;

              for (var i = 0; i < p.length; ++i) {

                  // get this point (pt1), the point before it
                  // (pt0) and the point that follows it (pt2)
                  var pt0 = p[(i > 0) ? i - 1 : p.length - 1];
                  var pt1 = p[i];
                  var pt2 = p[(i < p.length - 1) ? i + 1 : 0];

                  // find the line vectors of the lines going
                  // into the current point
                  var v01 = { x: pt1.x - pt0.x, y: pt1.y - pt0.y };
                  var v12 = { x: pt2.x - pt1.x, y: pt2.y - pt1.y };

                  // find the normals of the two lines, multiplied
                  // to the distance that polygon should inflate
                  var d01 = vecMul(vecUnit(rot(v01)), distance);
                  var d12 = vecMul(vecUnit(rot(v12)), distance);

                  // use the normals to find two points on the
                  // lines parallel to the polygon lines
                  var ptx0  = { x: pt0.x + d01.x, y: pt0.y + d01.y };
                  var ptx10 = { x: pt1.x + d01.x, y: pt1.y + d01.y };
                  var ptx12 = { x: pt1.x + d12.x, y: pt1.y + d12.y };
                  var ptx2  = { x: pt2.x + d12.x, y: pt2.y + d12.y };

                  // find the intersection of the two lines, and
                  // add it to the expanded polygon
                  expanded.push(intersect([ptx0, ptx10], [ptx12, ptx2]));
              }
              return expanded;
          }

          // drawing and animating a sample polygon on a canvas

          function drawPoly(p) {
              context.beginPath();
              context.moveTo(p[0].x, p[0].y);
              for (var i = 0; i < p.length; ++i) {
                  context.lineTo(p[i].x, p[i].y);
              }
              context.closePath();
              context.fill();
              context.stroke();
          }

          function drawPolyWithMargin(p, margin) {
              context.fillStyle = "rgb(255,255,255)";  
              context.strokeStyle = "rgb(200,150,150)";  
              drawPoly(expandPoly(p, margin));

              context.fillStyle = "rgb(150,100,100)";  
              context.strokeStyle = "rgb(200,150,150)";  
              drawPoly(p);
          }

          var p = [{ x: 100, y: 100 }, { x: 200, y: 120 }, { x: 80, y: 200 }];
          setInterval(function() {
              for (var i in p) {
                  var pt = p[i];
                  if (pt.vx === undefined) {
                      pt.vx = 5 * (Math.random() - 0.5);
                      pt.vy = 5 * (Math.random() - 0.5);
                  }

                  pt.x += pt.vx;
                  pt.y += pt.vy;

                  if (pt.x < 0 || pt.x > 400) { pt.vx = -pt.vx; }
                  if (pt.y < 0 || pt.y > 400) { pt.vy = -pt.vy; }
              }
              context.clearRect(0, 0, 800, 400);
              drawPolyWithMargin(p, 10);
          }, 50);
      }
  });

<html>
    <head>
            <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>
    </head>
    <body>
        <canvas id="canvas" width="400" height="400"></canvas>  
    </body>
</html>

示例代码免责声明：

• 为了清晰起见，该示例牺牲了一些效率。在您的代码中，您可能只想计算每条边的扩展并行一次，而不是像此处的两次

  ，

• 画布的 y 坐标向下增长，这会反转 CW/CCW 逻辑。不过事情仍然继续进行，因为我们只需要将外部法线转向与多边形相反的方向 - 并且两者都会翻转。

Answer 3

如果多边形以原点为中心，只需将每个点乘以公共比例因子即可。

如果多边形不是以原点为中心，则首先进行平移，使中心位于原点上，缩放，然后将其平移回原来的位置。

发表评论后

您似乎希望所有点都从原点移动相同的距离。
您可以通过获取该点的归一化向量来对每个点执行此操作。将其乘以“扩展常数”，并将所得向量加回原始点。

注意：如果中心不是该解决方案的原点，您仍然需要平移-修改-平移。

Answer 4

对于原图的每个线段，找到该线段的中点 m 和（单位长度）向外法线 u。扩展多边形的相应线段将位于通过 m+n*u（您要将原始多边形扩展 n）与法向 u 的直线上。要找到扩展多边形的顶点，您需要找到连续线对的交点。

Answer 5

设多边形的点为 A1、B1、C1...现在有从 A1 到 B1 的线，然后从 B1 到 C1...我们要计算多边形 P2 的点 A2、B2、C2。

如果平分角度，例如 A1 B1 C1，您将得到一条沿您想要的方向延伸的线。现在你可以在它上面找到一个点B2，它是等分线上距B1的适当距离。
对多边形 P1 的所有点重复此操作。