Fast algorithm for polygon/line intersects

[Joppy]

If we define our polygons as a collection of lines, then each polygon has slopes $\vec{m}$ and y-intercepts $\vec{c}$. For a single line in the plane $y = ax + b$ amounts to finding $x = \dfrac{b - \vec{c}}{\vec{m} - a}$, which is fine. But then we need to sift through the solution vector $x$ and remove any points not on the polygon. This is a trivial operation but costly when the number of polygons is large. What is a faster way to do this?

 

[I like Serena]

If we define our polygons as a collection of lines, then each polygon has slopes $\vec{m}$ and y-intercepts $\vec{c}$. For a single line in the plane $y = ax + b$ amounts to finding $x = \dfrac{b - \vec{c}}{\vec{m} - a}$, which is fine. But then we need to sift through the solution vector $x$ and remove any points not on the polygon. This is a trivial operation but costly when the number of polygons is large. What is a faster way to do this?

Hey Joppy,

Here's an article that outlines algorithms for polygon intersections.

A classical approach is a so called sweep-line algorithm.
We sort the edges on the highest y-coordinate, and we sweep a horizontal line through them from top to bottom.
The sweep iterates through new edges coming in range, and through intersections of the edges on the corresponding active list.

Another unmentioned approach is to divide into sub problems.
That is, if 2 polygons have a distance to each other that is greater than their size, they won't have intersections.

 

[Joppy]

Hey Joppy,

Here's an article that outlines algorithms for polygon intersections.

A classical approach is a so called sweep-line algorithm.
We sort the edges on the highest y-coordinate, and we sweep a horizontal line through them from top to bottom.
The sweep iterates through new edges coming in range, and through intersections of the edges on the corresponding active list.

Another unmentioned approach is to divide into sub problems.
That is, if 2 polygons have a distance to each other that is greater than their size, they won't have intersections.

Thanks! I think google is broken, I searched for some time and didn't find anything even remotely on these lines (pun intended).

edit: Hmm wait a minute.. Maybe I'm not understanding the routine highlighted there, but is this method just finding all the roots, or is it finding only those roots lying on say a closed polygon?

 

[I like Serena]

Thanks! I think google is broken, I searched for some time and didn't find anything even remotely on these lines (pun intended).

edit: Hmm wait a minute.. Maybe I'm not understanding the routine highlighted there, but is this method just finding all the roots, or is it finding only those roots lying on say a closed polygon?

The Bentley-Ottmann Algorithm finds all intersections of an arbitrary set of line segments.
View attachment 7992
In this example the sweep is with a vertical line from left to right over arbitrary line segments.