TD 1 - 2D Convex hulls

1. 2D Convex Hull: Andrew's algorithm

Now we are going to compute the convex hull of a set of points in 2D. Several algorithms were presented in class, some of which have complexity O(nlogn). Usually, Graham’s scan is illustrated, but today we will implement a variant instead: Andrew’s algorithm (outlined in the lecture), which avoids the use of trigonometric functions and sophisticated sorting (but, on the other hand, requires manipulating two lists). The algorithm computes the upper and lower parts of the convex hull separately. They will be concatenated at a later stage. Since this is the first lab session and you are not yet familiar with geometric data structures, we provide you with:

the skeleton of the class ConvexHull in file ConvexHull.java, containing the functions to complete,
a class TestConvexHull allowing testing your code.

Tip: We suggest that you start this exercise by taking a quick look at the ConvexHull class: it contains a number of types and data structures that may make it easier for you to work with the Jcg library.
Here are some of the classes and methods you will need for this exercise:

Point_2 (in package Jcg.geometry): implementation of 2D points and corresponding operations (real coordinates)
Fenetre: provide a 2D visualization of 2D points and segments
GeometricOperations_2 and GeometricPredicates_2 (in Jcg.geometry.kernel): provides geometric predicates, both exact and approximate (e.g. testing the ccw-orientation of a triangle)

For sorting the points, you can use algorithms already provided by Java, for example by using a comparator class, which allows you to customize the ordering of the points according to your needs:

 class SortPointsByCoordinates implements Comparator<Point_2> {
 
 public int compare(Point_2 p1, Point_2 p2) {
 return p1.compareTo(p2);
}
 }

You can use the method sort of the class Collections, that apply to data structures implementing the interface Collection : for instance, one can use an objet of type ArrayList<Point_2> to store a list of 2D points. To sort the list l it suffices to call Collections.sort(l, new SortPointsByCoordinates()).

1a. Upper convex hull

For now, let us focus on computing the upper part of the convex hull, and let U denote the list that will form this part. As already seen in today’s lecture, points must be removed incrementally in order to make the hull convex. To do this, we traverse the list of points from left to right, and before adding a newly considered point v to the list U, we perform the following check.
While the list v

contains at least two elements and
the triangle defined by (v, u[1], u[2]) is clowck-wise oriented, remove the first element from the list.

Complete the method computeUpperHull(...), that compute the upper convex hull.

1B. Lower convex hull

Complete the method computeLowerHull(...) that computes the lower convex hull: it is sufficient to slightly modify the previous code.

1C. Fusion des deux enveloppes

Finally, all that remains is to complete the method that merges the two lists of points, which terminates the computation of the convex hull.
Test your implementation using the TestConvexHull class.

2. Degenerate point clouds (optional)

Now, it remains to check whether your code is robust and can handle degenerate cases as well as errors caused by rounding issues (which lead to a loss of precision). Test your code by modifying the main function of the TestConvexHull class to generate a new point cloud (degenerate case).

    	int n=100; // number of input points
    	// create input points at random
    	//ArrayList<Point_2> vertices=pointsInCircle(n); 
    	ArrayList<Point_2> vertices=degeneratePoints(n);

What happens?

Question: Modify your code so that it is robust and able to correctly compute convex hulls.