Given three points $p$, $q$, and $r$, you can determine whether $r$ is to the left or right of the line $pq$ by taking the determinant of the matrix $\begin{bmatrix}1 & p_x & p_y \\ 1 & q_x & q_y \\ 1 & r_x & r_y \end{bmatrix}$. Additionally, that determinant is twice the surface area of the triangle formed by $pqr$, by the Shoelace method.

Considering these two facts, why is this test attractive for an algorithm that determines the Convex Hull of a set, for a) integer coordinates, and b) floating point coordinates? Is it because of the complexity class of the test, or what?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.