Quick Hull

Intro

STATUS: Working. Needs to be rebuilt as a tool.

Implementing the quickhull algorithm. Visually verifying the algorithms workings.

Source

Files

Doxygen

Code History

• 

  Let the three red points define a triangle, the purple points verify that the inside the triangle test works. The orange lines are the minimized point on the line segment to the other red point on the boundary. I ended up using a global static variable and hacked into halplane.cpp to insert debug code, which can be turned off so not to polute the code with dependencies.
• 

  Used graphical methods to verify visually as the algorithm was being built incrementally. Here two red points are on the boundary and are left and right most points. The third red point is the furthest away from the line joining the other two red points, including the green points. The blue points are the points on the other side of the line. By counting all points I verified that no points were being lost. Command line $./main numPoints=10 added to vary the number of points. Call me crazy but I have a little ruler which I hold up to my screen and verify that the point displayed is the furthest distance from the line.

• Thought Extensively on whether or not to use iterators or integer indexes to refer to points. Crunch came when writing halfplane where a decision had to be made. I choose to use integer indexes and a global vector of points for the following reasons.
  1. if all my algorithms use integer indexes then they can be interchanged with each other somewhat.
  2. information is preserved. e.g. If the points had a previous ordering, after applying the algorithm you still know where the points were initially. If I used the data structures natural iterators this would be lost.
  3. I felt that other programmers do not understand iterators, but could understand integer points better, and if I write algorithms with these I may better communicate the algorithm. Further this is not a loss because when I implement the algorithm for real I could always use the data structures natural iterators. Even thinking about this discussion made me realize why some applications get locked into their data structures and can no longer do things.
  4. I originally just planned to write the algorithm to calculate a convex hull, but realized that it could be modified to create a nlogn tessellation algorithm, do I did the doc for the new algorithm. A worthwhile diversion.

TODO

• Clean up code.
• Quick Hull tool.
  Input: file of points.
  Output: File of points.
  Output: File of indexes to the points.
  Similarly with vectors for communicaition in C++.
• Template the type of point.
• Rewrite using the mathlib 2dhalfspace.
• Somehow separate the graphics from the algorithm.
  For example one algorithm iteration then display the algorithms state.
• Implement in 3D.
  The algorithm is incorrect or I have implemented it in the wrong way.
  The algorithm steps need to be visually displayed, each iteration should be able to be stepped through. I expect the three half space containers of the previous iteration to be displayed in unique colors, and the current or next half space container. Hence it needs to be written as an iterator.
•