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