扩展凸多边形的填充 [英] Expand fill of convex polygon
问题描述
我有一个 N 个点的凸多边形 P1.这个多边形可以是任何形状或比例(只要它仍然是凸面的).
我需要使用原始多边形几何体计算另一个多边形 P2，但扩展"了给定数量的单位.扩展凸多边形的算法可能是什么?
要扩展一个凸多边形，请画一条平行于每条边和给定数量单位的线.然后使用新线的交点作为扩展多边形的顶点.最后的 javascript/canvas 遵循这个功能分解:
第 1 步:找出哪一侧出局"
顶点(点)的顺序很重要.在凸多边形中，它们可以按顺时针 (CW) 或逆时针 (CCW) 顺序列出.在 CW 多边形中，将其中一条边旋转 90 度 CCW 以获得向外的法线.在逆时针多边形上，改为CW.
如果事先不知道顶点的转向方向，请检查第二条边如何从第一条边转向.在凸多边形中，剩余的边会一直向同一个方向转动:
法线，使其长度变为一个单位
将法线乘以我们希望扩展多边形与原始多边形的距离
将相乘法线添加到边缘的两端.这将给我们平行线上的两个点.这两点足以定义平行线.
代码:
//给定两个顶点 pt0 和 pt1，一个期望的距离，和一个函数 rot()//将向量向外旋转 90 度:函数 vecUnit(v) {var len = Math.sqrt(v.x * v.x + v.y * v.y);返回 { x: v.x/len, y: v.y/len };}函数 vecMul(v, s) {返回 { 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)), 距离);//乘法单位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 步:计算平行线的交点
--这些将是展开多边形的顶点.
数学:
一条线经过两点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.yb1 = P3.x - P4.x b2 = P3.y - P4.yc1 = P3.x - P1.x c2 = P3.y - P1.y这将我们的方程式缩短为:
a1*t + b1*u = c1a2*t + b2*u = c2解决 t 得到我们:
t = (b1*c2 - b2*c1)/(a2*b1 - a1*b2)这让我们在 P = P1 + t * (P2 - P1) 处找到交点.
代码:
函数相交(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;变量 t = (b1*c2 - b2*c1)/(a2*b1 - a1*b2);返回 {x: line1[0].x + t * (line1[1].x - line1[0].x),y: line1[0].y + t * (line1[1].y - line1[0].y)};}第 4 步:处理特殊情况
有一些特殊情况值得关注.留给读者作为练习......
当两条边之间的角度非常锐利时，展开后的顶点可能与原来的顶点相差非常.如果超出某个阈值，您可能需要考虑剪裁扩展的边缘.在极端情况下，角度为零，这表明扩展的顶点在无穷大，导致在算术中被零除.小心.
当前两条边在同一条线上时，你无法通过观察它们来判断它是顺时针多边形还是逆时针多边形.查看更多边缘.
非凸多边形更有趣……这里不讨论.
完整示例代码
将它放到支持画布的浏览器中.我在 Windows 上使用了 Chrome 6.三角形及其扩展版本应该是动画的.
canvas { border: 1px solid #ccc;}$(function() {var canvas = document.getElementById('canvas');如果(canvas.getContext){var context = canvas.getContext('2d');//扩展多边形的数学函数 vecUnit(v) {var len = Math.sqrt(v.x * v.x + v.y * v.y);返回 { x: v.x/len, y: v.y/len };}函数 vecMul(v, s) {返回 { x: v.x * s, y: v.y * s };}函数 vecDot(v1, v2) {返回 v1.x * v2.x + v1.y * v2.y；}函数 vecRot90CW(v) {返回 { x: v.y, y: -v.x };}函数 vecRot90CCW(v) {返回 { x: -v.y, y: v.x };}功能相交(线1，线2){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;变量 t = (b1*c2 - b2*c1)/(a2*b1 - a1*b2);返回 {x: line1[0].x + t * (line1[1].x - line1[0].x),y: line1[0].y + t * (line1[1].y - line1[0].y)};}函数 polyIsCw(p) {返回矢量点(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;}函数expandPoly(p，距离){变种扩展 = [];var rot = polyIsCw(p) ?vecRot90CCW : vecRot90CW;for (var i = 0; i 0) ?i - 1 : p.length - 1];变量 pt1 = p[i];var pt2 = p[(i 400) { pt.vx = -pt.vx;}如果 (pt.y <0 || pt.y > 400) { pt.vy = -pt.vy;}}context.clearRect(0, 0, 800, 400);drawPolyWithMargin(p, 10);}, 50);}}); <html><头><script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script></头><身体><canvas id="canvas" width="400" height="400"></canvas></身体></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.
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>
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屋！
