SAT Polygon Circle Collision - 解决速度方向的交点并确定碰撞的一侧

4回答

jeck猫

我假设多边形是凸的，并且圆沿着直线移动（至少在一段可能很小的时间间隔内）并且没有遵循一些弯曲的轨迹。如果它遵循弯曲的轨迹，那么事情就会变得更加困难。在曲线轨迹的情况下，可以保留基本概念，但实际的碰撞点（圆的碰撞分辨率点）可能更难计算。不过，我正在概述一个想法，它也可以扩展到这种情况。另外，它可以作为圆和凸多边形之间碰撞检测的主要方法。我没有考虑所有可能的情况，可能包括特殊或极端的情况，但至少它给了你一个探索的方向。在你的脑海中将圆和多边形之间的碰撞转换为圆心（一个点）和一个由圆的半径加厚的多边形版本之间的碰撞r，即（i）多边形的每条边都是偏移的（翻译) 沿垂直于它的向量向外半径r并指向多边形外部，(ii) 顶点变成半径为的圆弧r，以多边形顶点为中心并连接适当的相邻偏移边的端点（基本上，放置半径的圆r在多边形的顶点并取它们的凸包）。现在，圆心的当前位置是C = [ C[0], C[1] ]并且它一直沿直线移动，方向矢量V = [ V[0], V[1] ]指向运动方向（或者如果您愿意，可以将其V视为圆在检测到的那一刻的速度）碰撞）。然后，有一个由向量方程定义的轴（或者说是一条射线 - 一条有向半线）X = C - t * V，其中t >= 0（该轴指向过去的轨迹）。基本上，这是通过中心点C并与向量对齐/平行的半线V。现在，分辨率点，即您要将圆圈移动到的点是轴X = C - t * V与加厚多边形边界相交的点。因此，您必须检查 (1) 第一个轴相交的边缘，然后 (2) 轴与与原始多边形顶点有关的圆弧相交。P = [ P[0], P[1], ..., P[N], P[0] ]假设多边形由逆时针方向的顶点数组给出。（1）对于原始多边形的每条边P[i-1]P[i]，与您的碰撞相关（这些可能是在检测到碰撞的顶点处相交的两条相邻边，或者在圆移动的情况下实际上可能是所有边非常高的速度并且您很晚才检测到碰撞，因此实际碰撞甚至没有发生在那里，我把这留给您，因为您更了解您的情况的细节）执行以下操作。您有作为输入数据：C = [ C[0], C[1] ]V = [ V[0], V[1] ]P[i-1] = [ P[i-1][0],  P[i-1][1] ]P[i] = [ P[i][0],  P[i][1] ]做：Normal = [ P[i-1][1] - P[i][1], P[i][0] - P[i-1][0] ];Normal = Normal / sqrt((P[i-1][1] - P[i][1])^2 + ( P[i][0] - P[i-1][0] )^2); // you may have calculated these alreadyQ_0[0] = P[i-1][0] + r*Normal[0];Q_0[1] = P[i-1][1] + r*Normal[1];Q_1[0] = P[i][0]+ r*Normal[0]; Q_1[1] = P[i][1]+ r*Normal[1]; 求解s, t线性方程组（相交方程）：Q_0[0] + s*(Q_1[0] - Q_0[0]) = C[0] - t*V[0];Q_0[1] + s*(Q_1[1] - Q_0[1]) = C[1] - t*V[1];如果0<= s <= 1和t >= 0，你就完成了，你的解决点是R[0] = C[0] - t*V[0];R[1] = C[1] - t*V[1];别的(2)对于与P[i]您的碰撞相关的每个顶点，请执行以下操作：求解t二次方程（有一个明确的公式）norm(P[i] - C + t*V )^2 = r^2或扩展：(V[0]^2 + V[1]^2) * t^2 + 2 * ( (P[i][0] - C[0])*V[0] + (P[i][1] - C[1])*V[1] )*t + ( P[i][0] - C[0])^2 + (P[i][1] - C[1])^2 )  - r^2 = 0或者，如果您更喜欢类似代码的方式：a = V[0]^2 + V[1]^2;b = (P[i][0] - C[0])*V[0] + (P[i][1] - C[1])*V[1];c = (P[i][0] - C[0])^2 + (P[i][1] - C[1])^2 - r^2;D = b^2 - a*c;if D < 0 there is no collision with the vertex i.e. no intersection between the line X = C - t*V and the circle of radius r centered at P[i]elseD = sqrt(D);t1 = ( - b - D) / a;t2 = ( - b + D) / a;  where t2 >= t1 那么你的解决点是R[0] = C[0] - t2*V[0];R[1] = C[1] - t2*V[1];

