Sweep-Line Algorithm for Line Segment Intersection (2/5) | Computational Geometry - Lecture 02
Вставка
- Опубліковано 4 лют 2025
- Computational Geometry
Lecture 02: Sweep-Line Algorithm for Line Segment Intersection
Part II: Sweep-Line Algorithm
Philipp Kindermann
Playlist: • Sweep-Line Algorithm f...
Slides: algo.uni-trier...
Full course: / @philippkindermann
Thank you for the explanation, the visual demonstration and walkthrough was great
Thank you for making this available to the public! Great explanation
Your explanation- Amazing!
Your accent - Even better!
Thanks for the great work. Keep the video's coming!
This is really good. Please also upload further lectures!
Best explanation on UA-cam.
Thanks for sharing the knowledge Professor.
The first time my prof could explain a topic better than the UA-cam
The best explanation out there, thank you so much!
Best explanation found in the topic
Amazingly helpful lesson. I'm trying to compute the visibility polygon of line segments using an angular sweep line algorithm, and your explanation is very easy to understand. Thank you!
Excelent explanation. Can you explain Vatti's algorithm?
Hey, Phillip! Thanks for a cool explanation. Wouldn't it be more appropriate to use a heap data structure in order to keep trask of sweep line motion? It seems that the only operation that we need for this part of the algorithm is actually "get the topmost point" and such an operation is provided by the max binary heap with the same algorithmic complexity as a BST (log(n)) but with less overhead for pointers and stuff. What do you think?
Hey gagra,
great suggestion! The reason we use a BST instead of a heap is a bit hidden: In line 4 of findNewEvent (see the next video, Part III: Algorithmic Details), we have to check whether the intersection point of two neighboring segments already exists in the event queue. This is an operation that we cannot do in O(log n) time on a heap. We could store all points that we already found and then do this test in O(log n) time, but that defeats the advantages of a heap. Also, in the improvement of the space consumption (very last slide, Part V: Running Time) from O(n+k) to O(n), we have to remove points from the queue, which we also cannot do fast enough on a heap.
@@PhilippKindermann I checked out the second video and now i see why you use a BST for a general case, thanks for an explanation. However in my case I am not looking for all intersection, I am looking for the first one (I just need to verify that a set of segements in not self intersecting) so in my case 1) the segments never change order on the sweep line, case when they do they have an intersection and I simply quit the routine 2) I never have to add anything else except for initial points to the event queue for the same reason. This kinda simplifies the task alot from the algorithimc perspecitive and many things that you handle in the general case I can just omit. So in my special case it still looks like the binary heap would work. Another bonus of a binary heap in my scenario is that to construct a heap out on N points you need O(N) operations, while an incremental construction of a BST would require O(N log(N)). And of course despite the fact that a self balancing BST and a heap have the same assimptotic complexity O(log(N)) of the exctact min operation the binary heap has a way smaller constant assosiated with it since you just need to sink a single element after you grab your min element and this is much more simple than a remove operation of a BST that may require a sequence of rotations.
I see you have a whole bunch of videos on computational geometry. That is cool, keep it going man! I will check them out.
@@gagra1234 This is true, if you only want to find any intersection, then you don't need a binary tree. In this case, you could even store all the points in a sorted list / array, since your event queue is static (we only add intersection points to the event queue, but you stop as soon as you find one). Then construction takes O(n log n) time, but you only need constant time for extraction; this should give you even smaller constants.
Thank you for your kind words!
Thank u for this amazing tutorial.
It is a great explanation, thank you!
Which did software you use to do this presentation.?
I used ipe, a vector drawing program with ipe support by the one and only Otfried Cheong: ipe.otfried.org/
@@PhilippKindermann Thanks! I used pipe since about a year, but i didn't have idea that I can make presentations with it!
how can i know one line between two line segment other ?
Great lecture!
I have one question about the algorithm, let's say we were interested in only counting the intersections that are not using an endpoint of a segment, in the example, there is only one such intersection (the first red dot). So, can we use the sweep line method just to detect these intersections, thus the runtime would be O(I).
or does the algorithm only sees the intersections as event points only because it has seen it previously from checking the two segments?
@@102petar Your second thought is correct. To find that intersection point, you first have to process the two segments that intersect in that point. So you still require the O(n log n + I) running time.
I expected the first Data Structure to be a maxHeap, since it will be way easier to get this done through a heap where we just need the maximum intersection point. Great explanation nonetheless
The reason I didn't use a MaxHeap is that deletion cannot be done trivially in logarithmic time. Otherwise a MaxHeap would be easier, that's true.
fantastic
this saved my ass
Dude looks like american, sound like indian.
I meant no insult, I just meant you got all to be a tutor online.
Haha, I'm German though :D