如何检测旋转的矩形何时相互碰撞 [英] How to detect when rotated rectangles are colliding each other

问题描述

在多次看到这个问题并回答了一个旧的（不可用的）代码后，我决定重做所有内容并将其发布。

矩形的定义如下：

• center ： x 和 y 表示自己的位置（请记住0; 0是最左上角，所以Y向下）


• 大小： x 和 y 他的大小


• 角度旋转（以度为单位，0度跟随OX轴并顺时针旋转）

目标是要知道2个矩形是否碰撞。

解决方案

将使用Javascript进行演示（并提供代码），但是我可以按照该过程对每种语言进行操作。

链接

• 
  
  

  处理

  
  
  

  1-查找矩形轴

  
  
  

  首先为轴0; 0（矩形的中心）到X（OX）和Y（OY）创建2个向量，然后旋转它们两个以便与矩形轴对齐。

  
  
  
  
  
  

  2-使用垂直轴获取角点
  
  

  首先要扩展轴（单位为1px），以便获得宽度（对于X）和高度（对于Y）的一半，以便添加

    const getCorners =（rect）=>。 {
   const axis = getAxis（rect）; 
   const RX = axis [0] .direction.Multiply（rect.w / 2）; 
   const RY = axis [1] .direction.Multiply（rect.h / 2）; 
   return [
   rect.center.Add（RX）.Add（RY），
   rect.center.Add（RX）.Add（RY.Multiply（-1）），
   rect.center.Add（RX.Multiply（-1））。Add（RY.Multiply（-1）），
   rect.center.Add（RX.Multiply（-1））。Add（RY ），
  ] 
  } 
    

  针对Vector使用以下两种新闻方法：

    // Add（5）
   // Add（Vector）
   // Add（{x，y}）
   Add（factor）{
   const f = typeof factor ==='object'
  ？ {x：0，y：0，... factor} 
  ：{x：factor，y：factor} 
  返回new Vector（{
  x：this.x + fx，
  y：this.y + fy，
  }）
  } 
   // Multiply（5）
   // Multiply（Vector）
   // Multiply（{x ，y}）
  乘数（factor）{
   const f = typeof factor ==='object'
  ？ {x：0，y：0，... factor} 
  ：{x：factor，y：factor} 
  返回new Vector（{
  x：this.x * fx，
  y：this.y * fy，
  }）
  } 
    

  Step结果

  
  
  
  
  
  

  3-取得弯角投影

  
  
  

  对于矩形的每个角，获取另一个矩形的两个轴上的投影坐标。

  
  
  

  只需将此函数添加到Vector类中即可：

    Project（line）{
   let dotvalue = line.direction.x *（this.x-line.origin.x）
   + line.direction.y *（this.y-line.origin.y）; 
  返回新向量（{
  x：line.origin.x + line.direction.x *点值，
  y：line.origin.y + line.direction.y *点值，
  }）
  } 
    

  （特别感谢Mbo

  
  
  

  4-选择投影的外部角

  
  
  

  为了对所有投影点进行排序（沿矩形轴），并取最小和最大投影点，我们可以：

  
  
  
  
  
  • 创建一个矢量来表示：矩形中心到投影角
  
  
  • 使用矢量幅值功能获取距离。
  
  
  
  
  

    getitude（）{ 
  返回Math.sqrt（this.x * this.x + this.y * this.y）; 
  } 
    

  
  
  

  
  
  • 使用
    
    
    

    5-最终：所有投影都达到矩形吗？

    
    
    

    通过沿轴的简单一维测试，我们可以知道它们是否达到：

      const isProjectionHit =（minSignedDistance< 0&& maxSignedDistance> 0 
     || Math.abs（minSignedDistance）< rectHalfSize 
     || Math.abs（maxSignedDistance）< rectHalfSize）; 
      

    
    
    

    完成

    
    
    

    测试所有4个投影将得出最终结果。 =] !!

    
    
    
    
    
    

    希望此答案会有所帮助尽可能多的人。任何意见表示赞赏。

    
    

    After saw this question many times and replied with an old (an not usable) code I decide to redo everything and post about it.

    Rectangles are defined by:

    • center : x and y for his position (remember that 0;0 is TOP Left, so Y go down)
    • size: x and y for his size
    • angle for his rotation (in deg, 0 deg is following axis OX and turn clockwise)

    The goal is to know if 2 rectangles are colliding or not.

    解决方案

    Will use Javascript in order to demo this (and also provide code) but I can be done on every language following the process.

    Links

    • Final Demo on Codepen
    • GitHub repository

    Concept

    In order to achieve this we'll use corners projections on the other rectangle 2 axis (X and Y). The 2 rectangles are only colliding when the 4 projections on one rectangles hit the others:

    • Rect Blue corners on Rect Orange X axis
    • Rect Blue corners on Rect Orange Y axis
    • Rect Orange corners on Rect Blue X axis
    • Rect Orange corners on Rect Blue Y axis

    Process

    1- Find the rects axis

    Start by creating 2 vectors for axis 0;0 (center of rect) to X (OX) and Y (OY) then rotate both of them in order to get aligned to rectangles axis.

    Wikipedia about rotate a 2D vector

    const getAxis = (rect) => {
      const OX = new Vector({x:1, y:0});
      const OY = new Vector({x:0, y:1});
      // Do not forget to transform degree to radian
      const RX = OX.Rotate(rect.angle * Math.PI / 180);
      const RY = OY.Rotate(rect.angle * Math.PI / 180);
    
      return [
         new Line({...rect.center, dx: RX.x, dy: RX.y}),
         new Line({...rect.center, dx: RY.x, dy: RY.y}),
      ];
    }
    

    Where Vector is a simple x,y object

    class Vector {
      constructor({x=0,y=0}={}) {
        this.x = x;
        this.y = y;
      }
      Rotate(theta) {
        return new Vector({
          x: this.x * Math.cos(theta) - this.y * Math.sin(theta),
          y: this.x * Math.sin(theta) + this.y * Math.cos(theta),
        });
      }
    }
    

    And Line represent a slop using 2 vectors:

    • origin: Vector for Start position
    • direction: Vector for unit direction

    class Line {
      constructor({x=0,y=0, dx=0, dy=0}) {
        this.origin = new Vector({x,y});
        this.direction = new Vector({x:dx,y:dy});
      }
    }
    

    Step Result

    2- Use Rect Axis to get corners

    First want extend our axis (we are 1px unit size) in order to get the half of width (for X) and height (for Y) in order to be able by adding when (and inverse) to get all corners.

    const getCorners = (rect) => {
      const axis = getAxis(rect);
      const RX = axis[0].direction.Multiply(rect.w/2);
      const RY = axis[1].direction.Multiply(rect.h/2);
      return [
        rect.center.Add(RX).Add(RY),
        rect.center.Add(RX).Add(RY.Multiply(-1)),
        rect.center.Add(RX.Multiply(-1)).Add(RY.Multiply(-1)),
        rect.center.Add(RX.Multiply(-1)).Add(RY),
      ]
    }
    

    Using this 2 news methods for Vector:

      // Add(5)
      // Add(Vector)
      // Add({x, y})
      Add(factor) {
        const f = typeof factor === 'object'
          ? { x:0, y:0, ...factor}
          : {x:factor, y:factor}
        return new Vector({
          x: this.x + f.x,
          y: this.y + f.y,
        })
      }
      // Multiply(5)
      // Multiply(Vector)
      // Multiply({x, y})
      Multiply(factor) {
        const f = typeof factor === 'object'
          ? { x:0, y:0, ...factor}
          : {x:factor, y:factor}
        return new Vector({
          x: this.x * f.x,
          y: this.y * f.y,
        })
      }
    

    Step Result

    3- Get corners projections

    For every corners of a rectangle, get the projection coord on both axis of the other rectangle.

    Simply by adding this function to Vector class:

      Project(line) {
        let dotvalue = line.direction.x * (this.x - line.origin.x)
          + line.direction.y * (this.y - line.origin.y);
        return new Vector({
          x: line.origin.x + line.direction.x * dotvalue,
          y: line.origin.y + line.direction.y * dotvalue,
        })
      }
    

    (Special thank to Mbo for the solution to get projection.)

    Step Result

    4- Select externals corners on projections

    In order to sort (along the rect axis) all the projected point and take the min and max projected points we can:

    • Create a vector to represent: Rect Center to Projected corner
    • Get the distance using the Vector Magnitude function.

      get magnitude() {
        return Math.sqrt(this.x * this.x + this.y * this.y);
      }
    

    • Use the dot product to know if the vector is facing the same direction of axis of inverse (where signed distance" is negative)

    getSignedDistance = (rect, line, corner) => {
      const projected = corner.Project(line);
      const CP = projected.Minus(rect.center);
      // Sign: Same directon of axis : true.
      const sign = (CP.x * line.direction.x) + (CP.y * line.direction.y) > 0;
      const signedDistance = CP.magnitude * (sign ? 1 : -1);
    }
    

    Then using a simple loop and test of min/max we can find the 2 externals corners. The segment between them is the projection of a Rect on the other one axis.

    Step result

    5- Final: Do all projections hit rect ?

    Using simple 1D test along the axis we can know if they hit or not:

    const isProjectionHit = (minSignedDistance < 0 && maxSignedDistance > 0
            || Math.abs(minSignedDistance) < rectHalfSize
            || Math.abs(maxSignedDistance) < rectHalfSize);
    

    Done

    Testing all 4 projections will give you the final result. =] !!

    Hope this answer will help as many people as possible. Any comments are appreciated.

    这篇关于如何检测旋转的矩形何时相互碰撞的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！