How do I calculate and use a Morton (z-index) value to index geodata with PHP/MySQL?

Question

I have a MySQL table of records, each with a lat/lng coordinate. Searches are conducted on this data based on a center point and a radius (any records within the radius is returned). I'm using the spherical law of cosines to calculate the distance within my query. My problem is that indexing the geodata is horribly inefficient (lat/lng values are stored as floats). Using MySQL's spatial extensions is not an option. With datasets around 100k in size the query takes an unreasonable amount of time to execute.

I've done some research and it seems like using a z-index i.e. Morton number could help. I could calculate the Morton number for each record on insertion and then calculate a high/low Morton value for a bounding box based on the Earth's radius/center point/given search radius.

I only know enough about this stuff to build my app so I'm not entirely sure if this would work, and I also don't know how I can compute the Morton number in PHP. Would this be a bitwise operation?

Answer 1

If your radius is small compared to the size of the Earth, then you can probably get by with simple 2D Pythagorus rather than expensive 3D spherical geometry. This is probably less true the closer you get to the poles, so I hope you're not mapping penguins or polar bears!

Next, think about the bounding boxes for your problem. You know they must be within +/- $radius of the search point. Convert the search radius to degrees and find all records where lat/lon is within the box defined by the search center +/- $radiusindegrees.

If you do that search first and come up with a list of possible matches then you have only to filter out the corners of your search box from the resulting data set. If you get back the lat/lon of the matching points you can calculate the distance in PHP and avoid having to calculate it for all points in the table. Did that make sense?

use the database to find everything that fits within a square bounding box and then use PHP to filter those points that are outside of the desired radius.