Lab 9: 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. We will find the bounding box and convex hull of a set of points. Custom bag, stack and heap data structures will aid in our Computational Geometry endeavor.

Bounding Boxes

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

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 bb = 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));
            bb.add(p);
            StdDraw.filledCircle(p.x(), p.y(), 3);
        }

        Point2D left = bb.left();
        Point2D right = bb.right();
        Point2D top = bb.top();
        Point2D bottom = bb.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());
    }
}

The BoundingBox Interface

class BoundingBox
          BoundingBox()        create an empty bounding box
     void add(Point2D item)    add a point to the bounding box
  boolean isEmpty()            is the bounding box empty?