更快速地检查相交的矩形？ [英] Faster way to check intersected rectangles?

问题描述

除了我的Rect-class：

Except from my Rect-class:

public class Rect {
  public int x;
  public int y;
  public int w;
  public int h;

  public Rect(int x, int y, int w, int h) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
  }

  ...
}

我有一个方法来检查两个Rects是否相交（没有双关语）：

I have a method to check if two Rects intersects (no pun intended):

public boolean intersect(Rect r) {
  return (((r.x >= this.x) && (r.x < (this.x + this.w))) || ((this.x >= r.x) && (this.x < (r.x + r.w)))) &&
  (((r.y >= this.y) && (r.y < (this.y + this.h))) || ((this.y >= r.y) && (this.y < (r.y + r.h))));
}

测试用例：

r1 = (x, y, w, h) = (0, 0, 15, 20)  center: (x, y) = (7, 10)
r2 = (x, y, w, h) = (10, 11, 42, 15)  center: (x, y) = (31, 18)
r1 Intersect r2: true

该课程正常。

我想知道的是，如果有的话另一种 - 也许更快 - 检查矩形是否相交的方法。我能以某种方式对其进行优化吗？

What I'm wondering is if there is another - perhaps faster - way to check if the rectangles are intersecting. Can I optimize it in some way?

推荐答案

我倾向于将矩形存储为min x，min y，max x和max y 。然后重叠发生在

I tend to store rectangles as min x, min y, max x and max y. Then overlap occurs when

r1.maxX > r2.minX &&
r1.minX < r2.maxX &&
r1.maxY > r2.minY &&
r1.minY < r2.maxY

如果它们重叠，则交叉点由

And if they overlap, the intersection is defined by

r3.minX = max(r1.minX, r2.minX);
r3.minY = max(r1.minY, r2.minY);
r3.maxX = min(r1.maxX, r2.maxX);
r3.maxY = min(r1.maxY, r2.maxY);

根据您是否认为它们具有相同重叠，应该注意一些边界。我使用严格的不等式意味着重叠的边界不算作重叠。鉴于您使用的是整数（因此边界的宽度为1），我将假设您确实希望将重叠边界视为重叠。我会这样做：

Some care should be taken depending on whether or not you consider them to be overlapping if they have the same boundary. I've used strict inequalities meaning that overlapping boundaries do not count as an overlap. Given that you are using integers (and thus the boundaries have a width of 1) I will assume that you do want to consider overlapping boundaries as an overlap. I would do something like:

public class Rect {
    public int minX;
    public int minY;
    public int maxX;
    public int maxY;

    public Rect() {}

    public Rect(int x, int y, int w, int h) {
        this.minX = x;
        this.minY = y;
        this.maxX = x + w -1;
        this.maxY = y + h -1;
    }

    public boolean Intersect(Rect r) {
        return this.maxX >= r.minX &&
               this.minX <= r.maxX &&
               this.maxY >= r.minY &&
               this.minY <= r.maxY;              
    }

    public Rect GetIntersection(Rect r) {
        Rect i = new Rect();
        if (this.Intersect(r)) {
            i.minX = Math.max(this.minX, r.minX);
            i.minY = Math.max(this.minY, r.minY);
            i.maxX = Math.min(this.maxX, r.maxX);
            i.maxY = Math.min(this.maxY, r.maxY);
        }
        return i;       
   }

   public int GetWidth() {
       return this.maxX - this.minX + 1;   
   }

    public int GetHeight() {
        return this.maxY - this.minY + 1;   
    }

    public void SetPosition(int x, int y) {
        int w = this.GetWidth();
        int h= this.GetHeight();
        this.minX = x;
        this.minY = y;
        this.maxX = x + w -1;
        this.maxY = y + h -1;
    }
}

这篇关于更快速地检查相交的矩形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！