Syntactic Confectionery Delight  
PerlMonks 
Re: Algorithm: point with N distance of a line between two other pointsby Limbic~Region (Chancellor) 
on Nov 03, 2010 at 23:51 UTC ( #869360=note: print w/replies, xml )  Need Help?? 
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 pointslope 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
In Section
Seekers of Perl Wisdom

