0

so I've been working on this problem for a few days. The aim was to produce a radius search of data based on a users current location ( A Lat/Lon ). How ever I want to add some intelligence to the search by calculating B Lat/Lon & B Lat/Lon ( which I can do ) then from the radius search I do remove any matching GPS points within this triangle....

The closest I have mananaged to get to is matching B to C but not the points included up to A...

This is part maths and part MySQL as that is the eventual method I want to use to implement this.

Any thoughts ?

Terran

Main Image

The Final Result

From else where

Q:Why are there radii around B and C if the only radius you want to return results in is A? AThis are simply to show the lat long of each point... I've added an additional diagram to show how this would be used.

Q:What do B and C actually represent (A is current location) A: B and C will be locations worked out ( via maths ) based on the users current location, bearing and speed.

"It's easy to test if a point is in a triangle - think cross products of triangle edge vectors and vectors from triangle corners to test point. Inside points are inside all three sides."

Link - Inside Triangle Calc - http://www.mathworks.com/matlabcentral/fileexchange/22690-inside-triangle/content/inside_triangle.m

Terran Brown
  • 509
  • 10
  • 25
  • Is the distance along the sides of the triangle that the green circle hits fixed? It looks ~2/3 at the moment... and is it always an isoceles / equilateral triangle? – ChrisW Aug 20 '12 at 21:40
  • At this time no.... the radius of the circle is dependant on a user proximity setting and the angle of the tri-angle sides will be dependant on the speed of the user.... I've tried to make the diagram simple for the purpose of the question... IF it needs to be fixed it can be.. – Terran Brown Aug 20 '12 at 21:42
  • Since you are using MySQL, have you tried http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html? It should handle this sort of calculations for you. – Stéphane Aug 20 '12 at 21:46

1 Answers1

2

There are several steps to this process.

Find the points within the bounding box of the circle. This works nicely and efficiently, if slightly sloppily on the longitude dimension, with

   SELECT *
     FROM points p
    WHERE p.lat >= alat-radius
      AND p.lat <= alat+radius
      AND p.lon >= alon-radius
      AND p.lon <= alon+radius

Next, exclude the points inside the triangle. You'll need to write a stored function to do triangle inclusion to handle this.

   SELECT *
     FROM points p
    WHERE p.lat >= alat-radius
      AND p.lat <= alat+radius
      AND p.lon >= alon-radius
      AND p.lon <= alon+radius
      AND NOT Inside_Triangle(p.lat, p.lon, alat, alon, blat, blon, clat, clon)

You can look here for algorithms for doing triangle inclusion. How can I determine whether a 2D Point is within a Polygon?

Finally, exclude the points that are outside the radius.

   SELECT *
     FROM points p
    WHERE p.lat >= alat-radius
      AND p.lat <= alat+radius
      AND p.lon >= alon-radius
      AND p.lon <= alon+radius
      AND NOT Inside_Triangle(p.lat, p.lon, alat, alon, blat, blon, clat, clon)
      AND Haversine(p.lat,p.lon,alat,alon) > radius

Here's an example of the Haversine function. Notice that you have to sort out the units of radius carefully. Why does this MySQL stored function give different results than to doing the calculation in the query?

There you have it. How to get a result set containing the points you want.

Community
  • 1
  • 1
O. Jones
  • 103,626
  • 17
  • 118
  • 172
  • Ollie - I think that is very helpful.... now I understand some of the maths I may use the PHP script which calls the SQL code.... I can pre populate most if not all of the x.lat / x.lon fields. OT I have spent a lot of time on my current query to make sure I only pull what is valid in the radius.... http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL is a really helpful doc on this but there are far better docs out there because when you do a radius calc you have to take in the shape of the earth too. I'll be happy to share if some one opens a new question and lets me know. – Terran Brown Aug 20 '12 at 23:23
  • I'll report back when I've had a chance to play with the above.... Many Thanks All T – Terran Brown Aug 20 '12 at 23:26
  • If you're not a civil engineer, you don't need to worry about the Earth-is-a-sphere approximation. It is plenty close enough for store finder and geocaching applications. It's only if you're dealing with sub-ten-meter or so precision that you need to deal with Earth's distortions. And in that case you probably know, or have a colleague who knows, what to do. You're right to avoid trying to do this in MySQL stored procedures. – O. Jones Aug 21 '12 at 03:11
  • Hi Ollie... had a read at your link and to me it seems its more about collision detection... ill keep looking though. In the mean time I found an matlab example to test a triangle.... link in first post..... I'm going to see what I can do with it. – Terran Brown Aug 21 '12 at 14:16