0 0

慕慕森

这可能不是您想要的，但这里有一种方法（如果您不是在寻找完美的精度）：您可以尝试近似位置而不是计算它。您设置代码的方式有一个很大的优势：在碰撞之前您拥有圆的最后位置。多亏了这一点，您可以通过轨迹“迭代”并尝试找到最接近交点位置的位置。我假设你已经有一个函数可以告诉你一个圆是否与多边形相交。代码（C++）：// What we need :Vector startPos; // Last position of the circle before the collisionVector currentPos; // Current, unwanted positionVector dir; // Direction (a unit vector) of the circle's velocityfloat distance = compute_distance(startPos, currentPos); // The distance from startPos to currentPos.Polygon polygon; // The polygonCircle circle; // The circle.unsigned int iterations_count = 10; // The number of iterations that will be done. The higher this number, the more precise the resolution.// The algorithm :float currentDistance = distance / 2.f; // We start at the half of the distance.Circle temp_copy; // A copy of the real circle to "play" with.for (int i = 0; i < iterations_count; ++i) {    temp_copy.pos = startPos + currentDistance * dir;    if (checkForCollision(temp_copy, polygon)) {        currentDistance -= currentDistance / 2.f; // We go towards startPos by the half of the current distance.    }    else {        currentDistance += currentDistance / 2.f; // We go towards currentPos by the half of the current distance.    }}    // currentDistance now contains the distance between startPos and the intersection point// And this is where you should place your circle :Vector intersectionPoint = startPos + currentDistance * dir;我没有测试过这段代码，所以我希望那里没有大错误。它也没有优化，并且这种方法存在一些问题（交点可能最终在多边形内）所以它仍然需要改进，但我认为你明白了。另一个（很大，取决于你在做什么）问题是它是一个近似值而不是一个完美的答案。

0 0

弑天下

