algorithm - 界交点

Question

给定一个像这样的 Bounds 结构:

struct Bounds {
  public double xMin;
  public double xMax;
  public double yMin;
  public double yMax;
}

我试图找出两个 Bounds A 和 B 是如何相交的。可能的结果是:

• A和B根本不相交
• A 和 B 相等
• A完全包含B
• B完全包含A
• A 和 B 相交

我第一次天真的尝试是测试 A 在 B 中有多少点以及 B 在 A 中有多少点，但我需要这个测试尽可能快并且可能有更好的方法去做。

非常感谢!

Answer 1

首先在 2D 1D 中尝试。应该清楚如何针对这五种可能的结果测试两个 [x_min, x_max] 对象。然后对 [y_min, y_max] 做同样的事情。然后合并两个结果:

• (无交集)_x +(任意)_y =(无交集)
• (等于)_x +(某物)_y =(某物)
• (A包含B)_x + (A包含B)_y = (A包含B)
• (A包含B)_x + (A和B相交)_y = (A和B相交)
• (A包含B)_x + (B包含A)_y = (A和B相交)

(我认为这涵盖了它。)