Loading...

Lab 8: 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 textbook's Point2D). We will find the bounding box and convex hull of a set of points. We will do this by creating custom bag, stack and heap data structures.

Bounding Boxes

You are provided with a class that finds and visualizes the Bounding Box of a set of points: the north, east, south & west boundaries. It assumes we have access to a bag with top , left , right , and bottom methods

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

Point2DBag bag = new Point2DBag();

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

bag.add(p);

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

}

Point2D left = bag.left();

Point2D right = bag.right();

Point2D top = bag.top();

Point2D bottom = bag.bottom();

StdDraw.setPenColor(StdDraw.ORANGE);

StdDraw.line(right.x(), bottom.y(), right.x(), top.y());

StdDraw.line(left.x(), bottom.y(), left.x(), top.y());

StdDraw.line(left.x(), bottom.y(), right.x(), bottom.y());

StdDraw.line(left.x(), top.y(), right.x(), top.y());

}

Point2DBag

Create a Point2DBag class that supports the standard Bag methods along with a few additional methods:

public class Point2DBag

Point2DBag() create an empty bag

​​Bounding Boxes

​​Point2DBag

Bounding Boxes

Point2DBag