First time poster so please be gentle! I really should remember this solution from high school maths, but I'm afraid that was a very long time ago :(
I am looking for a formula to determine if a given point lies within the locus of all points equidistant from a line segment marked on a sphere. What I am ultimately trying to do is this:
- I have a MySQL database with two tables: Buildings and People
- Every building and person has a location described in real-world co-ordinates as their lat/lng pair
- Buildings are always in a fixed position: their lat/lng pair never changes
- People can move, and for the sake of simplicity I assume they always move in a straight line from point A to point B (noting that it's not really a straight line, as it must follow the curvature of the earth)
- What I want to determine is for a given journey a person takes (from A to B), assuming their range of vision is 300 metres, what are all the buildings they would see along their route?
At the moment, I can successfully determine all buildings a person can see from one point (i.e., assuming the person is standing still). This is basically similar to determining all points within a circle given a certain radius described on a sphere (Haversine, I believe), and the SQL query looks like this:
SELECT Buildings.lat, Buildings.lng, (6378137 * acos(cos(radians(latPerson)) * cos(radians(latBuilding)) * cos(radians(lngBuilding) - radians(lngPerson)) + sin(radians(latPerson)) * sin(radians(latBuilding))))
AS distance FROM Buildings
HAVING distance < 300;
I could also implement a point-in-polygon algorithm probably using ray casting. So to solve the problem (albeit inefficiently and inelegantly) I could:
- Find the points within a rectangle of "side" edges at A and B, and "top" edges 600 metres apart and perpendicular to the "side" edges, using point-in-polygon (not sure if this will be accuracte given the curvature of the earth, but I could possibly live with that)
- Find the points within the two circles described by points A and B with radii 300 metres (because I think it's easier to find points in circles rather than points in semi-circles)
- Discard any duplicate points found (two buildings can't have exactly the same lat/lng pair)
But there must be a more correct, accurate, efficent and elegant way. I'd be very keen to see a mathematical, formulaic approach to this proble, with extra points for the algorithm written in SQL!
Thanks in advance for your help,
Arj
I think the formula you are looking for is: $$(x-x_m(t))^2 + (y-y_m(t))^2 \leq r^2 $$ where $x_m(t)$ and $y_m(t)$ are functions of x-coordinates and y-coordinates of the man under consideration. In you case it can have the sequence of points you have stored in table. This equation governs the area inside a circle whose center is moving as a function of time. You need to put all the building location coordinates for every new coordinate of man and check which buildings satisfy the inequality.