java - Sedgewick & Wayne 的算法，练习 1.2.3

Question

Sedgewick & Wayne 的算法，练习 1.2.3:

Write an Interval2D client that takes command-line arguments N, min, and max and generates N random 2D intervals whose width and height are uniformly distributed between min and max in the unit square. Draw them on StdDraw and print the number of pairs of intervals that intersect and the number of intervals that are contained in one another.

Interval2D 公开了以下 API:

Interval2D(Interval1D x, Interval1D y)
boolean intersects(Interval2D)
boolean contains(Point2D)
double area()
void draw()

是否可以仅使用这些方法检查一个 Interval2D 是否包含在另一个中？

Answer 1

A) 了解情况:

根据一维区间定义二维区间 A 和 B:

 A = Ixa x Iya = [x1a, x2a] x [y1a, y2a]
 B = Ixb x Iyb = [x1b, x2b] x [y1b, y2b]

然后

 A is contained in B, iff 
 Ixa = [x1a, x2a] is contained in Ixb [x1b, x2b] and
 Iya = [y1a, y2a] is contained in Iyb = [y1b, y2b].

使用

 I1 = [a, b] is contained in I2 = [c, d] iff c <= a and b <= d.

这类似于 Interval2D ( http://algs4.cs.princeton.edu/12oop/Interval2D.java.html ) 和 Intervall1D ( http://algs4.cs.princeton.edu/12oop/Interval1D.java.html ) 中相交方法的实现，只是它们测试条件的逻辑逆。

B) 现在你的方法:

contains(Point2D) 应该允许做测试，如果你检查左下角 (x1a, y1a) 和右上角 (x2a, y2a) 点:

 A is contained in B, iff B contains (x1a, y1a) and B contains (x2a, y2a).

丑陋的是，虽然 Interval1D 有 getter 来访问私有(private)的左右坐标，但 Interval2D 没有访问它的私有(private) x 和 y(一维)间隔。您可以从其 toString() 输出中解析它们，但这很丑陋并且工作量太大。创建一些父类(super class)

public class Rect {
  public Interval1D x;
  public Interval1D y;
  public Interval2D r;
  Rect(Interval1D px, Interval1D py) {
    x = px;
    y = py;
    r = new Interval2D(px, py);
  }
  public boolean contains(Rect that) {
    if (!this.r.contains(new Point2D(that.x.left(), that.y.left()))) return false;
    if (!this.r.contains(new Point2D(that.x.right(), that.y.right()))) return false;
    return true;
  }
}

而且使用起来很丑陋。