2

如果给定一个n边多边形和一条长度线k（在x,y和角度a），是否有一种算法可以检测我与多边形的哪一侧（如果有）发生碰撞？到目前为止，我已经求助于测试是否x,y在多边形之外，然后遍历多边形的每个边缘，计算到每一端的距离。这是一个展示我创建的世界的JS Fiddle 。

这是 JavaScript（HTML 和 CSS 并不值得复制）：

var eventLoop,
    maxVelocity = 10,
    agility = 5,
    baseLength = 5,
    degree = ((2*Math.PI)/360),
    world = document.getElementById('world'),
    context = world.getContext("2d"),
    boundry = [[180, 120],[240, 60],[360, 40],[420, 120],[360, 220],[350, 240],[360, 265],[470,360],[450,480],[360,540],[240,550],[140,480],[120,470],[100,360],[120,300],[220,240],[240,220]],
    camera = {
        location: {
            x:300,
            y:90
        },
        angle: 0,
        velocity: 0
    },
    engine = {
        drawWorld: function(shape, context) {
            var point,
                index,
                size = shape.length;

            context.clearRect(0, 0, world.width, world.height);
            context.beginPath();
            for(index = 0; index < size; index++) {
                point = shape[index];
                if(index == 0) {
                    context.moveTo(point[0], point[1]);
                } else {
                    context.lineTo(point[0], point[1]);
                }
            }
            context.closePath();
            context.stroke();
        },
        drawCamera: function(camera, context) {
            var a = camera.location,
                b = this.calcNextPoint(camera, 1);

            context.beginPath();
            context.moveTo(a.x, a.y);
            context.lineTo(b.x, b.y);
            context.stroke();

            context.beginPath();
            context.arc(a.x, a.y, baseLength, 0, Math.PI*2, true); 
            context.closePath();
            context.stroke();
        },
        calcNextPoint: function(camera, moment) {
            return {
                x: camera.location.x + ((camera.velocity*(1/moment))*Math.sin(camera.angle)),
                y: camera.location.y + ((camera.velocity*(1/moment))*(Math.cos(camera.angle)))
            };
        },
        isInside: function(point, shape) {
            var i, j, c = 0;
            for (i = 0, j = shape.length - 1; i < shape.length; j = i++) {
                if (((shape[i][1] > point.y) != (shape[j][1] > point.y)) && (point.x < (shape[j][0] - shape[i][0]) * (point.y - shape[i][1]) / (shape[j][1] - shape[i][1]) + shape[i][0])) {
                     c = !c;
                }
            }
            return c;
        }
    };

document.onkeydown = function(e) {
    e = e || window.event;
    if (e.keyCode == '37') {
        // left arrow
        camera.angle += degree*agility;
    }
    else if (e.keyCode == '39') {
        // right arrow
        camera.angle -= degree*agility;
    }
    else if (e.keyCode == '38') {
        // up arrow
        camera.velocity += 1;
        if(camera.velocity > maxVelocity) {
            camera.velocity = maxVelocity;
        }
    }
    else if (e.keyCode == '40') {
        // down arrow
        camera.velocity -= 1;
        if(camera.velocity < 0) {
            camera.velocity = 0;
        }
    }
}

engine.drawWorld(boundry, context);
engine.drawCamera(camera, context);

eventLoop = setInterval(function() {
    engine.drawWorld(boundry, context);
    engine.drawCamera(camera, context);
    if(engine.isInside(camera.location, boundry)) {
        camera.location = engine.calcNextPoint(camera, 1);
    }
}, 100);

我一直在玩弄一些 JavaScript 来模拟 ThatGameComapny 的游戏Flower的 2-Dementional 版本，最终我想尝试实现一个 Oculus Rift 版本。我要解决的下一个问题是，一旦玩家与边缘发生碰撞，就将其转回多边形。

4

3 回答 3

6

所以你基本上想知道多边形的哪些边与给定的线相交，对吧？

这只是对表示边缘的一些线性方程（更准确地说是不等式）的非常简单的处理。您已经有一个很好的inside操作实现，它也可以做到这一点。所有这些算法的共同点是比较直线的哪一侧[x1, y1]——[x2, y2]重点[x, y]在于：

compare = function (a, b) { // classical compare function, returns -1, 0, 1
    return a < b ? -1 : (a == b ? 0 : 1);
}
...
_lineSide: function (x, y, x1, y1, x2, y2) {
    return compare(x - x1, (x2 - x1) * (y - y1) / (y2 - y1));
}

[x, y]如果位于[x1, y1]-线的一侧，此函数将返回 -1，在另一侧返回 1 [x2, y2]，如果正好位于线上，则返回 0。这里不重要哪一边是哪一边，只是为了将它们分开。y2 - y1然而，当为零或接近零时，这将不起作用。在这种情况下，您必须 xy 翻转情况：

lineSide: function (x, y, x1, y1, x2, y2) {
    var eps = 1e-20; // some very small number
    if (Math.abs(y2 - y1) > eps)       // this way we avoid division by small number
        return _lineSide(x, y, x1, y1, x2, y2);
    else if (Math.abs(x2 - x1) > eps)  // flip the situation for horizontal lines
        return _lineSide(y, x, y1, x1, y2, x2);
    else // edge has close-to-zero length!
        throw new this.zeroLengthLineException()
},
zeroLengthLineException: function () {},

