Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Line intersections.

  1. Dec 3, 2005 #1
    I have a series of points on a 2 dimensional plane that form a polygon.
    Somewhere inside the polygon I have another point and an angle that defines a ray. What algorithm would I use to find which interval is first interstected with the ray?
    If the point happens to be outside the polygon then I would want to solve which is the second intersection.

    I can work this out using algebra and geometry but I was hoping that perhaps using matrices or something there may be a more efficient way suitable for computing quickly.

    I have attatched a simple sketch of what I mean. Thanks.

    Attached Files:

    Last edited: Dec 3, 2005
  2. jcsd
  3. Dec 3, 2005 #2
    Is computational speed a factor? Also, is the polygon in question necessarily convex, and is it a large polygon? I'm not aware of any specific algorithm for doing what you ask because line-line intersection can be easily solved in o(1) time, and if you have an array of points in o(n) time. Anyway, answer those questions if I didn't get around to asking this too late (your attachment is still pending)
  4. Dec 3, 2005 #3
    Thanks vsage. The speed is a huge factor, I will be having shapes of all kinds with no limit to the number of vertices, no convex constraints, and it will be possible to have shapes cut out of them [see these examples]. At the moment I was thinking this:

    Code (Text):
    1. For each polygon edge:

    2. If the angle to the endpoints are both less than or both
       greater than theta go back to 1.

    3. Treat the interval as a line and find the intersection and
       the distance.

    4. If the distance is less than the minimum found distance
       keep it.
    This seems to be the fastest way I can think of, is it possible to improve it? I can precompute whether or not the shape is convex or concave and use separate algorithms if there are better alternatives for different kinds.
    Also, if shapes of different topology make it more difficult I can scrap that, it is less important.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook