I'm trying to design an algorithm to find the convex hull of a set of co-ordinates using the slope between two points to determine if a point is part of the convex hull. I'm testing a set of five points:
$$A(135,127),B(444,249),C(441,420),D(275,210),E(383,59)$$
Plotting these points looks like the below:
What I first do is find the co-ordinate with the minimum y-value ($E(383,59)$), and then compare the slope of the line between that point and every other point:
$$\begin{align} EA_{slope} &= \frac{59-127}{383-135} = \frac{-68}{248} = -0.24 \\ EB_{slope} &= \frac{59-249}{383-444} = \frac{-190}{-61} = 3.11 \\ EC_{slope} &= \frac{59-420}{383-441} = \frac{-361}{-58} = 6.22 \\ ED_{slope} &= \frac{59-210}{383-275} = \frac{-151}{108} = -1.40 \\ \end{align}$$
I'm looking for the smallest magnitude slope in the negative direction which ends up being $EA$. Using five points was probably a poor idea, but if there were more (so I don't hit the minimum x-value co-ordinate so fast), I'd redo this in the same direction until I find all points in the bottom-left quarter of the hull.
The problems I come upon are that it's very inefficient as I will have to iterate over $n*(n-1)*(n-2)*...*1$ points ($O(\text{n log n})$?) and I'm not too sure how to go about getting all of the quarters of the hull.
My thought was:
Smallest magnitude negative slope = point is in bottom-left quarter
Biggest magnitude positive slope = point is in the top-left quarter
Smallest magnitude positive slope = point is in the top-right quarter
Biggest magnitude negative slope = point is in the bottom-right quarter
Is this correct? Is there a better way of doing this?
This is quite a well-traveled topic. You are struggling (it seems) to implement the Graham scan algorithm correctly. This is well-described in a number of locations, some including code. I will cite my own, associated with Computational Geometry in C: link here.
(Image from Discrete and Computational Geometry.)