Thread: 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.

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.

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.

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

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?

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.

You forgot the break statements.

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

I really need to know how to do that last thing with the union!!!

Too late now! I had to turn it in!

Much easier to use a loop.

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