JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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.
RSS