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: 132
I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
Thread 'Star maps using Blender'
Blender just recently dropped a new version, 4.5(with 5.0 on the horizon), and within it was a new feature for which I immediately thought of a use for. The new feature was a .csv importer for Geometry nodes. Geometry nodes are a method of modelling that uses a node tree to create 3D models which offers more flexibility than straight modeling does. The .csv importer node allows you to bring in a .csv file and use the data in it to control aspects of your model. So for example, if you...
Back
Top