Bentley Ottman and Line Sweep algorithms in general - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Bentley Ottman and Line Sweep algorithms in general

FlynnnFlynnn Posts: 1Member
Hi! :) I am in need of an algorithm that will tell me all of the intersection points in a given array of lines.

At first, I went googling "Line intersection point". I got lots of algebra, which could have solved, but computers... Not so much. I have no clue how to convert algebra to a computer program. That's question one.

As I went through this I came across a quote: "A naive algorithm would attempt to analyze all lines in an array, and calculate each line's intersection" (Or something like that). That's exactly where I was heading. The quote lead me towards the Bently Ottman algorithm which uses a Line Sweep method. Line seeps themselves confuse me -- I could find nothing actually explaining their inner workings, just that they basically sweep, typically horizontally, and put down any information they find that is of relevance along the way. That deeply troubled me, but, since Line Sweeps are just ideas, not really hard algorithms, I went back to Bently Ottman. I could find nothing on how THAT internally works either, just more of "how you can visualize it". his is where I get really confused.

In order for it to be detecting intersections, shouldn't it be, say, going at infinitesimally small jumps? How could this possibly be efficient. So, okay, maybe it just jumps to where things intersect, and vertices. How can that be possible when it does not know where the intersections are? Okay, maybe it jumps at static lengths. Then, more often than not, it'll jump completely over all the vertices and intersections!

Just now it occurs to me -- Maybe it goes across each vertex, and whenever it comes across more than one at the same time, it calculates the intersection for those and jumps there or to the next vertex. That makes more sense to me. The question is left though, how best to calculate the intersection point?

Thanks for any answers that can be given, Flynn

Sign In or Register to comment.