Wrapping a boundary around a set of points

In this lab exercise we are going to implement an algorithm that can take a set of points in the x,y plane and construct a boundary that just wraps around the points.

Your program will read the coordinates for a list of points from a text file named "points.txt" and run an algorithm to compute a set of points needed to construct a boundary polygon that just wraps around the points in the plane. Your program will save the coordinates of the boundary points to a second file named "boundary.txt".

To help you judge whether or not your results are correct I will also provide a Java program that allows you to see both the original set of points and the boundary that you have constructed. The picture above shows the result we are looking for.

Building blocks for the algorithm

Like many algorithms in computer science, the algorithm we are going to implement in this lab exercise relies on solutions to a set of subproblems. This section of the lab materials will describe a couple of those subproblems and how to solve them.

The first idea the lab is going to make use of is the polar angle between a pair of points. The picture below illustrates this concept.

The picture shows a pair of points, p and q. The difference between the x coordinates of the two points is Δx, and the difference between the y coordinates of the two points is Δy. The polar angle θ in radians of the point q relative to the reference point p is given by the formula

θ = atan2(Δy,Δx)

The atan2(y,x) function in available in Java as the Math.atan2(y,x) method.

The second subproblem our solution will need to make use of is a procedure whether a set of three points in the plane form a left hand turn or a right hand turn.

Here is a picture of a set of three points p, q and r that form a left hand turn.

Here is a picture of a set of three points p, q and r that form a right hand turn.

Here is code for a Java method that can determine whether the three points form a right hand turn.

public static boolean rightTurn(Point p,Point q, Point r) {
  double v1x = q.x - p.x;
  double v1y = q.y - p.y;
  double v2x = r.x - q.x;
  double v2y = r.y - q.y;
  return v1x*v2y-v2x*v1y < 0;
}

The algorithm to construct the boundary

Here now is the outline of the algorithm we will use to construct a set of boundary points for a collection of points in the plane.

1. Put all of the points in a list, and make second, empty list to hold the boundary points.
2. Search the list of points to find the point with the lowest y coordinate. This point will become the reference point for the algorithm. Remove this point from the original list of points.
3. Next, compute the polar angle of each one of the remaining points relative to this reference point. Sort the list of points in order of increasing polar angle.
4. Put the reference point on the boundary list. Place the first point on the sorted list of points on the boundary list as well.
5. For each of the points after the first point on the list of points do this:
1. While the last two points in the boundary list and this point form a right hand turn remove and discard the last point in the boundary list.
2. Add this point to the boundary list.

Once this algorithm finishes we will have the list of boundary points we need.

Checking your work

At the top of these instructions you will find a button that links to a NetBeans project that you will use for this lab exercise. The NetBeans project includes a text file points.txt that you will use to provide your program with a set of points to work with. The project also includes a visualization program that will allow you to visualize your results. Running the project will launch the visualization program.

Since the visualization program expects to read a list of boundary points from a file named boundary.txt you will not be able to run the visualization program until you have written a program to compute the boundary points and save them to boundary.txt.

Add a new class to the project for your program. The main method of this new class will implement the algorithm that I outlined above. Running this program should compute and save the list of boundary points to the boundary.txt file. At that point you will be able to run the visualization program to confirm that your boundary is correct.