CODEWITHSUNDEEP
javaalgorithmgraphicsgeometry
Simon Morgan
Simon Morgan

Reputation: 2248

Algorithms by Sedgewick & Wayne, Exercise 1.2.3

Algorithms by Sedgewick & Wayne, Exercise 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 exposes the following API:

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

Is it possible to check whether one Interval2D is contained in another using only these methods?

Upvotes: 1

Views: 888

Answers (4)

tchappy ha
tchappy ha

Reputation: 197

My solution is here: 

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

}

Upvotes: 0

Vitalii Vitrenko
Vitalii Vitrenko

Reputation: 10395

You might use methods left() and right() in Interval1D, in advance saving them during the creation of 2D intervals.

I did it like that

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

Upvotes: 1

mvw
mvw

Reputation: 5105

A) To understand the situation:

Definition of the 2D intervals A and B in terms of 1D intervals:

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

Then

 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].

Using 

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

This is similar to the implementation of the intersect methods in Interval2D (http://algs4.cs.princeton.edu/12oop/Interval2D.java.html) and Intervall1D (http://algs4.cs.princeton.edu/12oop/Interval1D.java.html) only that they test for the logical inverse of the conditions.

B) Now to your methods:

The contains(Point2D) should allow to do the test, if you check the lower left (x1a, y1a) and upper right (x2a, y2a) points:

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

The ugly thing is that while Interval1D has getters to access the private left and right coordinates, Interval2D has none to access it's private x and y (one dimensional) intervals. You could parse them from its toString() output, but that is ugly and too much work. Creating some 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;
  }
}

and using it is just ugly.

Upvotes: 1

Thorn
Thorn

Reputation: 4057

It makes much more sense to check for intersection using the upper and lower bounds of the interval. Theoretically it should be possible to use only the methods listed, but doing so efficiently may be tricky. If Interval A contains Interval b, then every point in B is also in A. We could therefore iterate over every point (if the coordinate system is based on int and not double) and check this condition. If we are faced with doubles, then a modified technique could be used to generate a contains method that will function correctly with high probability.

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

The trick is to find the right subset. But I think an algorithm guaranteed to always be correct is MUCH harder. Consider a one dimensional case. If interval A = (0.5,Math.PI/6) and B = [0.4,Math.PI/6]. It's obvious that B contains A but none of those methods can help us see that they both have the same right endpoint but B includes that point while A does not. How can those methods help us differential that example from this one:

A = (0.5,Math.PI/6] and B = [0.4,Math.PI/6) Now there is exactly one point that needs to be chosen to show that B does not contain A: Math.PI/6 This leads me to feel that such an algorithm is next to impossible.

Upvotes: 0

Related Questions