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

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.