Plane Sweep: don't understand event intersection

Vote count: 0

I don't quite understand the event intersection in plane sweep algorithm regarding segments. I do the sweep from top to down and not from left to right. In case of two intersecting segments, they are swapped in the status structure T.
1) Why are they swapped?

Now, suppose we have segments s1 and s2 already in T and they are intersecting. As far as I understood, T is sorted after the x component. Let's say the x component of s2 is smaller than s1, so s1 is the right neighbour of s2 in T. We also have segments s3 and s4. They are both below s1 and s2, and s4 is below s3. The x component of s3 is in between s1 and s2 and s4 has the biggest x component.

Imagine it like this in the X-axis for starting point: s2 < s3 < s1 < s4
Imagine it like this in the Y-axis for starting point: s1 > s2 > s3 > s4

Imagine it like this in the X-axis for end point: s1 < s4 < s2 < s3
Imagine it like this in the Y-axis for end point: s3 > s4 > s1 > s2

si x sj denotes the intersection of segment i and segment j. We have two intersections.
s2 x s1 is before starting point s3
s4 x s3 is below the starting point s4
All intersections are before the end points.

Now, if I add a new segment s3 into the structure T, I just look at the x component and add the new segment at the correct place. But I reach first the intersecting point of s1 x s2. Therefore I need to do a swap. Then I read the starting point of s3 and I have to add s3 into T. Originally, the x component of s3 is in between s1 and s2. But I already swapped s1 and s2.
2) Where do I add s3 in T now?

Then I read the segment s4.
3) Where do I add s4 in T now?

It is a lot of text, but I don't know how else to explain it without an actual drawing. I would appreciate some helpful explanations.

asked 44 secs ago

tumbler

Let's block ads! (Why?)

Plane Sweep: don't understand event intersection