I have a bunch of points defined by their x and y position, in my real world scenario these are points on the ground where a van will go and deliver some stuff, the x and y positions are actually latitude and longitudes. I want to draw on a map a polygon showing the area containing the dots. There are actually different sets of dots where different vans go, so I will be putting lots of these polygons on a map and I want to show the areas covered by each van, but we can focus on the way to do just one van at a time. I don’t want the polygon to be all spikey, I want it to be what you would get if you put a rubber band around the points and it turns out this is called a convex hull.
The locations of the points are held in a mysql database and the latitude and longitude columns are indexed, this means I can do very fast queries that involve sorting or comparing these values. I know there is a computational cost for sorting and comparing things, but I don’t care about it, it is probably O(log n) in terms of complexity and it is fast and easy. I don’t really want to calculate angles at all because that involves doing more trigonometry than I can be bothered to remember.
Start at the most northerly point
select * from points order by lat desc limit 1;
From the points to the west choose the most northern one. — repeat this step until you are on the most western point.
select * from points where lng < ? order by lat desc limit 1;
From the points south of this one, select the most western — repeat until on the most southern point
select * from points where lat < ? order by lng asc limit 1;
From the points to the east of this one, select the most southerly — repeat until on the most eastern point
select * from points where lng > ? order by lat asc limit 1;
From the points to the north of this, select the most eastern point — repeat until back at the most northerly point that you started from.
select * from points where lat > ? order by lng desc limit 1;
This doesn’t necessarily give you a strictly convex hull, but it does give you a shape that water would run off even if rotated 90/180/270 degrees. This is actually good enough for my purposes but you can then do a second pass around the path you have calculated and check for convexness without doing any angles by taking three points at a time and checking to see if the middle point is left or right of the line connecting the first and last point, this can be done with simple maths and no angles with a function somewhat like this:
function convex(p1,p2,p3){ return (p2.lat-p1.lat)*(p3.lng-p1.lng)-(p2.lng-p1.lng)*(p3.lat-p1.lat)
}
If that returns a negative value then discard the middle point from the polygon (I may have that the wrong way round). This test could be done as you go along as part of the first walk around the path.
Here is what it looks like for my data, without doing the second pass for strict convex shapes.
