我正在尝试检测画布上的多边形。我使用的代码来自这个堆栈溢出问题https://stackoverflow.com/a/15308571/3885989
function Vec2(x, y) {
return [x, y]
}
Vec2.nsub = function (v1, v2) {
return Vec2(v1[0] - v2[0], v1[1] - v2[1])
}
// aka the "scalar cross product"
Vec2.perpdot = function (v1, v2) {
return v1[0] * v2[1] - v1[1] * v2[0]
}
// Determine if a point is inside a polygon.
//
// point - A Vec2 (2-element Array).
// polyVerts - Array of Vec2's (2-element Arrays). The vertices that make
// up the polygon, in clockwise order around the polygon.
//
function coordsAreInside(point, polyVerts) {
var i, len, v1, v2, edge, x
// First translate the polygon so that `point` is the origin. Then, for each
// edge, get the angle between two vectors: 1) the edge vector and 2) the
// vector of the first vertex of the edge. If all of the angles are the same
// sign (which is negative since they will be counter-clockwise) then the
// point is inside the polygon; otherwise, the point is outside.
for (i = 0, len = polyVerts.length; i < len; i++) {
v1 = Vec2.nsub(polyVerts[i], point)
v2 = Vec2.nsub(polyVerts[i + 1 > len - 1 ? 0 : i + 1], point)
edge = Vec2.nsub(v1, v2)
// Note that we could also do this by using the normal + dot product
x = Vec2.perpdot(edge, v1)
// If the point lies directly on an edge then count it as in the polygon
if (x < 0) {
return false
}
}
return true
}
它工作得很好,但是对于更复杂的形状,它就不那么好了…这里有一个链接到孤立的代码与一个例子,一个形状工作,另一个不工作:http://jsfiddle.net/snqF7/
啊!就像GameAlchemist说的,问题是这个算法是针对凸多边形的,这里有一个新的&&我从这些C代码示例(http://alienryderflex.com/polygon/)翻译的非凸(或复杂)多边形(不完美)的改进算法
function pointInPolygon(point, polyVerts) {
var j = polyVerts.length - 1,
oddNodes = false,
polyY = [], polyX = [],
x = point[0],
y = point[1];
for (var s = 0; s < polyVerts.length; s++) {
polyX.push(polyVerts[s][0]);
polyY.push(polyVerts[s][1]);
};
for (var i = 0; i < polyVerts.length; i++) {
if ((polyY[i]< y && polyY[j]>=y
|| polyY[j]< y && polyY[i]>=y)
&& (polyX[i]<=x || polyX[j]<=x)) {
oddNodes^=(polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x);
}
j=i;
}
return oddNodes;
}
,这里是一个工作小提琴:http://jsfiddle.net/snqF7/3/
您使用的算法要求多边形为凸形。
简而言之,凸意味着你可以在多边形的任意两点之间画一条线,所有的线都会在多边形内。
-或多或少是土豆或正方形:)-.
解决方案是要么将多边形分割成凸部分,要么采用更复杂的算法来处理非凸多边形。
要处理非凸多边形,思路是取一个你知道在多边形中(或不在多边形中)的参考点,然后在你的测试点和这个参考点之间画一条线,然后计算它与多边形段相交的次数和方向。计数+1或-1,如果最后的和为空,点在里面。