[huge_it_gallery id=”8″]

Project 3 of the 2D Generative design consists of a grid of rectangles on top of an image. The grid can be toggled on and off based on user entered keys. Mouse click on any particular grid would split the rectangles in that region into several pieces. Each split rectangle is filled by the average color sampled from the background image at the corresponding region. Two types of algorithms are used in the program to search for a rectangle that contains the mouse – linear search and the binary search. The search method can be selected based on user entered keys. Note that timing for sorting is not included in timing calculation for binary search. In a commodity laptop with Intel Core i3, 1.9 GHz micro-processor with 8 GB RAM,for about 20,000 rectangles, average timing to find rectangles to split using linear search was 0.448 milliseconds (approx.) and using binary search was about 0.252 milliseconds.

Below is a snippet of code that explains the key concept using the linear search method:

double timeLinearSearchStart = millis();

for (int i = 0; i < theRects.size (); i++) {
if (theRects.get(i).doesContain(mp)) {
println("mouse contained by Rectangle # " + i ) ;
println("Now splitting the rectangle....") ;
Rectangle[] tempRects = theRects.get(i).splitRect(mp) ;
theRects.remove( i) ;
for (int j = 0; j < tempRects.length; j++) {
theRects.add( tempRects[j]) ;
}
break;
}
}
double timeLinearSearchEnd = millis();

theRects is an ArrayList of Rectangle objects whose increases with a mouse click that splits several rectangles neighboring the mouse position. The idea is to iterate through the list of Rectangle objects and check if it contains the mouse. If yes, we split that rectangle, delete the existing rectangle that was split and add two new rectangles the arrayList theRects. A very simple technique, which only works when a rectangle is not rotated in a coordinate system, is used to check whether a point is inside a rectangle. Let x, y be an arbitrary point, and (x1, y1) be the lower left point of a rectangle, and (x2,y2) be the lower right point of the rectangle. It is inside that non-rotated rectangle if the condition: (x > x1 && x < x2) && (y > y1 && y < y2)) is true.

Below is a snippet of code that explains the key concept using the binary search method:

Collections.sort(theRects);

double timeBinarySearchStart = millis();

int index = Collections.binarySearch(theRects, new Rectangle(new Point(mp.getX(),0), 0, 0) );

if (index < 0){
index = (-1 * index) - 2;
}
int tempX = theRects.get(index).getPoint().getX();
index = tempX/colWidth * numRows;
for (int i = index; i < theRects.size(); i++)
if (theRects.get(i).doesContain(mp)) {
println("mouse contained by Rectangle # " + i) ;
println("Now splitting the rectangle....") ;
Rectangle[] tempRects = theRects.get(i).splitRect(mp) ;
theRects.remove( i) ;
for (int j = 0; j < tempRects.length; j++) {
theRects.add( tempRects[j]) ;
}
break;
}
}
double timeBinarySearchEnd = millis();

The Rectangle class defined in this project implements the JAVA class Comparable that overrides its compareTo function. The compareTo function of the rectangle class allows the sort methods of the Collections package to sort the list of Rectangle objects by increasing order of its x-coordinate of the upper left corner. Here is the implementation of the compareTo function:

int compareTo(Rectangle other) {

Point otherPoint = other.getPoint();

int diff = p1.getX() - otherPoint.getX() ;

if (diff < 0)
return (-1) ;
else if (diff > 0)

return (1) ;

else

return(0) ;

}

that returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object (in this case, the Rectangle object other). When the arrayList is sorted, we perform a binary search on the list to find the nearest rectangle from the mouse position on the left hand side of the sorted list of Rectangle objects. Once found, we start a linear search from the sorted list of only those rectangles that are in the same column as the mouse position consequently giving a slight performance boost in our search of a rectangle that contains the mouse.

Below is a set of few images that show some aspect of how the code was used to generate them:

[huge_it_gallery id="7"]

The top left image shows the initial grid rectangles filled with colors sampled from the image underneath. The top right image shows the same image with perimeter of rectangles and the original image underneath. The image on the bottom left shows the perimeter of rectangles after several thousand splits and the image to its right shows the corresponding view when rectangles are filled with colors sampled from the original image underneath.

The source code of this project can be downloaded from here:

.zip file (64KB)