8
\$\begingroup\$

This is exercise 3.2.1. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:

Consider the following data-type implementation for axis-aligned rectangles, which represents each rectangle with the coordinates of its center point and its width and height:

public class Rectangle
{
  private final double x, y;
  private final double width;
  private final double height;

  public Rectangle(double x0, double y0, double w, double h)
  {
      x = x0; y = y0; width = w; height = h;
  }
  public double area()
  {
      return width*height;
  }
  public double perimeter()
  {
      /* Compute perimeter. */
  }
  public boolean intersects(Rectangle b)
  {
      /* Does this rectangle intersects b? */
  }
  public boolean contains(Rectangle b)
  {
      /* Is b inside this rectangle? */
  }
  public void draw(Rectangle b)
  {
      /* Draw rectangle on standard drawing. */
  }
}

Fill in the code for perimeter(), intersects(), and contains(). Note : Consider two rectangles to intersect if they share one or more common points (improper intersections). For example, a.intersects(a) and a.contains(a) are both true.

This is exercise 3.2.2. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:

Write a test client for Rectangle that takes three command-line arguments n, min, and max; generates n random rectangles whose width and height are uniformly distributed between min and max in the unit square; draws them on standard drawing; and prints their average area and perimeter to standard output.

This is exercise 3.2.3. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:

Add code to your test client from the previous exercise code to compute the average number of rectangles that intersect a given rectangle.

Here is my program for all the above 3 exercises combined:

public class Rectangle
{
    private final double x, y;
    private final double width;
    private final double height;

    public Rectangle(double x0, double y0, double w, double h)
    {
        x = x0; y = y0; width = w; height = h;
    }   
    public double xCoordinate()
    {
        return x;
    }
    public double yCoordinate()
    {
        return y;
    }
    public double widthOf()
    {
        return width;
    }
    public double heightOf()
    {
        return height;
    }
    public double left()
    {
        return x - width/2;
    }
    public double right()
    {
        return x + width/2;
    }
    public double bottom()
    {
        return y - height/2;
    }
    public double top()
    {
        return y + height/2;
    }
    public double area()
    {
        return width*height;
    }
    public double perimeter()
    {
        return 2*width+2*height;
    }
    public boolean contains(Rectangle b)
    {
        if ((x - width/2)  <= (b.left())   &&
            (x + width/2)  >= (b.right())  &&
            (y - height/2) <= (b.bottom()) &&
            (y + height/2) >= (b.top()))
        {
            return true;
        }
        else return false;
    }
    public boolean intersects(Rectangle b)
    {
        boolean leftOfFirstBetweenLeftAndRightOfSecond   = (x - width/2)  > b.left()       && (x - width/2)  < b.right();
        boolean rightOfFirstBetweenLeftAndRightOfSecond  = (x + width/2)  > b.left()       && (x + width/2)  < b.right();
        boolean bottomOfFirstBetweenBottomAndTopOfSecond = (y - height/2) > b.bottom()     && (y - height/2) < b.top();
        boolean topOfFirstBetweenBottomAndTopOfSecond    = (y + height/2) > b.bottom()     && (y + height/2) < b.top();
        boolean leftOfSecondBetweenLeftAndRightOfFirst   = b.left()       > (x - width/2)  && b.left()       < (x + width/2);
        boolean rightOfSecondBetweenLeftAndRightOfFirst  = b.right()      > (x - width/2)  && b.right()      < (x + width/2);
        boolean bottomOfSecondBetweenBottomAndTopOfFirst = b.bottom()     > (y - height/2) && b.bottom()     < (y + height/2);
        boolean topOfSecondBetweenBottomAndTopOfFirst    = b.top()        > (y - height/2) && b.top()        < (y + height/2);
        if      ((leftOfFirstBetweenLeftAndRightOfSecond  && bottomOfFirstBetweenBottomAndTopOfSecond) || (leftOfSecondBetweenLeftAndRightOfFirst  && bottomOfSecondBetweenBottomAndTopOfFirst)) return true;
        else if ((rightOfFirstBetweenLeftAndRightOfSecond && bottomOfFirstBetweenBottomAndTopOfSecond) || (rightOfSecondBetweenLeftAndRightOfFirst && bottomOfSecondBetweenBottomAndTopOfFirst)) return true;
        else if ((leftOfFirstBetweenLeftAndRightOfSecond  && topOfFirstBetweenBottomAndTopOfSecond)    || (leftOfSecondBetweenLeftAndRightOfFirst  && topOfSecondBetweenBottomAndTopOfFirst))    return true;
        else if ((rightOfFirstBetweenLeftAndRightOfSecond && topOfFirstBetweenBottomAndTopOfSecond)    || (rightOfSecondBetweenLeftAndRightOfFirst && topOfSecondBetweenBottomAndTopOfFirst))    return true;
        else if (x == b.xCoordinate() && y == b.yCoordinate() && width == b.widthOf() && height == b.heightOf())                                                                                 return true;
        else                                                                                                                                                                                     return false;
    }
    public void draw()
    {
        StdDraw.rectangle(x, y, width/2, height/2);
    }
    public static double randomize(double a, double b)
    {
        return a + Math.random()*(b-a);
    }
    public static void main(String[] args)
    {
        int n = Integer.parseInt(args[0]);
        double min = Double.parseDouble(args[1]);
        double max = Double.parseDouble(args[2]);
        Rectangle[] rectangles = new Rectangle[n];
        for (int i = 0; i < n; i++)
        {
            rectangles[i] = new Rectangle(randomize(0.2,0.8),
                                          randomize(0.2,0.8),
                                          randomize(min,max),
                                          randomize(min,max));
        }
        for (int i = 0; i < n; i++)
        {
            rectangles[i].draw();
        }
        double averageArea = 0;
        double averagePerimeter = 0;
        for (int i = 0; i < n; i++)
        {
            averageArea += rectangles[i].area();
            averagePerimeter += rectangles[i].perimeter();
        }
        System.out.println("Average area = " + averageArea);
        System.out.println("Average perimeter = " + averagePerimeter);
        int[] intersections = new int[n];
        for (int i = 0; i < n; i++)
        {
            intersections[i]--;
            for (int j = 0; j < n; j++)
            {
                if (rectangles[i].intersects(rectangles[j]))
                {
                    intersections[i]++;
                }
            }
        }
        int sumOfIntersections = 0;
        for (int i = 0; i < n; i++)
        {
            sumOfIntersections += intersections[i];
        }
        System.out.println("Average intersections = " + ((int) sumOfIntersections/n));
    }
}

