How does the sweep line algorithm check for intersection using vector cross product?

Question

I am trying my best to understand the sweep-line algorithm to find line intersections.

I have understood most of the intuition except how it is calculating the intersection between 2 line segments using cross product.

I am providing the code for that below, please ask me any doubts related to the code, so that I can explain it to those people who are not familiar with programming.

Full code here.

public boolean intersect(Line other) {
            // out.println(turn(p1, p2, other.p1) + turn(p1, p2, other.p2));
            // out.println(turn(other.p1, other.p2, p1) + turn(other.p1, other.p2, p2));
            return intersect1d(p1.x, p2.x, other.p1.x, other.p2.x)
                    && intersect1d(p1.y, p2.y, other.p1.y, other.p2.y)
                    && turn(p1, p2, other.p1) * turn(p1, p2, other.p2) <= 0
                    && turn(other.p1, other.p2, p1) * turn(other.p1, other.p2, p2) <= 0;
        }


public boolean intersect1d(double l1, double r1, double l2, double r2) {
        if (l1 > r1) {
            double temp = l1;
            l1 = r1;
            r1 = temp;
        }
        if (l2 > r2) {
            double temp = l2;
            l2 = r2;
            r2 = temp;
        }
        return Math.max(l1, l2) <= Math.min(r1, r2) + 1e-12;
    }

  public int turn(Vector p1, Vector p2, Vector p3) {
        double c = cross(p2.x-p1.x, p2.y-p1.y, p3.x-p2.x, p3.y-p2.y);
        if (c < -1e-12) {
            return -1;
        } else if (c > 1e-12) {
            return 1;
        } else {
            return 0;
        }
    }

public double cross(double x1, double y1, double x2, double y2) {
        return x1 * y2 - y1 * x2;
    }

Comments about the code:

• The function intersect(Line) is called when evaluating whether the present line is intersecting with another line segment which is provided.
• intersect in turn calls the functions intersect1d() and turn() each 2 times respectively. intersect1d takes both the starting and ending x-axis and y-axis coordinates for both lines in 2 separate function calls.
• turn() is called next. I have no idea what turn() is doing.

Questions about the code:

• What is cross product of 2 vectors in ${\rm I\!R^2}$ ?

What does that even mean ? Cross Product is supposed to be defined only for vectors in ${\rm I\!R^3}$ ?

Post like this say this is a mathematical hack. Well if it works why is it a hack ? And what exactly is happening with a cross product in 2D ? And why is it relevant here ?

• How does the cross product compute the area of a parallelogram ?

This post mentions that the cross product of 2 vectors calculate the area of the parallelogram. How are we getting a parallelogram and how is the are being calculated by the cross product ?

• What is intersect1d() actually doing ?

From the looks of it, it is checking that the x coordinates of the first line are less than the x coordinates of the second line. Same for y coordinates.

• Please explain what turn() is doing ?

I have no clue.

Other details:

I have gone through other SO posts like this.

I can almost understand how they are deriving the parametric equations of the lines from the vectors, but I simply have no clue how they are using the cross product to check for co-linearity and intersections.

Namely, I cannot understand these conditions from the SO answer:

Now there are four cases:

1. If r × s = 0 and (q − p) × r = 0, then the two lines are colinear.

In this case, express the endpoints of the second segment (q and q + s) in terms of the equation of the first line segment (p + t r):

t0 = (q − p) · r / (r · r)

t1 = (q + s − p) · r / (r · r) = t0 + s · r / (r · r)

If the interval between t0 and t1 intersects the interval [0, 1] then the line segments are collinear and overlapping; otherwise they are collinear and disjoint.

Note that if s and r point in opposite directions, then s · r < 0 and so the interval to be checked is [t1, t0] rather than [t0, t1].

2. If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting.
3. If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s.
4. Otherwise, the two line segments are not parallel but do not intersect.

Note: As you may have guessed I am a novice to linear algebra and vectors, so if you do chose to help me I would request you to write "noob" friendly answers. This will stop me from wasting your time with a ton of follow up questions.

Thanks.

Answer 1

• What is cross product of 2 vectors in ${\rm I\!R^2}$ ?

If you compute the crossproduct of 2 vectors on the $xy$ plane you get a vector along the $z$ axis. In 2D the crossproduct is defined as the (scalar) $z$ value of that vector.

Moreover the value is positive is the angle goes one way and negative if it goes the other way (which exact way depends on the handedness you picked for your 3D space). That way you can test whether a line segment crosses another line.

• How does the cross product compute the area of a parallelogram ?

The value of the crossproduct ends up as $|a|*|b|*\sin(\theta)$ where theta is the angle between the vectors. If you take $a$ as base then $|b|*sin(\theta)$ is the height of the parallelogram.

• What is intersect1d() actually doing ?

It checks whether there is an overlap between the segments on a 1D line. Doing it on x and y mean the code does an axis aligned bounding box collision test as an early out.

• Please explain what turn() is doing ?

It maps the value of the crossproduct to a direction of turn using the sign as I explained above. But values near 0 are mapped to no turn (for accuracy reasons).