JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Line Sweep Algorithms Great article!
 Great article! | Reply I really enjoyed reading this! Excellent job, bmerry!
 Re: Great article! (response to post by DmitryKorolev) | Reply I also really enjoyed reading this!However, I didn't quite understand the following and I think it is a very important point:"In this case, the three types of events are: start of a horizontal line, end of a horizontal line, and a vertical line. As the sweep line moves, we'll keep an active set of horizontal lines cut by the sweep line, sorted by Y value (the red lines in the figure)."So how exactly do you move the sweep line? I don't see any way of moving it continuously. If you move it in discrete steps then you might accidently skip events. If you make the discrete steps too small then the sweep will take too long. What am I missing here?
 Re: Great article! (response to post by dimkadimon) | Reply I believe you sweep it discretely, by only examining the Xs that events exist on - O(n) in total, but you will never miss any events.
 Re: Great article! (response to post by dimkadimon) | Reply the point is data is sorted .... And, of course you move at discrete points..
 Re: Great article! (response to post by vinaysingh) | Reply Precisely. You make an array of all the events and sort it by X. A typical event structure will contain the X value, the type of the event and the index of the line/rectangle/whatever that is connected with the event.
 Re: Great article! (response to post by bmerry) | Reply if you have added some psuedo-codes, that would have been great :)I mean some code for interval trees etc.
 Re: Great article! (response to post by vinaysingh) | Reply http://www.hsin.hr/coci/The last problem of the last contest actually requires sweep line. If you look at the solution, you can find C++ and pascal code.Great article! I wish you write more articles like this =)
 Re: Great article! (response to post by bmerry) | Reply I also think that adding some pseudo- or real code would have been very helpful in understanding of ideas mentioned in article. When these ideas are written only in plain words it's often very hard to catch its essence...
 Re: Great article! (response to post by DmitryKorolev) | Reply I concur. This was an excellent article.
 Forums Tutorial Discussions Line Sweep Algorithms Great article! Previous Thread  |  Next Thread