Assignment 06: Convex Hulls

an interactive illustration of Graham's scan algorithm

Due Friday, March 24 Monday, March 27 at 11:59pm

Overview

For this assignment, you will produce an interactive visualization of Graham’s scan algorithm for computing the convex hull of a set of points in the plane. The visualization must allow the user to (1) specify an instance of the convex hull problem by clicking an SVG element to add points to the set, and (2) step through an execution of Graham’s scan algorithm on the instance, visualizing each step taken by the algorithm.

Purpose

The purpose of this assignment is two-fold:

  1. Understand and implement Graham’s scan algorithm for computing convex hulls.
  2. Produce an interactive visualization that illustrates the algorithm and teaches a user how the algorithm works.

Resources

Graham’s scan algorithm is described in detail in Section 1.1: Convex Hulls (pdf) in Computational Geometry by de Berg et al. Techniques for allowing user interactions, algorithm visualizations, and animation were discussed at length in Lectures 07–10. You may freely use any posted code from examples in class as part of your project. However, you are responsible for understanding all of the code used in your project.

  • Download hw06-convex-hulls.zip for a skeleton of the assignment files.

  • Download ch-tester.zip for the autograder for your getConvexHull method. In order to run the autograder you will need to add the following lines to the end of convex-hull.js:

    1
2
3
4
5
6

      try {
    exports.PointSet = PointSet;
    exports.ConvexHull = ConvexHull;
  } catch (e) {
    console.log("not running in Node");
  }

    Usage instructions for ch-tester.js are included in the comments at the beginning of that file.

Specification

Your submission must consist of three files: index.html, style.css, and convex-hull.js. The first two files should specify the structure and style of your website, while all of the functionality is implemented in convex-hull.js.

You will be provided with a progam, ch-tester.js that will test the correctness of your implementation of Graham’s scan algorithm.

Interactions

When opening index.html in a web browser, the user must see:

  • a title for your site
  • a brief description of your page and how to use it
  • an initially blank SVG image that will show the visualization
  • buttons to start, step, and animate the visualization

The user should be able to add points to the set by clicking the SVG image. Once points are added to the image, the user can start a visualization of Graham’s scan algorithm with the start button. Repeatedly clicking the step button will update the image to illustrate successive steps of the algorithm. The effect of animate is the same as repeatedly steping at regular time intervals until the algorithm terminates. When the algorithm completes, the image should clearly depict the convex hull of the points added by the user.

Implementation

The provided version of convex-hull.js includes two pre-defined objects, Point and PointSet. A Point represents a point in the \(xy\)-plane (together with an ID), and a PointSet represents a collection of Points. A PointSet stores an array of Points (called points), and provides methods for sorting the array by \(x\)-coordinate and reversing the array. You should not modify the Point or PointSet implementations in convex-hull.js.

The file convex-hull.js also includes incomplete definitions of a ConvexHullViewer and ConvexHull class. Your primary task in this assignment is to compete implementations of these two objects.

  • ConvexHullViewer is an object that handles interactions between the user (website), a PointSet, and a ConvexHull object (which will implement the Graham’s scan algorithm). The ConvexHullViewer stores a PointSet ps that represents the current set of points for the visualization, and an SVG DOM element called svg. At minimum, the ConvexHullViewer should handle the following tasks:

    • adding points to ps in response to user clicks
    • adding DOM elements to svg (e.g., circle elements) to represent the points in ps
    • allow points to be (un)highlighted, (un)muted
    • draw and update line segments between points to represent portions of the convex hull

    You may wish to include other functionality that helps visualize Graham’s scan as you’d like to depict it.

  • A ConvexHull represents an instance of the convex hull problem. It stores a PointSet ps representing the input to the problem, and a ConvexHullViewer viewer that depicts the execution of Graham’s scan algorithm. It includes three methods that you must implement:

    • start, which (re)starts a visualization of Graham’s scan algorithm on ps

    • step, which performs a single computational step of Graham’s scan and updates viewer to depict the step. What constitutes a single “step” is up to you. Your goal should be to depict the execution in enough detail that a user understands how the algorithm works by looking at the sequence of steps performed by your program.

    • getConvexHull, which performs Graham’s scan algorithm without visualization (for testing purposes) and returns a PointSet representing the points on the convex hull

    You may wish to add more methods to the ConvexHull class, but the methods above are required. You should not change the names or signatures of any of the three methods above.

Assessment

30 points total

  • 10 points for page and interactions:
    • page uses correct HTML/CSS/JavaScript syntax without any errors
    • content is sensibly formatted on the page
    • page includes a brief description of the program and how to use it
    • page includes buttons to start, step, and animate an execution of Graham’s scan
    • page styling is reasonably elegant, beyond the default styles for elements (e.g., text and buttons)
  • 10 points for Graham’s scan implementation:
    • the ConvexHull.getConvexHull() method correctly implements Graham’s scan algorithm and passes all tests performed by ch-tester.js
  • 10 points for Graham’s scan visualization:
    • the visualization clearly illustrates each step of Graham’s scan algorithm
    • when the algorithm execution completes, the page clearly indicates the convex hull of the input points
    • the program visualizes an execution using both the manual step method and the animate method, which steps through the execution automatically until the algorithm terminates

Going Farther

Here are some suggestions for taking your visualization to the next level! Extra credit may be awarded.

  1. Add functionality for removing points from the set. For example, the user might click a point to highlight it, then pressing the delete key will remove the point from the visualization (and the corresponding PointSet)
  2. Add functionality to add points after an execution of the algorithm is complete. The visualization should show if the added points are within the convex hull of the previous points or not.
  3. Add a slider that allows the user to change the speed of the animated illustration.