# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 5 Testing
### Test-First Development  
For each of our programs serious debugging has been necessary. At the very beginning, the test framework was primitive; it checked the answers in quadratic time. Thereafter, a natural workflow was to repeatedly write a new implementation and test it. The implementation under consideration was corrected whenever necessary. The test framework was gradually improved when we understood the corner cases better. As shown in Section 5.3, we succeeded in using the test framework to reveal an error at the algorithm level. However, its main purpose was to help remove some small embarrassing errors from the code. To simplify the implementation task, we used the generic functions of the C++ standard library whenever possible, e.g., std::sort, std::minmax_element, std::max_element, std::partitioning, std::reverse. The consequence of this choice was that our code relies on iterators, array indexing is not used. When looking at our code, sometimes there seem to be unnecessary complications. Often, however, these complications are there to fix some correctness issue. The basic reason for a complication--which can just be an irritating if statement--is the expectation that the programs must be able to handle multiset data, degenerate cases, and arithmetic overflows. To understand such complications better and to make it easier for others to develop reliable code, we list below some problem areas where we made programming errors. It is imperative to emphasize that the test framework was the most important aid to detect these issues. **Small instances. **: It is trivial to handle the cases \(n=0\) and \(n=1\), but already the case \(n=2\) introduces a complication: If the two points are duplicates, special handling is necessary. For larger \(n\), it is also possible that the west pole and the east pole coincide, so this special case must be handled separately. **Referential integrity. **: Let p and q be two iterators pointing to some elements. A typical way of swapping these elements is to invoke std::iter_swap(p, q). An unfortunate consequence of this swap is that the iterators are not valid after this operation. It may be necessary to execute std::swap(p, q) just after it. The situation becomes worse when there is another iterator \(r\) pointing to the same position as p or q. After the swap, this iterator is not valid any more. **Empty ranges. **: Often a subroutine expects to get a range specifying a sequence of elements. In most cases the range is non-empty, but we should also be prepared to handle the empty case. **Duplicates. **: These can appear in many places, including places where you do not expect them. For a set of points in general position, it may be enough to execute a single assignment, but in the case of duplicates we may need a loop to jump over them. **Points on a rectilinear line. **: When several points are on the same rectilinear line and this happens when finding a pole, a rule is needed to know which one to choose. To break the tie, we use lexicographic ordering even though we want to avoid it in sorting. In a typical case, there is only one pole per direction, so we wanted to avoid the overhead of maintaining two poles per direction, i.e., the bottommost west pole and the topmost west pole. **Elimination of concave points. **: After a pole is found, there may be other points on the same rectilinear line. The standard backtracking procedure [33] is not always able to process collinear points correctly. Therefore, a separate routine is needed to find the next convex-hull point that is on the same line and farthest away from the found pole. **Points on a line. **: When finding the farthest point from a line segment and several points are equally far, it is necessary to use lexicographic ordering as a tiebreaker. Again, the reason is the standard backtracking procedure--it may fail if collinear points are not processed in the correct order. **Index arithmetic. **: When computing the convex hull in pieces, the points may not be in consecutive positions any more.