MHB Fast algorithm for polygon/line intersects

  • Thread starter Thread starter Joppy
  • Start date Start date
  • Tags Tags
    Algorithm
AI Thread Summary
Defining polygons as collections of lines involves determining slopes and y-intercepts for efficient intersection calculations. The challenge arises when needing to filter solution vectors to retain only points on the polygon, which can be computationally expensive with numerous polygons. A suggested solution is the sweep-line algorithm, where edges are sorted by their highest y-coordinate, and a horizontal line sweeps through them to identify intersections. Another approach is to divide the problem into subproblems, eliminating pairs of polygons that are too far apart to intersect. The Bentley-Ottmann Algorithm is also mentioned as an effective method for finding intersections among line segments. There is some confusion about whether the discussed methods find all roots or only those within closed polygons.
Joppy
MHB
Messages
282
Reaction score
22
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?
 
Technology news on Phys.org
Joppy said:
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.
 
I like Serena said:
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?
 
Last edited:
Joppy said:
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.
 

Attachments

  • 1348015188_9174.png
    1348015188_9174.png
    10.2 KB · Views: 131
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Thread 'Project Documentation'
Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...
Back
Top