How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)

Question

Let's say I have a point $(x_0, y_0)$, and some other points $(x_1, y_1), (x_2, y_2) ... (x_n, y_n)$, such that all of them are lattice points; all have integer coordinates. Let's further assume that all points are distinct.

Is there any way to sort points $1...n$ by order of the angle they make with $(x_0, y_0)$ and the $x$-axis, without ever having to resort to using floating-point numbers?

(This has applications within the Convex Hull Problem; specifically, the Graham Scan, an $O(NlogN)$ algorithm whose first step is to choose the lowest point and to sort all other points in increasing order of the angle they make with the $x$-axis).

My idea: $cos(\theta)$ is strictly decreasing from $0^{\circ}$ to $180^{\circ}$, and it is well-known that given two vectors $v_1$ and $v_2$, $cos(\theta) = \frac{a \cdot b}{|a||b|}$. Therefore, treat every point as a vector from $(x_0, y_0)$ to that point (i.e. $\langle x_i - x_0, y_i - y_0 \rangle$); then, comparisons between angles can be done by comparisons between $\frac{a \cdot b}{|a||b|}$. And to take care of the fact that $|a|$ and $|b|$ may not be integers since they are the square root of an integer, we can square the fractions and compare those. The last thing to do is to realize that the squared fractions will always be positive, while the $\frac{a \cdot b}{|a||b|}$ values may initially be negative. To fix this, just keep an extra boolean telling whether or not the value is positive or negative, and proceed...

But this seems pretty complicated, and I'm not even completely sure if the logic is correct. Does anyone have a better idea/a confirmation that this idea will work?

Answer 1

In computational geometry, we often sort the points clockwise or anti-clockwise. For example, in Graham's scan, the algorithm sorts the points with respect to $(x_0,y_0)$ in clockwise or anti-clockwise order. For that, you can use the concept of left rotation or right rotation. That can be done using cross-product. It does not require any division or square roots. It is given in CLRS in more detail.

Your solution is also correct. Just adding something more. When you compare two fractions $a/b$ and $c/d$. Simply check if $ad < bc$ assuming without the loss of generality that $d$ and $b$ are positive real values. In this way, you can avoid using division operations.