<p>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 <a href="https://en.wikipedia.org/wiki/Bounding_volume_hierarchy" rel="nofollow noreferrer">bounding volume hierarchy (BVH)</a>. 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.</p>

<p>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.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Delaunay_triangulation" rel="nofollow noreferrer">Delaunay triangulation</a> 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:</p>

<p><a href="https://i.sstatic.net/nEET2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nEET2.png" alt="enter image description here"></a></p>

<p>And now here it is with a constrained Delaunay triangulation, calculating using <a href="https://www.cs.cmu.edu/~quake/triangle.html" rel="nofollow noreferrer">Jonathan Shewchuk's "Triangle" program</a>:</p>

<p><a href="https://i.sstatic.net/EElJb.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/EElJb.jpg" alt="enter image description here"></a></p>

<p>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.</p>

CC BY-SA 3.0
2016-03-14T17:05:09.320Z
Thank you for the suggestions Nathan, I'll look into BVH. Delaunay triangulation could be useful, but I'm seeing potential issues in the example you posted. I'm having the greatest issues where one contour is significantly longer than the other. On the ENE ridge in the image the triangles are spanning the same contour, which is the type of location that I really need the lines to span both contours to interpolate a smooth curve. I may have to go with a ray tracing type approach.
Mike Bannister
CC BY-SA 3.0
2016-03-14T21:17:01.287Z
@MikeBannister, yes, there are places where triangles span the same contour, but you could detect those and filter them out, and only look at triangles that span two adjacent contours.
Nathan Reed
CC BY-SA 3.0
2016-03-13T08:09:05.523Z
2016-03-13T08:09:05.523Z
Nathan Reed
<p>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. </p>

<p>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. </p>

<p>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. </p>

<p>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?</p>

CC BY-SA 3.0
2016-03-11T21:45:17.817Z
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.)
Nathan Reed
CC BY-SA 3.0
2016-03-12T03:41:19.340Z
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.
Mike Bannister
CC BY-SA 3.0
2016-03-12T15:51:57.763Z
So your triong to find the closest point on the curve?
joojaa
CC BY-SA 3.0
2016-03-12T16:51:03.637Z
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.
Mike Bannister
CC BY-SA 3.0
2016-03-12T17:26:06.243Z
Would you be interested in solutions that use precomputed acceleration structures? Bsp trees and possibly vornoi diagrams seem likely useful (:
Alan Wolfe
<geometry><2d>
Calculating intersection of polyline and line
Mike Bannister
# Calculating intersection of polyline and line

(Asked by: username_0 on 2016-03-11)

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?

**Tags:** geometry, 2d

> **Comments:**
> **username_1**: 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.)  
> **username_0**: username_1, 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.  
> **username_2**: So your triong to find the closest point on the curve?  
> **username_0**: 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.  
> **username_3**: Would you be interested in solutions that use precomputed acceleration structures? Bsp trees and possibly vornoi diagrams seem likely useful (:  

---

## 1 answers

### Answer by username_1 on 2016-03-13. Score: 3

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)](https://en.wikipedia.org/wiki/Bounding_volume_hierarchy). 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](https://en.wikipedia.org/wiki/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:

[![enter image description here](https://i.sstatic.net/nEET2.png)](https://i.sstatic.net/nEET2.png)

And now here it is with a constrained Delaunay triangulation, calculating using [Jonathan Shewchuk's "Triangle" program](https://www.cs.cmu.edu/~quake/triangle.html):

[![enter image description here](https://i.sstatic.net/EElJb.jpg)](https://i.sstatic.net/EElJb.jpg)

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.

> **Comments:**
> **username_0**: Thank you for the suggestions username_1, I'll look into BVH. Delaunay triangulation could be useful, but I'm seeing potential issues in the example you posted. I'm having the greatest issues where one contour is significantly longer than the other. On the ENE ridge in the image the triangles are spanning the same contour, which is the type of location that I really need the lines to span both contours to interpolate a smooth curve. I may have to go with a ray tracing type approach.  
> **username_1**: @username_0, yes, there are places where triangles span the same contour, but you could detect those and filter them out, and only look at triangles that span two adjacent contours.  

---

