# Calculating intersection of polyline and line

I have a convoluted polyline composed of vertices and straight segments and a separate point that is independent of the polyline. I am trying draw a straight new line from the point at a given angle and determine if the new line intersects the polyline and get the location of that intersection. If there are multiple intersections I want the location of the closest intersection.

I'm currently doing this by drawing a line an arbitrary (long) distance from the point at the desired angle and then intersecting it with the polyline using a python gis toolkit (shapely). If there are multiple intersections I sort them by distance and select the closest one.

This method works but is somewhat clumsy. Is there a more efficient method of calculating the closest intersection? It almost seems like ray tracing (of which I have minimal knowledge) but I can't find much online that applies to my case.

The other method that I contemplated was to iterate over every line segment in the polyline and use y = mx+b to see if the segment intersects the new line from the point. The polyline is potentially quite long with many segments, but I've also seen some sorting tricks online to make this method more efficient. Is there a method that I'm missing?

• Will you want to repeatedly test many different angles of ray from the same starting point, against the same polyline? Or will the starting point and angle both be variable? (What I'm getting at is it's probably possible to build an acceleration structure that would speed up these queries, but which structure is best will depend on how it's going to be used.) Mar 11, 2016 at 21:45
• Nathan, I will be testing many from a single starting point. And then test multiple angles from another starting point and another and etc. I actually have segments of two contour lines and am trying to draw a line in between the two of them. My current strategy is to draw a series of lines at semi-regular intervals between the two lines. I can then create a polyline between all the short crossing lines. I'm currently working on how to create the lines that cross between the two contours, which is surprisingly difficult due to how curvy and convoluted some of them are. Mar 12, 2016 at 3:41
• So your triong to find the closest point on the curve? Mar 12, 2016 at 15:51
• I tested out closest point on the curve and while it can work there are too many cases where it doesn't work at all or works poorly. The approach I'm currently considering is based on angles. When a line is drawn between two other lines 4 angles are created. I'm thinking the "best" line is created when all 4 angles are as close to 90 degrees as possible. So at a given position I intend to draw every possible line (intervals of 5 or 10 degrees or similar) and select the best line based on a ranking of the 4 angles. Mar 12, 2016 at 16:51
• Would you be interested in solutions that use precomputed acceleration structures? Bsp trees and possibly vornoi diagrams seem likely useful (: Mar 12, 2016 at 17:26