圆多边形截距如果球在移动并且你可以确保球总是在多边形之外开始，那么解决方案就相当简单了。我们将球及其运动称为球线。它从球的当前位置开始，到球将在下一帧的位置结束。要解决此问题，您需要找到距球线起点最近的截距。拦截有两种。线段（球线）与线段（多边形边）带圆的线段（球线）（每个（仅凸）多边形角处的圆）示例代码有一个Lines2对象，其中包含两个相关的拦截函数。截距以Vec2包含两个单位距离的形式返回。截距函数用于线（无限长）而不是线段。如果没有拦截，则返回未定义。对于线截距Line2.unitInterceptsLine(line, result = new Vec2())，单位值 (in result) 是从起点开始沿每条线的单位距离。负值落后于开始。考虑到球半径，每个多边形边沿其法线偏移球半径。多边形边缘具有一致的方向很重要。在示例中，法线位于直线的右侧，多边形点位于顺时针方向。对于线段/圆的截距Line2.unitInterceptsCircle(center, radius, result = new Vec2())，单位值 (in result) 是沿直线与圆相交的单位距离。result.x将始终包含最近的截距（假设您从圆圈外开始）。如果有一个拦截，那么即使它们在同一点，也总是有两个。例子该示例包含所有需要的内容感兴趣的对象是ball和polyball定义球及其运动。也有代码来绘制它的例子poly保存多边形的点。根据球半径将点转换为偏移线。它被优化为仅在球半径发生变化时才计算线条。函数poly.movingBallIntercept是完成所有工作的函数。它需要一个球对象和一个可选的结果向量。Vec2如果它接触多边形，它将返回作为球的位置。它通过找到到偏移线和点（作为圆）的最小单位距离来做到这一点，并使用该单位距离来定位结果。请注意，如果球在多边形内，则与角的截距是相反的。该函数Line2.unitInterceptsCircle确实提供了线进入和退出圆圈的 2 个单位距离。但是，您需要知道您是在室内还是室外才能知道使用哪一个。该示例假设您在多边形之外。指示移动鼠标来改变球的路径。单击以设置球的起始位置。Math.EPSILON = 1e-6;Math.isSmall = val => Math.abs(val) < Math.EPSILON;Math.isUnit = u => !(u < 0 || u > 1);Math.TAU = Math.PI * 2;/* export {Vec2, Line2} */ // this should be a modulevar temp;function Vec2(x = 0, y = (temp = x, x === 0 ? (x = 0 , 0) : (x = x.x, temp.y))) {    this.x = x;    this.y = y;}Vec2.prototype = {    init(x, y = (temp = x, x = x.x, temp.y)) { this.x = x; this.y = y; return this }, // assumes x is a Vec2 if y is undefined    copy() { return new Vec2(this) },    equal(v) { return (this.x - v.x) === 0 && (this.y - v.y) === 0 },    isUnits() { return Math.isUnit(this.x) && Math.isUnit(this.y) },    add(v, res = this) { res.x = this.x + v.x; res.y = this.y + v.y; return res },    sub(v, res = this) { res.x = this.x - v.x; res.y = this.y - v.y; return res },    scale(val, res = this) { res.x = this.x * val; res.y = this.y * val; return res },    invScale(val, res = this) { res.x = this.x / val; res.y = this.y / val; return res },    dot(v) { return this.x * v.x + this.y * v.y },    uDot(v, div) { return (this.x * v.x + this.y * v.y) / div },    cross(v) { return this.x * v.y - this.y * v.x },    uCross(v, div) { return (this.x * v.y - this.y * v.x) / div },    get length() { return this.lengthSqr ** 0.5 },    set length(l) { this.scale(l / this.length) },    get lengthSqr() { return this.x * this.x + this.y * this.y },    rot90CW(res = this) {        const y = this.x;        res.x = -this.y;        res.y = y;        return res;    },};const wV1 = new Vec2(), wV2 = new Vec2(), wV3 = new Vec2(); // pre allocated work vectors used by Line2 functionsfunction Line2(p1 = new Vec2(), p2 = (temp = p1, p1 = p1.p1 ? p1.p1 : p1, temp.p2 ? temp.p2 : new Vec2())) {    this.p1 = p1;    this.p2 = p2;}Line2.prototype = {    init(p1, p2 = (temp = p1, p1 = p1.p1, temp.p2)) { this.p1.init(p1); this.p2.init(p2) },    copy() { return new Line2(this) },    asVec(res = new Vec2()) { return this.p2.sub(this.p1, res) },    unitDistOn(u, res = new Vec2()) { return this.p2.sub(this.p1, res).scale(u).add(this.p1) },    translate(vec, res = this) {        this.p1.add(vec, res.p1);        this.p2.add(vec, res.p2);        return res;    },    translateNormal(amount, res = this) {        this.asVec(wV1).rot90CW().length = -amount;        this.translate(wV1, res);        return res;    },    unitInterceptsLine(line, res = new Vec2()) {  // segments        this.asVec(wV1);        line.asVec(wV2);        const c = wV1.cross(wV2);        if (Math.isSmall(c)) { return }        wV3.init(this.p1).sub(line.p1);        res.init(wV1.uCross(wV3, c), wV2.uCross(wV3, c));        return res;    },    unitInterceptsCircle(point, radius, res = new Vec2()) {        this.asVec(wV1);        var b = -2 * this.p1.sub(point, wV2).dot(wV1);        const c = 2 * wV1.lengthSqr;        const d = (b * b - 2 * c * (wV2.lengthSqr - radius * radius)) ** 0.5        if (isNaN(d)) { return }        return res.init((b - d) / c, (b + d) / c);    },};/* END of file */ // Vec2 and Line2 module /* import {vec2, Line2} from "whateverfilename.jsm" */ // Should import vec2 and line2const POLY_SCALE = 0.5;const ball = {    pos: new Vec2(-150,0),    delta: new Vec2(10, 10),    radius: 20,    drawPath(ctx) {        ctx.beginPath();        ctx.arc(this.pos.x, this.pos.y, this.radius, 0, Math.TAU);        ctx.stroke();    },}const poly =  {    bRadius: 0,    lines: [],    set ballRadius(radius) {        const len = this.points.length        this.bRadius = ball.radius;        i = 0;        while (i < len) {            let line = this.lines[i];            if (line) { line.init(this.points[i], this.points[(i + 1) % len]) }            else { line = new Line2(new Vec2(this.points[i]), new Vec2(this.points[(i + 1) % len])) }            this.lines[i++] = line.translateNormal(radius);        }        this.lines.length = i;    },    points: [        new Vec2(-200, -150).scale(POLY_SCALE),        new Vec2(200, -100).scale(POLY_SCALE),        new Vec2(100, 0).scale(POLY_SCALE),        new Vec2(200, 100).scale(POLY_SCALE),        new Vec2(-200, 75).scale(POLY_SCALE),        new Vec2(-150, -50).scale(POLY_SCALE),    ],    drawBallLines(ctx) {        if (this.lines.length) {            const r = this.bRadius;            ctx.beginPath();            for (const l of this.lines) {                 ctx.moveTo(l.p1.x, l.p1.y);                ctx.lineTo(l.p2.x, l.p2.y);            }            for (const p of this.points) {                 ctx.moveTo(p.x + r, p.y);                ctx.arc(p.x, p.y, r, 0, Math.TAU);            }            ctx.stroke()        }    },    drawPath(ctx) {        ctx.beginPath();        for (const p of this.points) { ctx.lineTo(p.x, p.y) }        ctx.closePath();        ctx.stroke();    },    movingBallIntercept(ball, res = new Vec2()) {        if (this.bRadius !== ball.radius) { this.ballRadius = ball.radius }        var i = 0, nearest = Infinity, nearestGeom, units = new Vec2();        const ballT = new Line2(ball.pos, ball.pos.add(ball.delta, new Vec2()));        for (const p of this.points) {            const res = ballT.unitInterceptsCircle(p, ball.radius, units);            if (res && units.x < nearest && Math.isUnit(units.x)) { // assumes ball started outside poly so only need first point                nearest = units.x;                nearestGeom = ballT;            }        }        for (const line of this.lines) {            const res = line.unitInterceptsLine(ballT, units);            if (res && units.x < nearest && units.isUnits()) { // first unit.x is for unit dist on line                nearest = units.x;                nearestGeom = ballT;            }        }        if (nearestGeom) { return ballT.unitDistOn(nearest, res) }        return;    },}const ctx = canvas.getContext("2d");var w = canvas.width, cw = w / 2;var h = canvas.height, ch = h / 2requestAnimationFrame(mainLoop);// line and point for displaying mouse interaction. point holds the result if anyconst line = new Line2(ball.pos, ball.pos.add(ball.delta, new Vec2())), point = new Vec2();function mainLoop() {    ctx.setTransform(1,0,0,1,0,0); // reset transform    if(w !== innerWidth || h !== innerHeight){        cw = (w = canvas.width = innerWidth) / 2;        ch = (h = canvas.height = innerHeight) / 2;    }else{        ctx.clearRect(0,0,w,h);    }    ctx.setTransform(1,0,0,1,cw,ch);  // center to canvas    if (mouse.button) { ball.pos.init(mouse.x - cw, mouse.y - ch) }    line.p2.init(mouse.x - cw, mouse.y - ch);    line.p2.sub(line.p1, ball.delta);    ctx.lineWidth = 1;    ctx.strokeStyle = "#000"    poly.drawPath(ctx)    ctx.strokeStyle = "#F804"    poly.drawBallLines(ctx);               ctx.strokeStyle = "#F00"        ctx.beginPath();    ctx.arc(ball.pos.x, ball.pos.y, ball.radius, 0, Math.TAU);    ctx.moveTo(line.p1.x, line.p1.y);    ctx.lineTo(line.p2.x, line.p2.y);    ctx.stroke();    ctx.strokeStyle = "#00f"        ctx.lineWidth = 2;    ctx.beginPath();    if (poly.movingBallIntercept(ball, point)) {       ctx.arc(point.x, point.y, ball.radius, 0, Math.TAU);    } else {       ctx.arc(line.p2.x, line.p2.y, ball.radius, 0, Math.TAU);    }    ctx.stroke();               requestAnimationFrame(mainLoop);}const mouse = {x:0, y:0, button: false};function mouseEvents(e) {      const bounds = canvas.getBoundingClientRect();      mouse.x = e.pageX - bounds.left - scrollX;      mouse.y = e.pageY - bounds.top - scrollY;      mouse.button = e.type === "mousedown" ? true : e.type === "mouseup" ? false : mouse.button;}["mousedown","mouseup","mousemove"].forEach(name => document.addEventListener(name,mouseEvents));#canvas {  position: absolute;  top: 0px;  left: 0px;}<canvas id="canvas"></canvas>Click to position ball. Move mouse to test trajectory Vec2和Line2为了使其更容易，矢量库将有所帮助。对于示例，我编写了一个快速Vec2和Line2对象（注意仅示例中使用的函数已经过测试，注意该对象是为性能而设计的，没有经验的编码人员应避免使用这些对象并选择更标准的矢量和线库）

0 0

智慧大石

我不确定我是否正确理解了场景，但是一个有效的直接用例是，首先只使用圆形的正方形边界框，计算该正方形与多边形的交点非常快，快得多，而不是使用圆圈。一旦您检测到该正方形和多边形的交集，您需要考虑或编写最适合您的场景的精度。如果你需要比这个状态更好的精度，你可以从这里继续：从你的方形交叉点的 90° 角，你画一条 45° 的线，直到它接触你的圆，此时，它在哪里触摸，你画了一个新的正方形，但是这一次，正方形嵌入到圆中，现在让它运行，直到这个新的正方形与多边形相交，一旦相交，你就有了一个保证的圆相交。根据您需要的精度，您可以像这样简单地玩耍。我不确定你的下一个问题是什么？如果它只能是圆形轨迹的倒数，那么它必须是那个倒数，我真的不确定我在这里错过了什么。

0 0