0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Hi there Aniket. If I understand your formula correctly, you are suggesting sampling the line every t seconds and running the formula at every point, is that correct? So that if a person travels at 10 m/s for 100m, I would have to run the formula at every 10m along the path and get all the points within the circle's radius 10 times, is that right? If so, how does this account for excluding overlaps so that the same building isn't "seen" multiple times? And does your formula take into account the curvature of the earth? Thanks, Arj. $\endgroup$
    – Arj
    Commented Aug 28, 2018 at 4:56
  • $\begingroup$ Yes, your interpretation is right. In fact, if you are working on a machine that can handle functions (like MATLAB) then you can directly generate an end-function that will provide area covered by the person walking in any arbitrary continuous function of path (maybe straight line, curved line, sinusoid but in 2D only, not the curvature of Earth) between distinct endpoints. For excluding multiple times of the same building you can always remove the duplicate coordinates found in every iteration. I can try to edit this formula to incorporate third dimension (curvature of Earth). $\endgroup$ Commented Aug 28, 2018 at 5:10
  • $\begingroup$ Hi Aniket, thanks for your reply. No need to edit your formula - I understand the premise and have the Haversine formula in SQL and PHP to handle the calculations. I guess I was looking for a formula that didn't use time or distance sampling, and also one that automatically excluded duplicates. However if this is not mathematically possible, then I guess I will go with your approach. Arj $\endgroup$
    – Arj
    Commented Aug 28, 2018 at 5:16
  • $\begingroup$ Yeah I think the solution I provided cannot work in discrete sense because if time steps are not small enough then the actual area is a sequence of circles instead of a rectangle with circular ends. The problem in finding a single equation is that a rectangle in itself is a discontinuous shape, behaves differently in different domains. So adding semicircular ends does no good. So it is hard to find an equation that directly draws the area you require. Please do let me know if you find such an equation. I would love to know it. $\endgroup$ Commented Aug 28, 2018 at 15:19
  • $\begingroup$ Thanks for your reply Aniket. There was definitely such a formula when I was in high school. However it's in a very old text book which I don't have any more. And I can't find it on the web :( $\endgroup$
    – Arj
    Commented Aug 29, 2018 at 10:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .