Find dive sites within specified distance of each other

3rd party extensions (phpDivingLog, dive computer downloader,...)
Post Reply
lloyd_borrett
Posts: 228
Joined: Sun Jun 11, 2006 09:24
Location: Frankston South, Victoria, Australia
Contact:

Find dive sites within specified distance of each other

Post by lloyd_borrett »

G'day,

This one is a little bit off topic, but I'm hoping someone out there could help.

I came across a MySQL function at http://forge.mysql.com/tools/tool.php?id=222 to calculate/measure the distance between two points using Vincenty Distance WGS-84 algorithm.

This got me to thinking that I have a few MySQL databases, including my phpDivingLog one, with WGS-84 datum based coordinates stored in them. It would be nice to be able to query the database to find any points within 'x' metres of each other. This would make it easier to locate possible duplicate points.

So the query would have to get each point, then calculate the distance from it to every other point, and select those less than or equal to the specified distance, and then do the same for every other point.

Would anyone out there be able to construct a MySQL query to achieve this for the Diving Log MySQL table based on the above distance function?

Then we'd be able to use phpMyAdmin to run the query and learn more about the points stored.

Best Regards, Lloyd Borrett.

rene
Posts: 65
Joined: Sun Sep 12, 2010 19:07
Location: France

Re: Find dive sites within specified distance of each other

Post by rene »

Hello Lloyd,

Do you mean you want a 'find the (nearly) duplicates' ? Or just find the closest sites to a given site ?

I certainly can do something with my program, but not in php nor mysql... I am definitively not a fan of web development :/

Did you tried the MySql function in a query ? You also need to write or find a function to convert from « DD°MM'ss.sss" L » to radians since the coords are stored in plain text.

BTW, there is a portable apache/php/mysql distro: http://www.chsoftware.net/en/mowes/mowe ... /mowes.htm. It works pretty well.

rené

lloyd_borrett
Posts: 228
Joined: Sun Jun 11, 2006 09:24
Location: Frankston South, Victoria, Australia
Contact:

Re: Find dive sites within specified distance of each other

Post by lloyd_borrett »

G'day Rene,

Well the query I'm after would let you do both of those things. Apart from the sites in Diving Log, I also have a lot of waypoints for dive sites in other databases for my GPS unit. People keep giving them to me, and I find some on the web. But it's always hard to tell if the waypoints are the same dive spot you already have, sometimes just with a different name, or with just slighty different coordinates.

Diving Log stores the lat and longs as dd.ddddd, so no conversion should be necessary.

I'm already using Mowes disto for my php/mysql/appache disto on Windows for phpDivingLog development.

Best Regards, Lloyd Borrett.

lloyd_borrett
Posts: 228
Joined: Sun Jun 11, 2006 09:24
Location: Frankston South, Victoria, Australia
Contact:

Re: Find dive sites within specified distance of each other

Post by lloyd_borrett »

To convert from ddd mm ss.sss to dd.dddd

CREATE FUNCTION `convert_from_dms`
(degrees INT, minutes int, seconds int)
RETURNS double DETERMINISTIC
BEGIN
RETURN degrees + (minutes/60) + (seconds/3600);
END $$

rene
Posts: 65
Joined: Sun Sep 12, 2010 19:07
Location: France

Re: Find dive sites within specified distance of each other

Post by rene »

More precisely, Diving Log stores lat/lon in a text field « DDD°MM'SS.SSS" d » but exports them in decimal degrees. You are lucky :)

The trivial algorithm will be in O(n²) (for each site, look for all the other sites...) that is not rather optimized for a great number of sites. Look for the 'Nearest neighbor search'... It's definitively not a trivial problem.

The probably simpliest algorithm is to perform a sort on latitude then longitude and compute the distance of two consecutive points (maybe a second query ordered by lon then lat would be useful). Unwritable in sql... you need to fetch all records returned by the query and do some calculation with them.


(Lloyd, what's your pronostic for NZ-Australia ? ;-) )

lloyd_borrett
Posts: 228
Joined: Sun Jun 11, 2006 09:24
Location: Frankston South, Victoria, Australia
Contact:

Re: Find dive sites within specified distance of each other

Post by lloyd_borrett »

rene wrote:(Lloyd, what's your pronostic for NZ-Australia ? ;-) )
I've only ever lived in states of Australia where Australian Rules Football is the totally dominant of our four football codes here -- AFL, soccer, rugby league and rugby. And I don't even follow the AFL. So when it comes to rugby, which would be the least followed football code in Australia, it's a case of who cares. :D

I'm well aware that the New Zealander's see the Rugby World Cup as more important than the Olympics and the Soccer World Cup, but here in Australia it's hard to find the Rugby World Cup games on the TV even if you wanted to look at them.

Post Reply