概括
这个问题是用 JavaScript 写的，但是用任何语言、伪代码或数学来回答都会很棒！
我一直在尝试实现分离轴定理来完成以下任务：
- 检测凸多边形和圆之间的交点。
- 找出可应用于圆的平移以解决相交问题，使圆几乎不接触多边形，但不再在内部。
- 确定碰撞的轴（问题末尾的详细信息）。
我已成功完成第一个要点，您可以在问题末尾看到我的 javascript 代码。我在其他部分有困难。
解决交集
网上有很多关于如何解决圆最小/最短重叠方向上的交点的例子。您可以在最后的代码中看到我已经计算过了。
但是，这不适合我的需要。我必须解决与圆轨迹相反方向的碰撞（假设我已经有了圆的轨迹，并希望将它作为单位向量或角度传递给我的函数，以适合者为准）。
您可以在下图中看到最短分辨率和预期分辨率之间的差异：
如何计算最小平移向量以解决test_CIRCLE_POLY函数内部的交点，但这将应用于特定方向，与圆的轨迹相反？
我的想法/尝试：
- 我的第一个想法是在必须在 SAT 算法中测试的轴上添加一个附加轴，该轴将垂直于圆的轨迹。然后我会在投影到这个轴上时根据重叠来解决。这会有点工作，但在大多数情况下会解决得很远。它不会导致最低翻译。所以这不会令人满意。
- 我的第二个想法是继续使用最短重叠的幅度，但将方向更改为与圆的轨迹相反。这看起来很有希望，但可能有很多我没有考虑到的极端情况。也许这是一个不错的起点。
确定碰撞侧/轴
我想出了一种方法来确定圆与多边形的哪些边相撞。对于多边形的每个测试轴，我会简单地检查重叠。如果有重叠，那一侧就会发生碰撞。
这个解决方案将不再被接受，因为我只想根据圆的轨迹找出一侧。
我的预期解决方案会告诉我，在下面的示例图像中，轴 A 是碰撞轴，而不是轴 B。这是因为一旦解决了交点，轴 A 就是对应于多边形边的轴只是勉强接触到圆圈。
我的想法/尝试：
目前我假设碰撞轴垂直于 MTV（最小平移向量）。这目前是不正确的，但是一旦我在问题的前半部分更新了交叉点解析过程，它应该是正确的轴。所以这部分应该首先解决。
或者，我考虑从圆的先前位置及其当前位置+半径创建一条线，并检查哪些边与这条线相交。但是，仍然存在歧义，因为有时会有不止一侧与线相交。
到目前为止我的代码
function test_CIRCLE_POLY(circle, poly, circleTrajectory) {
// circleTrajectory is currently not being used
let axesToTest = [];
let shortestOverlap = +Infinity;
let shortestOverlapAxis;
// Figure out polygon axes that must be checked
for (let i = 0; i < poly.vertices.length; i++) {
let vertex1 = poly.vertices[i];
let vertex2 = poly.vertices[i + 1] || poly.vertices[0]; // neighbouring vertex
let axis = vertex1.sub(vertex2).perp_norm();
axesToTest.push(axis);
}
// Figure out circle axis that must be checked
let closestVertex;
let closestVertexDistSqr = +Infinity;
for (let vertex of poly.vertices) {
let distSqr = circle.center.sub(vertex).magSqr();
if (distSqr < closestVertexDistSqr) {
closestVertexDistSqr = distSqr;
closestVertex = vertex;
}
}
let axis = closestVertex.sub(circle.center).norm();
axesToTest.push(axis);
// Test for overlap
for (let axis of axesToTest) {
let circleProj = proj_CIRCLE(circle, axis);
let polyProj = proj_POLY(poly, axis);
let overlap = getLineOverlap(circleProj.min, circleProj.max, polyProj.min, polyProj.max);
if (overlap === 0) {
// guaranteed no intersection
return { intersecting: false };
}
if (Math.abs(overlap) < Math.abs(shortestOverlap)) {
shortestOverlap = overlap;
shortestOverlapAxis = axis;
}
}
return {
intersecting: true,
resolutionVector: shortestOverlapAxis.mul(-shortestOverlap),
// this resolution vector is not satisfactory, I need the shortest resolution with a given direction, which would be an angle passed into this function from the trajectory of the circle
collisionAxis: shortestOverlapAxis.perp(),
// this axis is incorrect, I need the axis to be based on the trajectory of the circle which I would pass into this function as an angle
};
}
function proj_POLY(poly, axis) {
let min = +Infinity;
let max = -Infinity;
for (let vertex of poly.vertices) {
let proj = vertex.projNorm_mag(axis);
min = Math.min(proj, min);
max = Math.max(proj, max);
}
return { min, max };
}
function proj_CIRCLE(circle, axis) {
let proj = circle.center.projNorm_mag(axis);
let min = proj - circle.radius;
let max = proj + circle.radius;
return { min, max };
}
// Check for overlap of two 1 dimensional lines
function getLineOverlap(min1, max1, min2, max2) {
let min = Math.max(min1, min2);
let max = Math.min(max1, max2);
// if negative, no overlap
let result = Math.max(max - min, 0);
// add positive/negative sign depending on direction of overlap
return result * ((min1 < min2) ? 1 : -1);
};
