展开凸多边形的填充 [英] Expand fill of convex polygon

问题描述

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

我需要计算另一个多边形 P2 使用原始的多边形几何体，但按给定数量的单位扩大。这个算法可以用来展开一个凸多边形吗？

解决方案

要展开一个凸多边形，绘制一条平行于每个边的直线和给定数量的单位。然后使用新线的交点作为展开的多边形的顶点。第一步：找出哪一边是out。

$结束语javascript / canvas在这个功能分类之后：

b
$ b

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

1. 法线，使其长度变成一个单位




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



p>在边的两端添加乘法法线。这将在平行线上给我们两点。这两点足以定义平行线。

代码：

  //给定两个顶点pt0和pt1，一个所需的距离，以及一个函数rot（）
 //将矢量向外旋转90度：
 
函数vecUnit（v）{
 var len = Math.sqrt（vx * vx + vy * vy）; 
 return {x：v.x / len，y：v.y / len}; 
 
 
函数vecMul（v，s）{
 return {x：v.x * s，y：v.y * s}; 
} 
 
 var v01 = {x：pt1.x  -  pt0.x，y：pt1.y  -  pt0.y}; //边缘矢量
 var d01 = vecMul（vecUnit（rot（v01）），distance）; //乘以单位正常
 var ptx0 = {x：pt0.x + d01.x，y：pt0.y + d01.y}; // 
上的两个点var ptx1 = {x：pt1.x + d01.x，y：pt1.y + d01.y}; //平行线
  

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

- 这些将是展开多边形的顶点。 $ b

$ b $ / $>
$ b $ $ b

经过两点的线 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）
  pre> 
 
 
这可以按照如下方式处理： 
 
 
 （P2 -  P1）* t +（P3  -  P4）* u = P3  -  P1 
  
 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）。
 
 
 
代码：
 函数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）
}; 
} 
  
 第四步：处理特殊情况 p> 
 
 
有许多值得关注的特殊情况。作为练习留给读者...... 
 
 
 
当两个边缘之间存在非常尖锐的角度时，展开的顶点可以是很远远离原来的。如果超出某个阈值，您可能需要考虑裁剪扩展边缘。在极端情况下，角度为零，这表明扩展顶点处于无穷大，导致算术除零。注意。
  
 
 
当前两条边在同一条直线上时，只需看它们就无法判断它是CW还是CCW多边形。看看更多的边缘。
  
 
 
非凸多边形更有趣...并且在这里没有处理。 b 
 完整示例代码 
 
 
 
将其放在具有画布功能的浏览器中。我在Windows上使用了Chrome 6。该三角形及其扩展版本应具有动画效果。
 
 
 
  
 < html> 
< head> 
< style type =text / css> 
 canvas {border：1px solid #ccc; } 
< / style> 
< script type =text / javascriptsrc =http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js>< / script> 
< script type =text / javascript> 
 $（function（）{
 var canvas = document.getElementById（'canvas'）; 
 if（canvas.getContext）{
 var context = canvas.getContext（'2d '）; 
 
 //用于展开多边形的数学
 
函数vecUnit（v）{
 var len = Math.sqrt（vx * vx + vy * vy ）; 
 return {x：vx / len，y：vy / len}; 
} 
 
函数vecMul（v，s）{
 return {x： vx * s，y：vy * s}; 
} 
 
函数vecDot（v1，v2）{
 return v1.x * v2.x + v1.y * v2 .y; 
} 
 
函数vecRot90CW（v）{
 return {x：vy，y：-vx}; 
 } 
 
函数vecRot90CCW（v）{
 return {x：-v.y，y：v.x}; 
} 
 
函数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; 
 
（var i = 0; i< p.length; ++ i）{
 
 //得到这个点（pt1），它之前的点
 //（pt0）及其之后的点（pt2）
 var pt0 = p [（i> 0）？ i  -  1：p.length  -  1]; 
 var pt1 = p [i]; 
 var pt2 = p [（i  
 //找到行
 //到当前点的行向量
 var v01 = {x：pt1.x  -  pt0.x，y：pt1。 y  -  pt0.y}; 
 var v12 = {x：pt2.x  -  pt1.x，y：pt2.y  -  pt1.y}; 
 
 //找到两条线的法线，将
 //与多边形应该膨胀的距离相乘
 var d01 = vecMul（vecUnit（rot（v01）），distance ）; 
 var d12 = vecMul（vecUnit（rot（v12）），distance）; 
 
 //使用法线在平行于多边形线的
 //线上找到两个点
 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}; 
 
 //找到两条线的交点，
 //将其添加到展开的多边形
 expanded.push（intersect（[ptx0，ptx10]，[ptx12， PTX2]））; 
} 
返回已展开; 
 
 
 //在画布上绘制和设置示例多边形的动画效果
 
 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（）; 
} 
 
函数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）; 
} 
}）; 
< / script> 
< / head> 
< body> 
< canvas id =canvaswidth =400height =400>< / canvas> 
< / body> 
< / html> 
  
