Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

comment on

( #3333=superdoc: 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 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


In reply to Re: Algorithm: point with N distance of a line between two other points by Limbic~Region
in thread Algorithm: point with N distance of a line between two other points by japhy

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others surveying the Monastery: (4)
    As of 2020-07-07 19:37 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      No recent polls found

      Notices?