Loading...

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?

​​Bounding Boxes

​​The BoundingBox​ Interface

Bounding Boxes

The BoundingBox Interface