# I think I need an algorith

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• September 1st, 2010, 15:49
javapenguin
I think I need an algorith
I'm trying to get it to compare rectangles in an array.

I want it to compare Rectangle 0 and Rectangle 1 and Rectangle 0 and Rectangle 2, etc.

The number of rectangles is being specified by the user.

I want it to check like for 6 rectangles,

1 and 2, 1 and 3, 1 and 4, 1 and 5, 1 and 6
2 and 3, 2 and 4, 2 and 5, 2 and 6
3 and 4, 3 and 5, 3 and 6
4 and 5, 4 and 6
5 and 6

Where 1 is the first rectangle.

Note: Rectangle 1 corresponds to Rectangle[0] where each value in Rectangle[0] through Rectangle[n] is a Rectangle(my defined Rectangle, not the already written Rectangle class.)

I'd like to compare each Rectangle with each other to see if it overlaps but I don't want to do check the same thing, like 1 and 1, 2 and 3 and also checking 3 and 2.
• September 1st, 2010, 16:02
aussiemcgr
Re: I think I need an algorith
Ok, so if you are checking to see if they are overlapping. You want to see if any given point in each edge of Rectangle A is Less than the X value and the Y value of the top-left edge of Rectangle B and greater than the X value and the Y value of the bottom-right edge of Rectangle B.
• September 1st, 2010, 16:30
copeg
Re: I think I need an algorith
First, write a method which compares the rectangles. In the java.awt.Rectangle class, there is a method intersects which returns a boolean, perhaps implement something like this (any reason why you are not using or extending that class?). You then need a double loop to compare the rectangles...something like this

Code java:

```int size = 10; Rectangle[] rects = new Rectangle[size]; //instantiate the rectangles for ( int i = 0; i < size; i++ ){ for ( int j = i+1; j < size; j++ ){ if ( rects[i].intersects(rects[j]) ){ //do something } } }```
• September 1st, 2010, 16:55
Brt93yoda
Re: I think I need an algorith
intersects() can also be used for collision detection, right?
• September 1st, 2010, 17:15
Norm
Re: I think I need an algorith
If you're not sure, write a small program, define two rectangles, and execute the intersects() method to see.
• September 1st, 2010, 17:17
Brt93yoda
Re: I think I need an algorith
ok, I will try it
• September 1st, 2010, 17:21
helloworld922
Re: I think I need an algorith
Kind of. You need to figure out whether intersects will return true if the two objects share an edge, or even just a vertex. If it does, then that would be take care of collision checking between two rectangles, and you'd just need to check for collision between all rectangles or use an accelerator structure to reduce the number of potential collisions you need to check.
• September 1st, 2010, 17:22
Brt93yoda
Re: I think I need an algorith
Trying not to be annoying, but what is an "accelerator structure?"
• September 1st, 2010, 17:27
helloworld922
Re: I think I need an algorith
It's a way of dividing up your rectangles/objects in a way that allows you to quickly decide if it's even possible that any two objects/rectangles will be in collision. It's kind of a general term, but there are many accelerator structures for collision detection and they operate in different ways.

A simple one is using a grid:

Divide your data into small grids, then for every rectangle that lies in that region, add it to a list of objects for that grid (note: each rectangle can belong to several grid boxes).

Then, when you're checking for collisions, start by figuring out which grid boxes the rectangle you're interested in lies in. You will only need to check collisions against any rectangle which lies in these grids because your rectangle doesn't lie in any other grid.
• September 1st, 2010, 19:51
javapenguin
Re: I think I need an algorith
Here's what they want me to do. I'm not sure how to do a switch structure.

