Calculating intersection of polyline and line

Question

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?

Answer 1

Given that you want to test for intersection against rays with many different starting points and directions, it's worth investigating raytracing-style acceleration structures, such as the bounding volume hierarchy (BVH). In 2D, this would look like a tree of axis-aligned bounding boxes that divide up the space. Each leaf node of this tree would store a reference to a small list of nearby segments of the polyline, as well as a bounding box that contains them. Higher nodes would store a bounding box that contains all their children.

There's a ton of material on BVH construction and traversal out there, so I'd recommend doing a few searches and reading up. It's not too difficult to implement a top-down construction method, by starting with the bounding box of the whole polyline and recursive splitting. Then, to use it for acceleration, when you do a ray query you can find which BVH nodes the ray touches and test only the segments in those nodes for intersections.

However, all that being said, I'd like to propose a different approach to your original problem of working with contour lines. It seems to me that this is a place where Delaunay triangulation can probably be very helpful. It basically constructs a triangle mesh that connects a set of input vertices and edges. For example, here is a contour map I found on the internet:

And now here it is with a constrained Delaunay triangulation, calculating using Jonathan Shewchuk's "Triangle" program:

As you can see, the triangulation gives you a lot of information about neighboring regions in the contour map, so I suspect that you could find a way to get what you want from it somehow. For instance, you could find all the triangles that touch the two contour lines you're interested in, and look at their edges, midpoints, and so on.