Convex Hull | |||||

One Page |
02_clockwise
20161205
## The clockwise functionAs you gathered from the outline of the algorithm in the introduction, we need to write a function to decide whether the motion from point 1 to point 2 to a point 3 is clockwise or counterclockwise or collinear. Let's focus on that first. ## Triange areaThe area of a triangle can be calculated from following determinant: It happens to be so that when the area is negative, the motion from point 1 -> 2 -> 3 is a counterclockwise motion. When the calculated area is positive, the motion from point 1 -> 2 -> 3 is a clockwise motion. And when it's zero? Yes, you've guessed it: the points fall on the same line, ie. they are collinear. . ## Example ProgramThe following program is for inspecting whether the clockwise function works as expected: it draws a number of cases, with p1 always at (50,0), p2 at ( 20..80, 50), and p3 random. Depending on clockwise or counterclockwise, the line is drawn in either red or green, to make it possible to visually inspect the correctness.
Note: the x() and y() functions are convenience functions to get the x and y element from a point (a tuple with 2 elements), because this formula is easier to read ..
.. than this one ..
## Example PlotThe following is a plot generated by the above program. When inspecting clockwise or not, start with P1 at the bottom, and choose a line going up to P2, and continue to P3. Is it a clockwise motion? The line should be in red then. |