StdDraw is a simple API written by the authors of the book. I checked my program and it works. Here is one instance of it:

Input: 200 0.01 0.1

Output:

Average area = 0.6067956188701565

Average perimeter = 44.41595092011365

Average intersections = 5

enter image description here

Is there any way that I can improve my program (especially the implementation of intersects method)?

Thanks for your attention.

One can find the follow-up to this post in here.

\$\endgroup\$
  • 1
    \$\begingroup\$ For the intersects() method, I find it easier to enumerate the cases where the rectangles do not intersect: if the second rectangle lies completely left of the first one (second right edge less than first left edge), it's a miss. Same for "completely above", "right", or "below" the first rectangle. Otherwise they intersect. \$\endgroup\$ – Ralf Kleberhoff Sep 15 at 15:09
8
\$\begingroup\$
  private final double x, y;
  private final double width;
  private final double height;

  public Rectangle(double x0, double y0, double w, double h)
  {
      x = x0; y = y0; width = w; height = h;
  }

That really should be something like this, considering readability and the default Java patterns:

  private final double x;
  private final double y;
  private final double width;
  private final double height;

  public Rectangle(double x, double y, double width, double height) {
      this.x = x;
      this.y = y;
      this.width = width;
      this.height = height;
  }

Having said that, neither is b a good variable name. I understand the constraints of printed media, but the example code wasn't already that good.


Now, regarding your implementation. Storing the values for left/right/etc. might be a nice solution. Also, they should most likely be prefixed with get, like getLeft.

The contains function could be rewritten to utilize that:

    public boolean contains(Rectangle otherRectangle) {
        return getLeft() <= otherRectangle.getLeft()
                && getRight()  >= otherRectangle.getRight()
                && getBottom() <= otherRectangle.getBottom()
                && getTop() >= otherRectangle.getTop();
    }

intersects is quite a mess, I have to say, it can be made much more readable by using a helper function.

private boolean contains(double x, double y) {
    return x >= getLeft() && x <= getRight()
            && y >= getBottom() && y <= getTop();
}

private boolean overlapsHorizontalLine(double xStart, double xEnd, double y) {
    return xStart <= getLeft()
            && xEnd >= getRight()
            && y >= getBottom()
            && y <= getTop();
}

private boolean overlapsVerticalLine(double yStart, double yEnd, double x) {
    return yStart <= getBottom()
            && yEnd >= getTop()
            && x >= getLeft()
            && x <= getRight();
}

public boolean intersects(Rectangle otherRectangle) {
    return contains(otherRectangle.getLeft(), otherRectangle.getTop())
            || contains(otherRectangle.getLeft(), otherRectangle.getBottom())
            || contains(otherRectangle.getRight(), otherRectangle.getTop())
            || contains(otherRectangle.getRight(), otherRectangle.getBottom())
            || overlapsHorizontalLine(otherRectangle.getLeft(), otherRectangle.getRight(), otherRectangle.getBottom())
            || overlapsHorizontalLine(otherRectangle.getLeft(), otherRectangle.getRight(), otherRectangle.getTop())
            || overlapsVerticalLine(otherRectangle.getBottom(), otherRectangle.getTop(), otherRectangle.getLeft())
            || overlapsVerticalLine(otherRectangle.getBottom(), otherRectangle.getTop(), otherRectangle.getRight());
}


Your Rectangle class is doing too much, namely, everything. Ideally Rectangle would only contain the data for a single rectangle, and a Main class would contain your main, randomize and do the drawing.


Instead of using an array, you could use a List:

List<Rectangle> rectangles = new ArrayList<>();

for (int counter = 0; counter < numberOfRectangles; counter++) {
    rectangles.add(new Rectangle(...));
}

for (Rectangle rectangle : rectangles) {
    draw(rectangle);
}

You could split your main also in different functions, like this:

public static final main(String[] args) {
    List<Rectangle> rectangles = createRectangles(args);
    drawRectangles(rectangles);

    double averageArea = calculateAverageArea(rectangles);
    System.out.println("Average area = " + Double.toString(averageArea));
    
    // And so on...
}

If you feel extra fancy, you can create a Configuration class which, parses the given arguments into a POJO, which is then used/passed around.


Your calculation of the intersections could be simplified by directly summing up the intersections.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Your implementation of intersects assumes that if rectangles intersect then at least one corner is inside the other rectangle, this isn't always true. (imagine a + sign made of 2 rectangles) \$\endgroup\$ – potato Sep 16 at 8:46
  • \$\begingroup\$ You're right, missed that. \$\endgroup\$ – Bobby Sep 16 at 15:50
  • \$\begingroup\$ @potato I've added it, I'm sure there is a better way, but I can't concentrate right now. Feel free to edit it. \$\endgroup\$ – Bobby Sep 16 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.