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.

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.

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

Re: I think I need an algorith

intersects() can also be used for collision detection, right?

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.

Re: I think I need an algorith

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.

Re: I think I need an algorith

Trying not to be annoying, but what is an "accelerator structure?"

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.

1 Attachment(s)

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(

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.

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?

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.

1 Attachment(s)

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.

Re: I think I need an algorith

I need to know how to set up a switch structure.

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
}

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

Re: I think I need an algorith

I thought I was missing something. I barely use switch statements.

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

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()

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

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]) ?

Re: I think I need an algorith

Much easier to use a loop.

Code Pseudo:

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