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

[Limbic~Region]

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.

[japhy]

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?

[Limbic~Region]

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 :-)