1

Sedgewick & Wayne 的算法，练习 1.2.3：

编写一个Interval2D客户端，它接受命令行参数N、 min和 ，max并生成随机二维间隔，其宽度和N高度均匀分布在单位正方形之间。绘制它们并打印相交的间隔对的数量以及彼此包含的间隔的数量。minmaxStdDraw

Interval2D 公开了以下 API：

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

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

4

4 回答 4

1

A) 了解情况：

根据 1D 区间定义 2D 区间 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/中的 intersect 方法的实现。 Interval1D.java.html ) 只是他们测试条件的逻辑逆。

B）现在你的方法：

如果您检查左下角 (x1a, y1a) 和右上角 (x2a, y2a) 点， contains(Point2D) 应该允许进行测试：

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

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

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;
  }
}

并且使用它只是丑陋的。

于 2013-07-14T13:00:51.500 回答
1

您可以使用 Interval1D 中的 left() 和 right() 方法，在创建 2D 间隔期间提前保存它们。

我是这样做的

    int intersect = 0;
    int contain = 0;    
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (arr2D[i].intersects(arr2D[j])){
                intersect++;
            }
            if ( (arrX[i].left() <= arrX[j].left() && arrX[i].right() >= arrX[j].right())
                && (arrY[i].left() <= arrY[j].left() && arrY[i].right() >= arrY[j].right())) {
                contain++;
            }   
        }
    }
于 2015-07-03T13:09:02.723 回答
0

使用区间的上限和下限检查交叉点更有意义。从理论上讲，应该可以只使用列出的方法，但有效地这样做可能会很棘手。如果区间 A 包含区间 b，则 B 中的每个点也在 A 中。因此我们可以遍历每个点（如果坐标系基于 int 而不是 double）并检查此条件。如果我们面临双打，那么可以使用修改后的技术来生成一个包含方法，该方法将以高概率正确运行。

//Iterate over some subset of points.
if(b.contains(pointP) && !a.contains(pointP))
   return false;

诀窍是找到正确的子集。但我认为保证始终正确的算法要困难得多。考虑一维情况。如果区间A = (0.5,Math.PI/6)和B = [0.4,Math.PI/6]。很明显，B 包含 A，但这些方法都不能帮助我们看到它们都具有相同的正确端点，但 B包含该点而 A 没有。这些方法如何帮助我们将该示例与此示例区分开来：

A = (0.5,Math.PI/6]现在B = [0.4,Math.PI/6) 需要选择一个点来表明 B 不包含 A：Math.PI/6 这让我觉得这样的算法几乎是不可能的。

于 2013-07-14T13:13:02.333 回答
0

我的解决方案在这里： 

package exercise.chapter2.section2;

import edu.princeton.cs.algs4.Interval1D;
import edu.princeton.cs.algs4.Interval2D;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

public class Ex1_2_03 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int N = Integer.parseInt(args[0]);
        double min = Double.parseDouble(args[1]);
        double max = Double.parseDouble(args[2]);
        MyInterval2D[] boxes = new MyInterval2D[N];
        for (int i = 0; i < N; i++) {
            double width = StdRandom.uniform(min, max);
            double height = StdRandom.uniform(min, max);

            double xlo = StdRandom.uniform(width, 1.0 - width);
            double xhi = xlo + width;
            double ylo = StdRandom.uniform(height, 1.0 - height);
            double yhi = ylo + height;

            boxes[i] = new MyInterval2D(new Interval1D(xlo, xhi), new Interval1D(ylo, yhi));
            boxes[i].draw();            
        }

        int cintersects = 0;
        int ccontained = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (boxes[i].intersects(boxes[j])) {
                    cintersects++;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            boxes[i].draw();
            for (int j = 0; j < N; j++) {
                if (i != j && boxes[j].contains(boxes[i])) {
                    ccontained++;
                    break;
                }
            }
        }
        StdOut.println(cintersects);
        StdOut.println(ccontained);
    }

}

class MyInterval2D extends Interval2D {
    private Interval1D xint;
    private Interval1D yint;

    public MyInterval2D(Interval1D xint, Interval1D yint) {
        super(xint, yint);
        this.xint = xint;
        this.yint = yint;
    }

    public boolean contains(MyInterval2D box) {
        if (xint.contains(box.xint.min()) && xint.contains(box.xint.max()) && yint.contains(box.yint.min()) && yint.contains(box.yint.max())) {
            return true;
        }
        return false;
    }

}
于 2020-06-02T10:38:02.303 回答