现在测试两条线是否[x1, y1]相交[x2, y2]非常容易[x3, y3]。[x4, y4]看看 if [x1, y1]and[x2, y2]位于[x3, y3]-的对面[x4, y4]，if [x3, y3]and位于-[x4, y4]的对面。如果是，那么线条相交！[x1, y1][x2, y2]

// proper: true/false (default false) - if we want proper intersection, i.e. just 
// touching doesn't count
linesIntersect: function (x1, y1, x2, y2, x3, y3, x4, y4, proper) {
    var min_diff = proper ? 2 : 1;
    return Math.abs(this.lineSide(x1, y1, x3, y3, x4, y4) - 
                    this.lineSide(x2, y2, x3, y3, x4, y4)) >= min_diff 
        && Math.abs(this.lineSide(x3, y3, x1, y1, x2, y2) - 
                    this.lineSide(x4, y4, x1, y1, x2, y2)) >= min_diff;
},

最终解决方案 - http://jsfiddle.net/gLTpT/7/

现在，最终的解决方案linesIntersect很简单：只需通过调用循环检查给定线与所有多边形边的交点：

http://jsfiddle.net/gLTpT/7/

在此处输入图像描述

于 2014-01-03T16:03:32.510 回答
1

一个通用的 LS 到 LS 测试将包括确定多边形端点 P[i], P[i+1] 是否位于向量 (p, p+d) 的不同侧，其中 d 是方向向量。为了使线相交，相反的情况也必须成立：(p, p+d) 都必须在线段 P[i], P[i+1] 的不同侧。

  o  P[i]              Here P[i], P[i+1] are on different side of p -> q=p+d
   \                   but not the opposite.
    \     q__----p
     \
      o  P[i+1]

在复杂或凹面场景中，向量可以跨越多个段，并且需要求解最近的段。这最容易从参数方程中完成

  (x0, y0) + (t * dx, t * dy) == i[0] + u * (i[1]-i[0]), j[0] + u * (j[1]-j[0])

编辑 比较点 (i[n],j[n]) 与线 (x0,y0) -> (x0 + dx, x1 +dy) 的有符号距离需要两个点积和符号比较。

  sameSide = sign((i0-x0)*(-dy)+(j0-y0)*dx) == sign((i1-x0)*(-dy)+(j1-y0)*dx))

在 javascript 中，这可能通过a * b > 0, wherea和bare 符号在比较中的表达式来最有效地完成。

于 2014-01-03T08:42:11.460 回答
1

这是一个小库，可以满足您的需要。我还将该库合并到您的程序的重写中。它在这个 Gist中，您可以下载并在浏览器中打开它。（我一直想永远尝试 HTML5 画布图形。谢谢你给我这个灵感！）

也在JS Fiddle 中运行。

该库使用一些线性代数来查找两条线段的交点，如果它存在，或者告诉你它是否不存在。要确定碰撞的位置，只需检查边界的每个边缘与从相机位置到您将要占据的位置的线段。如果有相交，就会发生碰撞。

如果您的相机正在迈出大步，或者如果您试图确定子弹在发射前会撞击的位置，那么您确实需要担心一步越过多个边缘并在几个可能的交叉点中找到正确的一个的可能性。然而，这个小库使它很容易做到这一点。说你的步骤是a-->b。然后跟踪最小相交参数t_ab。这个给你正确的碰撞边缘和碰撞点。

我用动画中的浅灰色线段做到了这一点。

我的代码只是检查是否有任何交叉点，如果找到，则会阻止该步骤被采取，因此相机会在距离超出边界的情况下停止部分步骤。

一个更有趣和有趣的尝试是将相机移动到确切的交点，然后计算物理上正确的“反弹”方向，使其继续移动，撞击墙壁。如果你想知道它是如何工作的，问我可以告诉你。

有更好（更快）的方法来进行碰撞检测，但是这个简单的方法对于这个小程序中的段数来说效果很好。请参阅 Gino Van Den Bergen 的经典“交互式 3D 环境中的碰撞检测”，以获得对这个主题的良好处理。他的讨论显然是针对 3D 的，但这些想法在 2D 中运行良好，而且他的许多示例也在 2D 中。

var lib = {
  // Find parameters of intersection of segments a->b and c->d or null for parallel lines
  intersectionParams: function(a, b, c, d) {
    var dx_ab = b.x - a.x
    var dy_ab = b.y - a.y
    var dx_dc = c.x - d.x
    var dy_dc = c.y - d.y
    var eps = 0.00001
    var det = dx_ab * dy_dc - dx_dc * dy_ab
    if (-eps < det && det < eps) return null
    var dx_ac = c.x - a.x
    var dy_ac = c.y - a.y
    var t_ab = (dx_ac * dy_dc - dx_dc * dy_ac) / det
    var t_cd = (dx_ab * dy_ac - dx_ac * dy_ab) / det
    return { t_ab: t_ab, t_cd: t_cd }
  },

  // Determine if intersection parameters represent an intersection.
  // This always counts parallel lines as non-intersecting even if they're touching.
  areIntersecting: function(ip) {
    return ip != null && 0 <= ip.t_ab && ip.t_ab <= 1 && 0 <= ip.t_cd && ip.t_cd <= 1
  },

  // Find the intersection from its parameters and two points.
  intersection: function(ip, a, b) {
    return { x: a.x + ip.t_ab * (b.x - a.x), y: a.y + ip.t_ab * (b.y - a.y) }
  }
}
于 2014-01-07T07:40:10.563 回答