Segments intersection#839

Segments intersection (Editorial)

The bounding rectangle of a geometric figure is the smallest rectangle with sides parallel to the coordinate axes that completely contains the given figure.

In simpler terms, if we want to "fit" the figure into a rectangle so that all its points lie inside it, the bounding rectangle will have the minimum possible size.

Consider a segment with endpoints at $(x_{1}, y_{1})$ (x_1, y_1) and $(x_{2}, y_{2})$ (x_2, y_2). To find its bounding rectangle:

Determine the lower-left corner of the rectangle:

x_{1}^{'} = min (x_{1}, x_{2}), y_{1}^{'} = min (y_{1}, y_{2})

x_1' = min(x_1, x_2), y_1' = min(y_1, y_2)

Determine the upper-right corner of the rectangle:

x_{2}^{'} = ma x (x_{1}, x_{2}), y_{2}^{'} = ma x (y_{1}, y_{2})

x_2' = max(x_1, x_2), y_2' = max(y_1, y_2)

Thus, the bounding rectangle is the rectangle with corners $(x_{1}^{'}, y_{1}^{'})$ (x_1', y_1') and $(x_{2}^{'}, y_{2}^{'})$ (x_2', y_2') that contains our segment.

Lemma. Suppose two segments $(x_{1}, x_{2})$ (x_1, x_2) and $(x_{3}, x_{4})$ (x_3, x_4) are given on a line, where $x_{1} < x_{2}$ x_1 < x_2 and $x_{3} < x_{4}$ x_3 < x_4. The segments do not intersect if and only if either the first segment lies entirely to the left of the second, or the second lies entirely to the left of the first.

Lemma. Suppose two rectangles $(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2) and $(x_{3}, y_{3}) - (x_{4}, y_{4})$ (x_3, y_3) - (x_4, y_4) are given in the plane, where $x_{1} < x_{2}, y_{1} < y_{2}$ x_1 < x_2, y_1 < y_2 and $x_{3} < x_{4}, y_{3} < y_{4}$ x_3 < x_4, y_3 < y_4. The rectangles do not intersect if and only if either the segments $(x_{1}, x_{2})$ (x_1, x_2) and $(x_{3}, x_{4})$ (x_3, x_4) do not intersect, or the segments $(y_{1}, y_{2})$ (y_1, y_2) and $(y_{3}, y_{4})$ (y_3, y_4) do not intersect.

Intersection criterion for two segments

Two segments $A B$ and $C D$ intersect if and only if the following three conditions hold:

1. 1. Their bounding rectangles intersect.

2. Points $C$ and $D$ lie on different sides of the line $A B$ , or at least one of the points $C$ or $D$ lies on the line $A B$ . This means that

[A B \times A C] \cdot [A B \times A D] \leq 0

[AB \times AC] \cdot [AB \times AD] \le 0

3. Points $A$ and $B$ lie on different sides of the line $C D$ , or at least one of the points $A$ or $B$ lies on the line $C D$ . This means that

[C D \times C A] \cdot [C D \times C B] \leq 0

[CD \times CA] \cdot [CD \times CB] \le 0

Below are various cases of the relative positions of two segments and the corresponding values of the cross products.

In the next example, each segment intersects the line containing the other segment. However, their bounding rectangles do not intersect.

Example

In the first example, the segments intersect. In the second example, they do not.

Algorithm implementation

Since the coordinates of the segment endpoints are integers, we'll use only the integer type long long for calculations. Later, we'll need a function sgn that determines the sign of a number $n$ .

int sgn(long long n)
{
  return (n > 0) - (n < 0);
}

The function RectanglesIntersects takes as arguments the coordinates of the bounding rectangles for segments $A B$ and $C D$ . It returns $1$ , if the rectangles $(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2) and $(x_{3}, y_{3}) - (x_{4}, y_{4})$ (x_3, y_3) - (x_4, y_4) intersect, and $0$ otherwise.

int RectanglesIntersect(long long x1, long long y1, 
                        long long x2, long long y2,
                        long long x3, long long y3, 
                        long long x4, long long y4)
{
  if (sgn(x3 - x2) * sgn(x4 - x1) > 0) return 0;
  if (sgn(y3 - y2) * sgn(y4 - y1) > 0) return 0;
  return 1;
}

C++

The function cross computes the cross product of two vectors $(A_{x}, A_{y})$ (A_x, A_y) and $(B_{x}, B_{y})$ (B_x, B_y).

long long cross(long long Ax, long long Ay, 
                long long Bx, long long By)
{
  return Ax * By - Ay * Bx;
}

The function intersect checks whether the segments $A B$ and $C D$ intersect.

int segmentsIntersect(long long x1, long long y1, 
                      long long x2, long long y2,
                      long long x3, long long y3,
                      long long x4, long long y4)
{

Check the intersection of the bounding rectangles. If they do not intersect, return $0$ .

  if (!RectanglesIntersect(
       min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2),
       min(x3, x4), min(y3, y4), max(x3, x4), max(y3, y4))
     ) return 0;

Construct the vectors $A B, A C, A D$ AB, AC, AD.

  long long ABx = x2 - x1, ABy = y2 - y1;
  long long ACx = x3 - x1, ACy = y3 - y1;
  long long ADx = x4 - x1, ADy = y4 - y1;

Construct the vectors $C D, C A, C B$ CD, CA, CB.

  long long CDx = x4 - x3, CDy = y4 - y3;
  long long CAx = x1 - x3, CAy = y1 - y3;
  long long CBx = x2 - x3, CBy = y2 - y3;

Compute the cross products.

  long long ABxAC = cross(ABx, ABy, ACx, ACy); // AB x AC
  long long ABxAD = cross(ABx, ABy, ADx, ADy); // AB x AD
  long long CDxCA = cross(CDx, CDy, CAx, CAy); // CD x CA
  long long CDxCB = cross(CDx, CDy, CBx, CBy); // CD x CB

Check points $2$ and $3$ of the segment intersection criterion. If they are not satisfied, return $0$ . To avoid overflow, the comparison with zero should be done not on the product of the numbers themselves, but on the product of their signs.

  if (sgn(ABxAC) * sgn(ABxAD) > 0) return 0;
  if (sgn(CDxCA) * sgn(CDxCB) > 0) return 0;
  return 1; // Segments intersect
}

The main part of the program. Read the input data.

scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
scanf("%lld %lld %lld %lld",&x3,&y3,&x4,&y4);

Check the intersection of the segments.

if (segmentsIntersect(x1, y1, x2, y2, x3, y3, x4, y4))
  puts("Yes");
else
  puts("No");