示例代码免责声明： 
 
 
 
 
 
为了清晰起见，该示例牺牲了一些效率。在你的代码中，你可能需要计算每条边的扩展平行线一次，而不是这里的两倍。
 
 
画布的y坐标向下增长，这反过来CW / CCW逻辑。事情继续进行，因为我们只需要向与多边形相反的方向转动向外法线，并且两者都会翻转过来。
  
 
 
I have a convex polygon P1 of N points. This polygon could be any shape or proportion (as long as it is still convex).

I need to compute another polygon P2 using the original polygons geometry, but "expanded" by a given number of units. What might the algorithm be for expanding a convex polygon?
解决方案


To expand a convex polygon, draw a line parallel to each edge and the given number of units away.  Then use the intersection points of the new lines as the vertices of the expanded polygon.  The javascript/canvas at the end follows this functional breakdown:

Step 1: Figure out which side is "out"

The order of the vertices (points) matters.  In a convex polygon, they can be listed in a clockwise (CW), or a counter-clockwise (CCW) order.  In a CW polygon, turn one of the edges 90 degrees CCW to obtain an outward-facing normal.  On a CCW polygon, turn it CW instead.



If the turn direction of the vertices is not known in advance, examine how the second edge turns from the first.  In a convex polygon, the remaining edges will keep turning in the same direction:

Find the CW normal of the first edge.  We don't know yet whether it's facing inward or outward.
Compute the dot product of the second edge with the normal we computed.  If the second edge turns CW, the dot product will be positive.  It will be negative otherwise.


Math:
// 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.
Code:
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;
Step 2: Find lines parallel to the polygon edges

Now that we know which side is out, we can compute lines parallel to each polygon edge, at exactly the required distance.  Here's our strategy:

For each edge, compute its outward-facing normal
Normalize the normal, such that its length becomes one unit
Multiply the normal by the distance we want the expanded polygon to be from the original
Add the multiplied normal to both ends of the edge.  That will give us two points on the parallel line.  Those two points are enough to define the parallel line.


Code:
// 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
Step 3: Compute the intersections of the parallel lines

--these will be the vertices of the expanded polygon.



Math:

A line going through two points P1, P2 can be described as:
P = P1 + t * (P2 - P1)
Two lines can be described as
P = P1 + t * (P2 - P1)
P = P3 + u * (P4 - P3)
And their intersection has to be on both lines:
P = P1 + t * (P2 - P1) = P3 + u * (P4 - P3)
This can be massaged to look like:
(P2 - P1) * t + (P3 - P4) * u = P3 - P1
Which in x,y terms is:
(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
As the points P1, P2, P3 and P4 are known, so are the following values:
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
This shortens our equations to:
a1*t + b1*u = c1
a2*t + b2*u = c2    
Solving for t gets us:
t = (b1*c2 - b2*c1)/(a2*b1 - a1*b2)
Which lets us find the intersection at P = P1 + t * (P2 - P1).

Code:
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)
    };
}
Step 4: Deal with special cases

There is a number of special cases that merit attention.  Left as an exercise to the reader...

When there's a very sharp angle between two edges, the expanded vertex can be very far from the original one.  You might want to consider clipping the expanded edge if it goes beyond some threshold.  At the extreme case, the angle is zero, which suggests that the expanded vertex is at infinity, causing division by zero in the arithmetic.  Watch out.
When the first two edges are on the same line, you can't tell if it's a CW or a CCW polygon by looking just at them.  Look at more edges.
Non convex polygons are much more interesting... and are not tackled here.
Full sample code

Drop this in a canvas-capable browser.  I used Chrome 6 on Windows.  The triangle and its expanded version should animate.

<html>
    <head>
            <style type="text/css">
                canvas { border: 1px solid #ccc; }
            </style>
            <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>
            <script type="text/javascript">
                $(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);
                    }
                });
            </script>
    </head>
    <body>
        <canvas id="canvas" width="400" height="400"></canvas>  
    </body>
</html>
sample code disclaimers:


the sample sacrifices some efficiency for the sake of clarity.  In your code, you may want to compute each edge's expanded parallel just once, and not twice as in here
the canvas's y coordinate grows downward, which inverts the CW/CCW logic.  Things keep on working though as we just need to turn the outward normals in a direction opposite to the polygon's -- and both get flipped.


                        
这篇关于展开凸多边形的填充的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！