13
我有一个凸多边形P1N点。这个多边形可以是任何形状或比例（只要它仍然是凸的）。展开填充凸多边形
我需要使用原始多边形几何体计算另一个多边形P2，但是按给定数量的单位“扩展”。该算法可能会用于扩展凸多边形吗？
Q
展开填充凸多边形
A
回答
36
要展开的凸多边形，画出平行的线每个边缘和单位的给定数量的路程。然后使用新线的交点作为展开的多边形的顶点。在端部的JavaScript /画布遵循此功能细分：
步骤1：找出哪一方是“出”
顶点（点）的事项的顺序。在凸多边形中，它们可以顺时针（CW）或逆时针（CCW）顺序列出。在CW多边形中，将其中一个边角90度CCW旋转以获得朝外法线。在CCW多边形上，改为将其替换为CW。
如果顶点的转弯方向被事先不知道，检查第二边缘从所述第一如何转动。在一个凸多边形，其余边缘将继续在同一方向转动：
Find the CW normal of the first edge。我们还不知道它是面向内部还是外部。
用我们计算的法线计算第二个边的dot product。如果第二个边缘顺时针旋转，则点积将为正值。否则将是否定的。
数学：
// 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：找到线平行于多边形边
现在我们知道哪一侧出了，我们可以计算出与每个多边形边缘平行的线条，恰好在所需距离处。这是我们的策略：
对于每条边，计算其朝外的正常
Normalize正常，使得其长度变为一个单位
乘以正常的，我们要的距离展开的多边形将从原始的
将相乘的法线添加到边的两端。这将在平行线上给我们两点。这两点足以定义平行线。
代码：
// 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步：用特殊的情况下
有许多是值得关注的特殊案件。作为练习留给读者......
当有两个边之间一个非常尖锐的角度，扩大顶点可以从原来的一个非常远。如果超出某个阈值，您可能需要考虑裁剪扩展边缘。在极端情况下，角度为零，这表明扩展顶点处于无穷大，导致算术除零。小心。
当前两个边缘位于同一条线上时，您不能通过只看它们来判断它是CW还是CCW多边形。看看更多的边缘。
非凸多边形更有趣...并没有在这里解决。
完整样本代码
在画布功能的浏览器掉落此。我在Windows上使用了Chrome 6。三角形及其扩展版本应该具有动画效果。
<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>
示例代码免责声明：
样品牺牲一些效率为清楚起见。在你的代码中，你可能想计算每条边的扩展并行只是一次，而不是这里的两倍。
画布的y坐标向下增长，这会反转CW/CCW逻辑。由于我们只需要将外部法线向与多边形相反的方向转动，并且两者都翻转，所以事情仍在继续。
0
设多边形的点为A1，B1，C1 ...现在你有从A1到B1，然后从B1到C1的直线......我们想计算多边形P2的点A2，B2，C2 。
如果你平分角度，例如A1 B1 C1，你将会有一条沿着你想要的方向走的线。现在你可以在它上面找到一个点B2，它是从平分线上B1的适当距离。 对多边形P1的所有点重复此操作。
+0
感谢您的回答。您能否详细介绍一下“现在您可以在其上找到一个与B1平分线上的距离B2”。我如何找到“适当”的距离？我如何找到平分线？谢谢。 – 2010-09-20 09:33:38
+0
您可以使用角平分线定理找到平分线：http://en.wikipedia.org/wiki/Angle_bisector_theorem当您得到平分线方程时，您可以在距离处以“给定数量的单位”计算点B2。 http://en.wikipedia.org/wiki/Distance – Branimir 2010-09-20 10:08:53
1
如果多边形以原点为中心，只需将每个点乘以一个公共缩放因子即可。
如果多边形未在原点上居中，则首先进行平移，以便中心在原点上缩放，然后将其转换回原来的位置。
您的评论
看来你希望所有点移动相同的距离远离原点之后。 您可以通过获得归一化矢量到这一点来为每个点做到这一点。把它乘以你的“扩展常数”，并将结果向量加回到原始点上。
n.b.如果中心不是该解决方案的原点，则仍需翻译 - 修改 - 翻译。
+0
这个解决方案的问题是，新形状不会在所有边缘均匀扩展。在一个矩形100x1上，垂直和水平差异将会非常不同。 – 2010-09-20 09:14:49
+0
是的，如果您将100x1缩放150％，您会获得150x1.5。我想你想100x1 - > 150x51如果扩大50？我会编辑这个答案。 – CiscoIPPhone 2010-09-20 09:56:19
1
对于原件的每个线段，找出段的中点m和（单位长度）向外正常u。扩展多边形的相应部分将位于通过m + n * u的线上（其中您想用n扩展原始数据）并使用正常的u。要找到展开的多边形的顶点，则需要找到相继的线对的交点。
0
看看直骨架。正如这里所暗示的那样，有一些非常棘手的问题，你可以毫不费力地使用非凸多边形！
+0
特别是我应该看的直骨骼呢？ – 2011-11-16 20:47:38
+0
这是一个用于膨胀和缩小多边形的算法。直骨架定义了多边形展开/收缩时节点沿其移动的轴。虽然在你的情况下，你正在处理凸多边形的事实可能会使它过度。当我研究它时，我发现忽略了处理几个边界情况的描述，我不得不为其添加代码。例如，当多边形轮廓的一部分的尖峰扩展穿过多边形的另一部分中的边缘时。 – 2011-11-17 17:12:00
+0
这篇文章值得一读。它还链接到我写的博客文章。 http://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-deflating-offsetting-buffering-polygons – 2011-11-17 17:13:53
相关问题
- 1. 填充多边形
- 2. 多边形填充算法
- 3. 凸3D多边形对象
- 4. 多边形C++的凸性？
- 5. Python：最小凸多边形？
- 6. 用矩形填充多边形
- 7. C＃填充多边形（三角形）
- 8. 填充没有填充多边形的三角形？
- 9. 的Java2D：填一个凸起的圆形多边形（QuadCurves）
- 10. 填充四边形
- 11. 填充凸形的有效方法
- 12. 用pyCairo填充多边形的多边形
- 13. 凸多边形，图形算法
- 14. 从矩形生成凸多边形
- 15. 创建用点填充的多边形
- 16. 如何绘制填充多边形？
- 17. 多边形不显示填充颜色
- 18. 填充多边形没有工作
- 19. 填充多边形的面积与Python
- 20. 调整多边形以填充画布
- 21. 在GDI中填充多边形
- 22. 通过热图填充多边形
- 23. 带孔洞的填充多边形
- 24. 填充多边形与一些颜色
- 25. 如何绘制填充的多边形？
- 26. 谷歌地球未填充多边形
- 27. 在矩阵中填充多边形
- 28. 如何在java中填充多边形？
- 29. OpenGL填充多边形颜色“流血”
- 30. vb6：用渐变填充多边形
这是完美的，非常清晰！感谢您抽出宝贵的时间。你用什么软件绘制图表？或者你从哪里得到图表？再次感谢。 – 2010-10-11 03:57:38
红色的多边形直接来自浏览器的画布。其余的用ms字拼凑在一起。 – 2010-10-11 04:43:36
这很有趣。我以前没见过这个，但是我需要类似的东西，所以我最终自己创建了完全相同的算法，现在我只是偶然发现了这个问题。 – bgw 2011-07-30 00:26:18