Project 3: Split Rectangles On An Image

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

Project 2: Image pointillism and transparency

[huge_it_gallery id=”4″]

Project 2 of the 2D Generative Design has two parts: first, creating a copy of an image whose dimension is twice as big as the original image and filling in the pixels of the new image by randomly sampling the pixels from the old image, and second, making an image transparent.

Below is a snippet of code that explains the key concept for the first part:


void pointillismAgent() {

int rx, ry;
for (int i = 0; i < 10000; i++){ rx = (int) random(im3.width); ry = (int) random(im3.height); c1 = im3.get(rx,ry); pushMatrix(); translate(0, im3.height); fill(c1); noStroke(); ellipse(2*rx, 2*ry, 4, 4); popMatrix(); } }

Each iteration in the above for loop randomly determines a pixel location in an original image (im3) and extracts the color of that pixel, transforms the coordinate system to where we want our new image to be and draws a circle at twice the pixel location of the original image(this is because we are scaling the new image by twice the dimension of the original image). An arbitrary width and height of 4 and 4 were chosen as dimensions for the circle.

Below is a snippet of code that explains the key concept for the second part (transparency):


void drawTransparent(){
im4 = loadImage("paint_small.jpg");
for (int i = 0 ; i < im2.width ; i++){ for (int j = 0 ; j < im2.height ; j++) { c1 = im2.get(i,j) ; greyScale = (int) (red(c1) + green(c1) + blue(c1)) / 3 ; // if greyscale is black, make pixel fully transparent, i.e. alpha = 1 if ( greyScale < 50 ) { c2 = color ( red(c1), green(c1), blue(c1), 1) ; im4.set(i,j,c2) ; } } }

The doubly nested for loop above extracts the greyscale color of each pixel of the original image(im2) and sets the color of that pixel to alpha value of 1 and assigns that pixel to the new image im4. Notice that the original image has a black background and sets those pixels transparency (alpha) to 1. This technique is only effective when there an image with solid background like white or black.

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

[huge_it_gallery id="5"]

Images in the first column are the original images and in the second column are its modification generated computationally using the aforementioned techniques.

The source code of this project can be downloaded from here:
.zip file (120KB)