扩展凸多边形填充

Question

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

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

- Adam Harte

Answer 1

要扩展一个凸多边形，需要沿着每条边绘制一条平行线，并使其与给定的距离相同。然后将新线的交点用作扩展多边形的顶点。下面是javascript/canvas代码的功能分解：

步骤1：找出哪一侧是“外侧”

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

如果事先不知道顶点的转向方向，请检查第二条边从第一条边开始的旋转方式。在凸多边形中，剩余的边将保持相同的方向旋转：

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的值得到：

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. 当前两条边在同一条直线上时，仅凭它们看不出是顺时针还是逆时针多边形。需要查看更多的边。

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逻辑。然而，事情还在继续工作，因为我们只需要将外法线翻转到多边形的相反方向 - 两者都被翻转。

- Oren Trutner

---

这非常完美，而且非常清晰！感谢您花费时间。您用什么软件绘制图表？或者您从哪里获取了这些图表？再次感谢。 - Adam Harte

很有趣。我之前没有看到过这个，但我需要类似的东西，所以我最终自己创建了完全相同的算法，现在我偶然发现了这个。 - bgw

作为我之前评论的延伸，Python实现包含在这里，并且（截至撰写本文）可以在这里找到实验性的Java端口。 - bgw

太棒了！不幸的是，该算法无法处理线交叉的多边形（例如http://jsfiddle.net/fgJdN/）。 - Ben Clayton

是的 - 如上所述，该算法仅适用于凸多边形（http://en.wikipedia.org/wiki/Convex_and_concave_polygons）。 它甚至不尝试应对复杂的凹多边形。 要解决这些更复杂的情况，可以参考https://dev59.com/iXNA5IYBdhLWcg3wC5Xh和http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf。 - Oren Trutner

Answer 2

如果多边形以原点为中心，则只需将每个点乘以一个公共缩放因子。

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

在您的评论之后

看起来您希望所有点都离原点相同的距离。 您可以通过获取到该点的归一化向量，将其乘以您的“扩展常数”，并将结果向量添加回原始点来完成每个点的操作。

请注意，如果中心不是原点，则仍需要进行平移-修改-平移以解决此问题。

- CiscoIPPhone

---

这个解决方案的问题是，新形状在所有边缘上不会均匀扩展。在一个100x1的矩形上，垂直和水平的差异将非常不同。 - Adam Harte

是的，如果你将一个100x1的图像放大150%，那么你会得到一个150x1.5的图像。我猜你想要以50%的比例扩展100x1 -> 150x51？我会编辑这个答案。 - CiscoIPPhone

Answer 3

对于原始多边形的每条线段，找到中点m和（单位长度）外向法线u。扩展多边形的相应线段将位于通过m + n * u（其中n为您要扩展原始的数量）的直线上，并且具有法线u。然后，要找到扩展多边形的顶点，您需要找到相邻线段的交点。

- dmuir

Answer 4

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

如果你平分角度，比如A1 B1 C1，你会得到一条朝向所需方向的线。现在你可以在其中找到一点B2，使其与平分线上的B1合适地距离。 对于多边形P1的所有点重复此过程。

- Branimir

---

谢谢您的回答。您能否详细说明一下“现在您可以在其上找到一个点B2，该点与角平分线上的B1距离适当”的含义？我如何找到“适当”的距离？以及如何找到角平分线？谢谢。 - Adam Harte

你可以使用角平分线定理找到角的平分线：http://zh.wikipedia.org/wiki/角平分线定理 当你得到平分线的方程后，你可以计算出距离上的B2点，距离为"给定的单位数量"。 http://zh.wikipedia.org/wiki/距离 - Branimir

Answer 5

看看直线骨架。正如在这里所暗示的，非凸多边形存在许多棘手的问题，你已经幸免于难了！

- Max Palmer

---

我应该关注直线骨架的哪些方面？ - Adam Harte

这是一个用于膨胀和收缩多边形的算法。直线骨架定义了节点沿着多边形扩展/缩小的轴线移动的方式。虽然在您的情况下，处理凸多边形可能会过度设计。当我研究它时，我发现描述忽略了一些边缘情况，我不得不添加代码来解决这些问题。例如，当多边形轮廓的一个部分的尖端通过多边形的另一个部分的边缘扩展时。 - Max Palmer

这篇文章值得一读。它还链接到我写的博客文章。https://dev59.com/iXNA5IYBdhLWcg3wC5Xh - Max Palmer

一个关于一些棘手案例的博客直链：http://roombuilder.blogspot.com/2008/09/breakthrough-external-straight-skeleton.html - Max Palmer