Lab 7: Bounding Boxes & Convex Hulls

Bard College – Computer Science – Data Structures

In this lab we will create programs to compute the perimeter of a set of points (the book's Point2D object). We will find the bounding box and convex hull of a set of points.

Bounding Boxes

Create a class BoundingBox that computes descriptive statistics of a set of 2D points.

public class BoundingBox

BoundingBox() create an empty bounding box

void add(Point2D item) add a point

int size() number of items in the box

Point2D top() the top-most point (max y)

Point2D bottom() the bottom-most point (min y)

Point2D left() the left-most point (min x)

Point2D right() the right-most point (max x)

Point2D centroid() the mean (centroid) of the points

All the methods should run in constant time, e.g., the time to find the left-most point should be independent of the number of points in the bounding box. Or to put it another way: you should not need to traverse the lists or arrays to perform any operation.

The following code visualizes the Bounding Box of a set of points: the north, east, south & west boundaries.

import edu.princeton.cs.algs4.StdDraw;

import edu.princeton.cs.algs4.StdRandom;

import edu.princeton.cs.algs4.Point2D;

public class BoundingBox{

public final static int W = 800;

public final static int H = 800;

public final static int N = 150;

public static void main (String[] args){

BoundingBox box = new BoundingBox();

StdDraw.setCanvasSize(W, H);

StdDraw.setXscale(0, W);

StdDraw.setYscale(0, H);

StdDraw.setPenColor(StdDraw.GREEN);

for (int i = 0; i < N; i ++){

Point2D p = new Point2D(StdRandom.gaussian(W/2, W/8),

StdRandom.gaussian(H/2, H/8));

box.add(p);

StdDraw.filledCircle(p.x(), p.y(), 3);

}

Point2D left = box.left();

Point2D right = box.right();

Point2D top = box.top();

​​Bounding Boxes

Bounding Boxes