0:02

So now let's look at a basic geometric data processing problem of determining

Â intersections among a set of line segments. So, it's called the orthogonal

Â line segment, segment intersection search where the lines segments or constrained to

Â be either horizontal or vertical. And so, suppose we have a large number of such

Â line segments and what we want to be able to do is to find all places where they

Â intersect. And as we'll see this extends to a practical problem in a number of

Â situations. So, in this case there's four places where these lines intersect. So,

Â how are we going to be able to determine these intersections efficiently? Now, the

Â natural algorithm, or the naive brute-force algorithm, is quadratic in

Â time. So that is, for every line segment, you check whether it intersects with every

Â other line segment. And again, as we know, such an algorithm is not going to be

Â practical, for huge numbers of line segments. So, just, to simplify our code

Â in the slides in it's off, off from the case for geometric data processing. We

Â don't have to worry about degeneracies where lots of things have the same x or y

Â coordinate. And just to simplify the code and to get it the main principles of the

Â algorithms, we're going to assume that all the coordinates that we have are distinct

Â that we've preprocessed in some way to remove the ones that touch without

Â intersecting. So the method that we're going to look at is a so called Sweep Line

Â algorithm and the idea is to think of vertical line that sweeps left to right

Â through the data. In to. Consider it as a every time it hits some line segment as an

Â event where we have to do something. So sweeping from left to right means we

Â consider each x coordinate as an event. So first thing is if we hit a horizontal line

Â segment. Well we're going to hit the left endpoint first, and so what we'll do when

Â we hit the left, endpoint is, insert, the y coordinate of that line into a binary

Â search tree. So, we're going to keep track of y coordinates in a binary search tree.

Â So that's what's happening over in the right there. So now again, sweep from left

Â to right. What's the next smallest x coordinate? In this case it's the line

Â number one there, and we'll remember its y coordinate in a binary search tree. And

Â then two and three. So those that's one kind of event that can happen as we sweep

Â from left to right. Another kind of event is that we hit the right endpoint of a

Â horizontal line segment. In this case we hit the right endpoint of line segment

Â two. So, at that point the right point of a horizontal line segment we just remove

Â it because we've processed that line completely. In this case we didn't find

Â any intersections. So, left endpoint insert the y coordinate into a BST, right

Â endpoint remove that ycoordinate from the BST. So, the BST contains the y

Â coordinates of all the horizontal lines that currently might involve an

Â intersection. And then the third kind of event is what happens when we hit a

Â vertical line segment? Well, in that case all we want, need to do is just do a range

Â search, for the interval of y end points. So, any point that's inside that interval,

Â is going to represent a horizontal line segment that is an intersection. That's

Â the basic idea behind the sweep line algorithm, to find intersections in sets

Â of horizontal and vertical lines. And it's actually a very simple algorithm, and it's

Â very easy to see that the running time is going to be proportional to N log N plus

Â the number of intersections returned. Where there's N horizontal vertical line

Â segments. And it's, and a couple of ways to implement it, one thing is you could

Â sort according to the x coordinates, or you could just put them all on a priority

Â queue. And then, so, so that's going to take N log N for every one of the lines to

Â process them all either N to build the priorit y queue and then log N to take the

Â smallest off each time, or N log N for the sort. And then putting the y coordinates

Â into, into a binary search tree is, again, N log N. And same for deleting. Each point

Â has to be inserted, deleted. It could be as many as N in the tree for each one. So

Â it's a total of N log N. And then the, range search, in the binary tree, for

Â each, each one of the range searches. It might take, log N, it might be as many as

Â N. And then there's, plus the number of points return. So, That's a, quick sketch

Â of the proof of this proposition. And with that 1D range search, implementation, we

Â get an efficient N log N, 2D orthogonal, orthogonal line segment, intersection

Â