What I described is the Bentley - Ottoman line sweep. The first step of Bentely-Ottoman is sorting the lines.
A little bit of explanation. After radially sorting the points, you have all the points in an single array. Now you start with any start point of a chord and go say clockwise, if you get another start point it means there is an intersection and you increase the value of 'tot'. The variable 'c' stores how many chords are currently overlapping. So if 2 chords are overlapping at a point and you get a start point, you add 2 intersections. You decrease 'c' when you reach an end point of a chord. -Dhyanesh On 4/24/06, Mayur <[EMAIL PROTECTED]> wrote: > It's a radial plane sweep. However, Dhyanesh, why do we need to deal with > radial sorting. I think the simple Bentley-Ottman line-sweep should do the > trick. > (Pramod) This algorithm is used to determine pairwise segment intersections > in the plane in O(nlogn) time. > mayur > > > > On 4/24/06, pramod <[EMAIL PROTECTED]> wrote: > > > > I don't get this, can you explain it? > > > > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