^:)^^:)^^:)^^:)^^:)^~X(~X(~X(~X(~X(~X(~X(~X(~X(~X(
• September 1st, 2010, 20:02
Norm
Re: I think I need an algorith
If your too lazy to write a description of your problem and post it here, I way to lazy to read it out of an attached file.
• September 1st, 2010, 20:17
javapenguin
Re: I think I need an algorith
Assignment 1: Rectangles
Out: 24th August 2010 Due: 2nd September 2010 (Thu) at 11:59pm
In this assignment you will write a class to represent an “axis-aligned” rectangle, i.e. a rectangle with only
horizontal and vertical sides. You will write various methods to support different operations on Rectangle
objects and finally, you will test your class by defining several rectangles and comparing them in various ways.
A rectangle is represented by its lower left corner (x,y), width and height. Write a class that represents a
rectangle as defined above. This class should have the following methods:
1. A constructor that allows you to pass the position and dimensions of this rectangle to initialize the
Rectangle object.
2. A toString() method to print out the various variables of the rectangle in a reasonable way.
3. A method area() that returns the area of the rectangle.
4. A method overlaps(Rectangle a) that takes as parameter a Rectangle object ‘a’ and returns true if this
rectangle overlaps with ‘a’.
5. A method intersect(Rectangle a) that takes as parameter a Rectangle object ‘a’ and returns the rectangle
that is formed by the intersection of this rectangle with ‘a’. Your method should return null if the two
rectangles do not overlap.
6. A method union(Rectangle a) that takes as parameter a Rectangle object ‘a’ and returns the rectangle
that represents the union of this rectangle and ‘a’. The union of two rectangles is defined as the smallest
rectangle that encloses both rectangles. Hint: The union and intersect methods are much more similar
to each other than you might think!
Now write another class with a main method. When you run the program, it should ask you for the following
inputs from the keyboard in the following order:
1. Number of rectangles
2. Position (x,y) and the dimensions (width and height) of each rectangle in order.
Finally, it should print the following in the following order:
1. The areas of all the rectangles in the order that they were entered.
(x,y)
width
height
2. All pairs of rectangles that overlap each other. For each such pair, it should also print the position and
dimensions of the intersection of the two rectangles.
3. The total number of overlaps found in step 2.
4. The position and dimensions of the rectangle obtained by the union of all the rectangles. This is the
smallest rectangle in which all the input rectangles will fit. It is called the “bounding box”.
See the accompanying file for an example of the expected input and output.
Applications: Such rectangle classes are very widely used. You will find a similar class in almost any windowing
toolkit/GUI library. They are used to manage overlapping text boxes, to detect whether a mouse is in a certain
region of the window, etc. Another practical application of rectangles and their operations is in large-scale
integrated circuit design where layouts on the chip are tested for consistency before fabricating the chip. If the
layouts (usually rectangular) of two components overlap each other, the chip cannot be fabricated in a single
layer. In practice more efficient algorithms are used to find all overlaps, but the concept is the same.
Expectations from a perfect program:
1. The class should have the same method names as above.
2. The source code should be suitably commented.
a. Inside every class should be a short explanation of what the class represents and what it is used
for.
b. Just before every method signature, there should be information about what the method does,
what every parameter means and what the method returns, if anything.
c. Just inside every method there should be information about what exactly the method does (in
steps).
3. The inputs should be taken in the specified order.
4. The outputs are exactly as specified.
What/How to submit: Turn in all your source code files (*.java) in a single zipped file on Blackboard. You do not
have to turn in your .class files.

Code :

```package rectangle;   import java.awt.Point; import java.awt.geom.Line2D;   /** * @author Paul * */ public class Rectangle { private double width; private double height; private double area; private double x; private double y; private Point p; private Line2D.Double line1; private Line2D.Double line2;   public Rectangle(double x, double y, double width, double height) { // makes the private variable height equal to the value of height in constructor. this.height = height;   // makes the private variable width equal to the value of width in constructor. this.width = width;   this.x = x; this.y = y;   line1 = new Line2D.Double(x, y, x, y - height); line2 = new Line2D.Double(x, y - height, x + width, y - height); //p = new Point(x,y);       }           public String toString() { System.out.println("width is: " + width + "; height is: " + height + "; area is: " + area + "; Point is: " + x + "," + y); String str = "width is: " + width + "; height is: " + height + "; area is: " + area + "; Point is: " + x + "," + y; return(str); }     public double area() { area = width * height; return(area); }   public boolean overlaps(Rectangle a) { // I somehow need a switch structure here, but have never done one in my life before.   /* 1. Draw the three cases on a piece of paper: two rectangles overlap partially, one rectangle is inside the other and two rectangles that do not overlap.   2. You have to write a method that correctly identifies whether it is case 1 or 2, in which case you return true. Or case 3, in which case you return false.   3. Look at the simplest case, the first one. In terms of only (x,y,width,height) of both rectangles (i.e. 8 values in total) can you express the partial overlap? That is, try to come up with a condition involving these 8 variables that will evaluate to true when the two rectangles partially overlap. Once you have this, see how you must change this condition so that it works for the other two cases. */     }   public Rectangle intersect(Rectangle a) {   if (a.overlaps(a) == true) { return(the new Rectangle); }   else return(null); }   public Rectangle union(Rectangle a) { // I know that you use two coordinates, the lower left and the upper right, of the new Rectangle, to get the height and width of the new Rectangle but how do you get those two points? } }```

Code :

```package rectangle;   import java.util.Scanner; import java.io.*; import java.util.*;   // this class is the test program. It will ask the user for the number of rectangles and for the bottom-left corner // coordinate and the width and height and will output the area, all the pairs of rectangles that overlap each other, // and also the lower-left corner postion and the dimensions of the rectangle formed by the intersection of each such pair // and also, it will output, by output I mean print out, the total number of overlaps, the position and dimensions of the rectangle that // will hold all of the other rectangles. /** * @author Paul * */ public class TestRectangleProgram {   /** * @param args */ static Scanner console = new Scanner(System.in); public static void main(String[] args) { // TODO Auto-generated method stub   // prints Enter the number of rectangles.   // creates int variable numOfOverlaps and initializes it to 0. int numOfOverlaps = 0; System.out.println("Enter the number of rectangles.");       // each array stores a value, xValue, yValue, widthArray, and heightArray. // The array values, made by the user inputs in the for loop, // will be called by another for loop that will print out // xCords[0], yCords[0], widthArray[0], heightArray[0] + add a line // xCords[1], yCords[1], widthArray[1], heightArray[1] and so on // for the widthArray and heightArray, their values will be made to fill // areaArray like this in the for loop: areaArray[j] = rect[j].area() , // where rect is an array of Rectangles the size of the number of rectangles.     // user input for # of rectangles int numOfRectangles;   numOfRectangles = console.nextInt();     // array of x values that will get filled in by the for loop. The array size is the number of rectangles. double[] xCords = new double[numOfRectangles];   // array of y values that will get filled in by the for loop. The array size is the number of rectangles. double[] yCords = new double[numOfRectangles];   // array for the width that will get filled in by the for loop. The array size is the number of rectangles   double[] widthArray = new double[numOfRectangles];   // array for the height that will get filled in by the for loop. The array size is the number of rectangles   double[] heightArray = new double[numOfRectangles];   // array to store areas. Array size is the number of rectangles. double[] areaArray = new double [numOfRectangles];           // for loop will ask user for x-coordinate of rectangle, y-coordinate of rectangle, height of rectangle, and width of rectangle // until it has done so for the number of rectangles. j is set to 0 and will increase until the for loop exits when the // value of j reaches the number of rectangles. Rectangle[] rect = new Rectangle[numOfRectangles]; for (int j = 0; j < numOfRectangles; j++) { System.out.println("Enter the x-coordinate for Rectangle " + (j+1)+ " "); xCords[j] = console.nextDouble(); System.out.println("Enter the y-coordinate for the Rectangle " + (j+1) + " "); yCords[j] = console.nextDouble(); System.out.println("Enter the width for the Rectangle " + (j+1) + " "); widthArray[j] = console.nextDouble(); System.out.println("Enter the height for the Rectangle " + (j+1) + " "); heightArray[j] = console.nextDouble(); rect[j] = new Rectangle(xCords[j], yCords[j], widthArray[j], heightArray[j]); areaArray[j] = rect[j].area(); System.out.println("Rectangle " + (j+1) + ": " + rect[j].toString());         }   for (int k = 0; k < numOfRectangles; k++) { System.out.println("The area of Rectangle " + (k+1) + " is " + areaArray[k] + "."); }   for(int v = 0; v < numOfRectangles; v++) {// beginning of for for (int w = v + 1; w < numOfRectangles; w++) { // beginning of inner for if (rect[v].overlaps(rect[w]) == true) { // beginning of if numOfOverlaps = numOfOverlaps + 1; } // end of if } // end of inner for } // end of for System.out.println("The number of overlaps is: " + numOfOverlaps); for (int p = 0; p < numOfRectangles; p++) {   } }   }```

How do you get it to perform the union(Rectangle a) method on each of the rectangles like so

Rectangle r = Rectangle 1.union(Rectangle2.union(Rectangle3.union(Rectangl e4.union(Rectangle.union(etc))))

or something like that

How do you get it to make the intersect method work? I know you use two corners or something, but how do you get these points?
• September 1st, 2010, 20:21
Norm
Re: I think I need an algorith
What are your questions? Again, I'm too lazy to read through all of your assignment and to try to figure out what you need to know and what you need to do. You'll have to read the assignment and come up with specific questions about the project where you want help.
• September 1st, 2010, 21:07
javapenguin
Re: I think I need an algorith
Quote:

Originally Posted by Norm
What are your questions? Again, I'm too lazy to read through all of your assignment and to try to figure out what you need to know and what you need to do. You'll have to read the assignment and come up with specific questions about the project where you want help.

How to write a switch struture.

Am sending a document with stuff in it:

In this assignment you will write a class to represent an “axis-aligned” rectangle, i.e. a rectangle with only
horizontal and vertical sides. You will write various methods to support different operations on Rectangle
objects and finally, you will test your class by defining several rectangles and comparing them in various ways.
A rectangle is represented by its lower left corner (x,y), width and height. Write a class that represents a
rectangle as defined above.
A method overlaps(Rectangle a) that takes as parameter a Rectangle object ‘a’ and returns true if this
rectangle overlaps with ‘a’.
A method intersect(Rectangle a) that takes as parameter a Rectangle object ‘a’ and returns the rectangle
that is formed by the intersection of this rectangle with ‘a’. Your method should return null if the two
rectangles do not overlap.
A method union(Rectangle a) that takes as parameter a Rectangle object ‘a’ and returns the rectangle
that represents the union of this rectangle and ‘a’. The union of two rectangles is defined as the smallest
rectangle that encloses both rectangles. Hint: The union and intersect methods are much more similar
to each other than you might think!

1. Draw the three cases on a piece of paper: two rectangles overlap
partially, one rectangle is inside the other and two rectangles that do
not
overlap.

2. You have to write a method that correctly identifies whether it is case
1

or 2, in which case you return true. Or case 3, in which case you return
false.

3. Look at the simplest case, the first one. In terms of only
(x,y,width,height) of both rectangles (i.e. 8 values in total) can you
express the partial overlap? That is, try to come up with a condition
involving these 8 variables that will evaluate to true when the two
rectangles partially overlap. Once you have this, see how you must change
this condition so that it works for the other two cases.

I have received a number of questions regarding how to approach the intersect and the union methods. Here is a hint: it may be easier to think of a rectangle in terms of two points: lower-left and upper-right. To get the answer to both these methods, you must find these two points for the resulting rectangle in terms of what you know about the two given rectangles. After that subtracting the first point from the second will get you the width and height respectively.
• September 1st, 2010, 23:23
javapenguin
Re: I think I need an algorith
I need to know how to set up a switch structure.
• September 1st, 2010, 23:31
Brt93yoda
Re: I think I need an algorith
Quote:

Originally Posted by javapenguin
I need to know how to set up a switch structure.

By switch structure do you mean:
Code java:

``` int testInt = 10;   switch (testInt) { case 1: system.out.println("int = 1"); case 2: system.out.println("int = 2"); ...ETC }```
• September 1st, 2010, 23:37
helloworld922
Re: I think I need an algorith
You forgot the break statements.

Code Java:

```int testInt = 10; switch(testInt) { case 1: System.out.println("int = 1"); break; case 2: System.out.println("int = 2"); break; default: System.out.println("the int was not 1 or 2"); }```
• September 1st, 2010, 23:45
Brt93yoda
Re: I think I need an algorith
I thought I was missing something. I barely use switch statements.
• September 2nd, 2010, 16:21
javapenguin
Re: I think I need an algorith
I have the problem where I'm not sure how to get a class that takes a Rectangle as a parameter to compare it to another Rectangle inside the class itself.

Code :

``` public boolean overlaps(Rectangle a) {   if ((b.getUpperRightPosition().getX() < a.getBottomLeftPosition().getX()) || (b.getUpperRightPosition().getY() < a.getBottomLeftPosition().getY()) || (b.getBottomLeftPosition().getX() > a.getUpperRightPosition().getX()) || (b.getBottomLeftPosition().getY() > a.getUpperRightPosition().getY())) { return(false); }   else return(true);       }   public Rectangle intersect(Rectangle a) { if (((a.getBottomLeftPosition().getX() <= b.getBottomLeftPosition().getX()) && (b.getUpperRightPosition().getX() <= a.getUpperRightPosition().getX())) && ((a.getBottomLeftPosition().getY() <= b.getBottomLeftPosition().getY()) && (b.getUpperRightPosition().getY() <= a.getUpperRightPosition().getY()))) { return(b); }   else if (a.overlaps(b) == false) { return(null); }   else return(new Rectangle(innerRectangle.getBottomLeftPosition().getX(), innerRectangle.getBottomLeftPosition().getY(), innerRectangle.getUpperRightPosition().getX() - innerRectangle.getBottomLeftPosition().getX(), innerRectangle.getUpperRightPosition().getY() - innerRectangle.getBottomLeftPostion().getY()));   }   public Rectangle union(Rectangle a) { if (((a.getBottomLeftPosition().getX() <= b.getBottomLeftPosition().getX()) && (b.getUpperRightPosition().getX() <= a.getUpperRightPosition().getX())) && ((a.getBottomLeftPosition().getY() <= b.getBottomLeftPosition().getY()) && (b.getUpperRightPosition().getY() <= a.getUpperRightPosition().getY()))) { return(a); } }   public Position getBottomLeftPosition() { return( new Position(x, y)); }   public Position getUpperRightPosition() { return(new Position( x + width, y + height)); } }```
• September 2nd, 2010, 17:10
Norm
Re: I think I need an algorith
Quote:

how to get a class that takes a Rectangle as a parameter
After over 200 posts and you don't know the difference between a class and a method. ?????

When comparing two objects of the same class in a method of that class and that has one object passed to it as a parameter, use the "this" reference for the members of the current class and use the passed parameter to get at the other objects members:
this.getX() >= parameter.getX()
• September 2nd, 2010, 18:18
javapenguin
Re: I think I need an algorith
Quote:

Originally Posted by Norm
After over 200 posts and you don't know the difference between a class and a method. ?????

When comparing two objects of the same class in a method of that class and that has one object passed to it as a parameter, use the "this" reference for the members of the current class and use the passed parameter to get at the other objects members:
this.getX() >= parameter.getX()

#-o#-o#-o#-o#-o#-o#-o#-o#-o#-o#-o#-o#-o#-o
• September 2nd, 2010, 21:35
javapenguin
Re: I think I need an algorith
Ok how do I get something to perform the union method on Rectangles in an array of size n;

Rectangle rectBig = rect[n-1].union(rect[n-2].union(rect[n-3].union(rect[n-4].union(rect[n-5].union(rect[n-6].union(etc)....union(rect[0]) ?
• September 2nd, 2010, 22:04
javapenguin
One last question
How do you get it to do something like this:

where there is an array of Rectangles of size n;

Rectangle superRect = rect[n-1].union(rect[n-2].union(rect[n-3].union(etc... .union(rect[0]))

:((:((:((~X(~X(^:)^^:)^^:)^^:)^^:)^^:)^^:)^^:)^^:) ^^:)
• September 2nd, 2010, 22:38
javapenguin
Help!!!
I really need to know how to do that last thing with the union!!!

Too late now! I had to turn it in!

```unionShape = empty shape for every rectangle in the list: unionShape = union(unionShape, rectangle)```