标签: separating-axis-theorem

我正在寻找一种算法来检测两个矩形是否相交(一个是任意角度,另一个只有垂直/水平线).

测试一个角落是否在另一个ALMOST中.如果矩形形成十字形状,则失败.

避免使用线条的斜率似乎是一个好主意,这需要垂直线条的特殊情况.

我不知道从哪里开始.显然CGRectIntersectsRect在这种情况下不起作用,你会明白为什么.

我有一个UIView的子类,里面有一个UIImageView,放在UIView的确切中心:

然后我旋转自定义UIView以维持内部UIImageView的框架,同时仍然能够执行CGAffineRotation.结果框架看起来像这样:

我需要阻止用户使这些UIImageViews相交,但我不知道如何检查两个UIImageViews之间的交集,因为它们的框架不仅不适用于父UIView,而且它们在不影响其框架的情况下旋转.

我尝试的唯一结果是不成功的.

有任何想法吗？

概括

这个问题是用 JavaScript 编写的，但是用任何语言、伪代码或数学来回答都会很棒！

我一直在尝试实施Separating-Axis-Theorem来完成以下工作：

• 检测凸多边形和圆之间的交点。
• 找出可以应用于圆的平移以解决交点，以便圆几乎不接触多边形但不再在内部。
• 确定碰撞轴（问题末尾的详细信息）。

我已成功完成第一个要点，您可以在问题末尾看到我的 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 …

问题在于Polygon::FindAxisLeastPenetration:

double Polygon::FindAxisLeastPenetration(unsigned int *faceIndex, const Polygon &polygonA, const Polygon &polygonB) const {
  double bestDistance = -std::numeric_limits<double>::infinity();
  unsigned int bestIndex;

  for (unsigned int i = 0; i < polygonA.points.size(); i++) {
    Vector2D n = polygonA.normals[i];
    Vector2D nw = polygonA.rotationMatrix * n; //ROTATION
    Matrix22 buT = polygonB.rotationMatrix.Transposed();
    n = buT * nw; //ROTATION

    Vector2D support = polygonB.points[polygonB.GetSupport(-n)];

    Vector2D vertex = polygonA.points[i];
    vertex = polygonA.rotationMatrix * vertex; //ROTATION
    vertex.Add(polygonA.body->GetPosition());
    vertex.Subtract(polygonB.body->GetPosition());
    vertex = buT * vertex; // ROTATION
    double distance = …

前提：我正在构建一个裁剪工具，可以处理图像的两指任意旋转以及任意裁剪。

有时，图像最终会以插入空白空间的方式旋转，以填充旋转图像和裁剪矩形之间的间隙（请参阅下面的示例）。

我需要确保图像视图在旋转时完全适合裁剪矩形。如果没有，我需要重新转换图像（缩放）以使其适合裁剪范围。

使用这个答案，我实现了检查旋转的 UIImageView 是否与裁剪 CGRect 相交的功能，但不幸的是，这并没有告诉我裁剪矩形是否完全包含在旋转的图像视图中。希望我可以对此答案进行一些简单的修改？

OK 的直观示例：

不好，我需要检测和处理：

更新：不起作用的方法

- (BOOL)rotatedView:(UIView*)rotatedView containsViewCompletely:(UIView*)containedView {

    CGRect rotatedBounds = rotatedView.bounds;
    CGPoint polyContainedView[4];

    polyContainedView[0] = [containedView convertPoint:rotatedBounds.origin toView:rotatedView];
    polyContainedView[1] = [containedView convertPoint:CGPointMake(rotatedBounds.origin.x + rotatedBounds.size.width, rotatedBounds.origin.y) toView:rotatedView];
    polyContainedView[2] = [containedView convertPoint:CGPointMake(rotatedBounds.origin.x + rotatedBounds.size.width, rotatedBounds.origin.y + rotatedBounds.size.height) toView:rotatedView];
    polyContainedView[3] = [containedView convertPoint:CGPointMake(rotatedBounds.origin.x, rotatedBounds.origin.y + rotatedBounds.size.height) toView:rotatedView];

    if (CGRectContainsPoint(rotatedView.bounds, polyContainedView[0]) &&
        CGRectContainsPoint(rotatedView.bounds, polyContainedView[1]) &&
        CGRectContainsPoint(rotatedView.bounds, polyContainedView[2]) &&
        CGRectContainsPoint(rotatedView.bounds, polyContainedView[3]))
        return YES;
    else
        return NO;
}

因此,我一直在尝试使用分离轴定理在我的游戏项目中使用碰撞检测和响应.我设法发现了碰撞,但是对于我的生活,我无法弄清楚如何应对它.我试图找到最小翻译向量,但我不知道如何使它成为一个实际向量,以便我可以计算如何响应碰撞.我已经阅读了教程后的教程,我在这里看了许多以前问过的问题,但我无法弄清楚如何实现它.我很难理解如何找到和使用MTV,所以如果有人真的可以帮助我理解,也许给我一些例子,这样我就可以在实现中理解它而不仅仅是理论,它会很多感谢,对于给您带来的任何不便,我们深表歉意.我的代码确实成功检测到了碰撞,现在它在下面:

//NOTE: This is within the HitPolygon class, so "this" is referencing itself as a polygon
public Projection project(Vector2D axis){

    float min = axis.dot(this.getVertices().get(0));
    float max = min;
    Vector2D vecMax  = new Vector2D(0, 0), vecMin = new Vector2D(0, 0);

    for(int i = 1; i < this.getVertices().size(); i++){
        float p = axis.dot(this.getVertices().get(i));
        if(p < min){
            min = p;
            vecMin = this.getVertices().get(i);
        }
        if(p > max){
            max = p;
            vecMax = this.getVertices().get(i);
        }
    }

    Projection result = new Projection(min, max, vecMin, vecMax, …