Sedgewick & Wayne 的算法,练习 1.2.3:
Write an
Interval2D
client that takes command-line argumentsN
,min
, andmax
and generatesN
random 2D intervals whose width and height are uniformly distributed betweenmin
andmax
in the unit square. Draw them onStdDraw
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
是否包含在另一个中?
最佳答案
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;
}
}
而且使用起来很丑陋。
关于java - Sedgewick & Wayne 的算法,练习 1.2.3,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17639548/