1
$\begingroup$

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?

$\endgroup$

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.