Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Algorithm: point with N distance of a line between two other points

by japhy (Canon)
on Nov 03, 2010 at 18:03 UTC ( #869287=perlquestion: print w/ replies, xml ) Need Help??
japhy has asked for the wisdom of the Perl Monks concerning the following question:

I have a world map with world events (like volcanoes, earthquakes, hurricanes, etc.) mapped on it. I also have buildings (like the Empire State Building) mapped on it. I can determine through simple math if an event is within N miles of a building. I've done this in Perl and translated the math to a mysql function, since these calculations are done at the database level.

But now I have a more complex sort of "building" to map. This isn't a building in a single place, it's essentially a path, like for a pipeline. The pipeline is defined by its vertices: every place the pipeline changes direction is a vertex (obviously).

I want to determine now if an event is within N miles of this "pipeline". However, this is more than just checking each individual vertex of the pipeline, because it is possible for the event to be too far from a vertex to register a hit, yet close enough to a line drawn between the two vertices (which is the actual pipeline).

I sort of know the math for this situation... I need to test for a point (X0,Y0) on the line from (X1,Y1) to (X2,Y2) -- that's the pipeline -- that is on the perimeter of a circle of radius R from point (X3,Y3) -- that's the event. But I'm not sure I know how to convert that into lat/lng math for use in mysql. Any pointers?


Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
Nos autem praedicamus Christum crucifixum (1 Cor. 1:23) - The Cross Reference (My Blog)

Comment on Algorithm: point with N distance of a line between two other points
Re: Algorithm: point with N distance of a line between two other points
by BrowserUk (Pope) on Nov 03, 2010 at 18:26 UTC
Re: Algorithm: point with N distance of a line between two other points
by choocroot (Friar) on Nov 03, 2010 at 19:48 UTC

    I think that what you really want is the distance of a point to a segment, and not the distance to a line. Because a line is infinite, and the shortest distance of a point to a line might fall outside your segment.

    In the case below, the distance of the point C to the line AB is CP. But P is outside of your segment, and what you really want is CA and not CP.

    / x (B) / / / x (C) x (A) `. / `. / `x / (P) / /

    So, you must find the coordinate of P (the distance to the line) then check if P is outside of your segment. If it's outside, then you compute CA and CB and take the shortest.

      In fact, I believe that you want ...

      (sort { $a <=> $b } (|CA|, |CB|, |CP|))[1]

      where |...| means "the distance between these points". Of course, because the OP is working with points on a curved surface, he may need to work with great circle distances (and even then he has to allow for the planet not being spherical if he wants to be *really* precise) whereas lots of the solutions you'll find online assume that you're working on a plane. The assumption that the surface is a plane really breaks down once you're talking about distances of more than a few hundred km.

Re: Algorithm: point with N distance of a line between two other points
by Limbic~Region (Chancellor) on Nov 03, 2010 at 23:51 UTC
    japhy,
    As BrowserUk pointed out, the way to find the shortest distance between a point and a line is finding the intersection of a the line that is adjacent to the original line and goes through the point (accomplished by using the inverse slope in the point-slope formula). As choocroot pointed out, you are really dealing with line segments, not points.

    The approach laid out by choocroot requires checking each segment as if it were a line and then determining if it is outside the segment one by one. I am too tired to be sure, but I believe this can be done a bit more efficiently. First iterate over the vertices of the pipe checking the distance to your event point. If the distance is within the acceptable limit return true and you are done. If the answer is no, pay attention to the vertex that is closest to the point (low water mark algorithm). When you are done, only 2 segments need to be tested (the ones that meet at that vertex).

    If you have sample data to play with, I would be happy to verify it works and if you had said you were using Pg - I would have written the plperl stored procedure for you too :-)

    Update: My original idea before posting was to create a circle around the event point using a radius of your acceptable distance and then determining if any of the segments intersected the circle. Unfortunately, the only formula I was aware of worked on lines and not segments. Doing a bit more research, I found this which implies it is possible to answer the question by solving a quadratic equation and testing the values of the two solutions. I don't know if it would be faster than the approach I outlined above or not.

    Cheers - L~R

      Yes, LR, my initial idea had been to solve a quadratic equation and test the values of the two solutions. But I've found that Math::Geometry::Planar's DistanceToSegment() function works well with cartesian coordinates.

      I'm facing two problems, though: 1) I'm starting with lat/long coordinates, not cartesian coordinates; and 2) I'd like the algorithm to run in a mysql query. I already have a GEO_DISTANCE(lat1,lng1,lat2,lng2) function in mysql, and I can reproduce DistanceToSegment() in mysql, but I'm not confident that DistanceToSegment() works appropriately with lat/long coordinates. Any ideas here?


      Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
      Nos autem praedicamus Christum crucifixum (1 Cor. 1:23) - The Cross Reference (My Blog)
        japhy,
        The shortest distance between two points on a sphere (forget that Earth is squished a bit) is the arc of the great circle passing between those two points so you may have reason for concern. You should read this and this (Cross-track distance). You may find that treating the surface of the sphere as a flat plane acceptable if your talking about a small enough area - otherwise, you need non-planar math.

        Regarding your statement about MySQL query - I assume have no idea what built-in trig functions are available and I don't envy re-implementing them from scratch. If this were Pg, you could just use plperl and use the module that did what you wanted :-)

        Cheers - L~R

Re: Algorithm: point with N distance of a line between two other points
by dHarry (Abbot) on Nov 04, 2010 at 10:38 UTC

    There is tons off stuff around to do this for you. See for example opensource GIS. At work we used database extensions to prototype a "map based search" functionality. A user can look for features on a body, e.g. a certain crater on Mars. Another application is to draw a rectangle on a map and get all relevant measurements back. Because the extensions support different coordinate systems, projections etc. You can solve most geometry problems relatively easy. Are you already using some mySQL extension? The distance between two points sounds trivial to me. Like Limbic~Region already said if the distance is small, an approximation is good enough, i.e. use a straight line instead of an arc. In fact in my experience this is sufficient inmost cases.

    Cheers

    Harry

      > Like Limbic~Region already said if the distance is small, an approximation is good enough, i.e. use a straight line instead of an arc.

      IMHO one can choose a spherical projection around the point in question which keeps distances¹ fix, no matter how big the region is.

      Shouldn't be too difficult to find corresponding techniques in spherical geometry.

      Cheers Rolf

      1) maybe its even better to choose gnomonic projection, where "great circles are mapped to straight lines" as long as bigger distances have bigger projections.

      UPDATE: ah indeed "Thus the shortest route between two locations in reality corresponds to that on the map.". Of course the real distance on the sphere still has to be calculated after back projecting the "nearest" point.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://869287]
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (6)
As of 2014-09-20 16:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (160 votes), past polls