C++ and STL implementation code example to determine the position relationship between two line segments in a plane

concept

The determination of the position relationship between two line segments in a plane has been widely used in many fields, such as games, CAD, graphics processing, etc., and the solution of the intersection point of two line segments is an important loop in this algorithm. This paper will try to use popular language to describe a mainstream and high performance algorithm in detail.

The cross product, also known as the cross product, is a concept in vector algebra (analytic geometry). The cross product of two 2-dimensional vectors v1(x1,y1) and v2(x2,y2), v1×v2= x1y2-y1x2. If the rotation from v1 to v2 is clockwise, the outer product is negative; otherwise, it is positive, and a value of 0 means that the two are in the same direction (parallel). In addition, the paper deals with the concepts of line equations and equations, see linear algebra.

For the convenience of calculation, the size comparison of the punctuation marks is defined as follows: the larger point of x coordinates is large, the larger point of x coordinates is equal, but the larger point of y coordinates is large, and the points of x and y coordinates are equal. The smaller end of a line segment is the starting point and the larger end is the ending point.

The problem

Given the endpoint coordinates of two line segments, find their position relationship and find the intersection point (if any).

Analysis of the

The position relation of two line segments can be roughly divided into three categories: coincidence part, no coincidence part but intersection point (intersection), no intersection point. In order to avoid the accuracy problem, all overlaps must be eliminated.

Overlap can be divided into: complete overlap, 1 - end overlap, partial overlap three cases. Obviously, the starting and ending points of the two line segments are the same, that is, they are completely coincident. Only the starting point is the same or only the ending point is the same as the end point (note: the end point of a line segment with a smaller coordinate and the starting point of a line segment with a larger coordinate should be judged as the intersection). To determine whether parts overlap, you must first determine whether they are parallel. A line segment L1 (p1 - > p2) and L2 (p3 - > p4), wherein p1(x1,y1) is the starting point of the first line segment, p2(x2,y2) is the end point of the first line segment, p3(x3,y3) is the starting point of the second line segment, p4(x4,y4) is the end point of the second line segment, thus two vectors can be constructed:

v1 (x2 - x1 y2 - y1), v2 (x4 - x3 y4 - y3)

If the cross product v1×v2 of v1 and v2 is 0, then the two line segments are parallel and may partially coincide. To judge whether the two parallel line segments are collinear, the first end of L1 and the first end of L2 are used to form the vector vs and take the cross product with v2. If vs and v2 are also parallel, the two line segments will be collinear (3 points collinear). Under the premise of collinear, if the end point of the line segment with a smaller starting point is greater than the starting point of the line segment with a larger starting point, it is judged to be partially coincident.

If there is no coincidence, it is necessary to judge whether two lines intersect or not, and the main algorithm still relies on the cross product. However, the calculation cost of the cross product is relatively large. If there are many non-intersecting cases, a quick repulsion experiment can be performed first: the two line segments can be regarded as the diagonals of two rectangles, and the two rectangles can be constructed. If there is no overlap between the two rectangles (x or y), they will be judged as disjoint.

The straddle test is then performed. The two intersecting line segments must cross each other, simply speaking, p1 and p2 are located on both sides of L2 and p3 and p4 are located on both sides of L1, so you can use the cross product to make a judgment. Construct vectors s1(p3,p1),s2(p3,p2), respectively, if s1×v2 and s2×v2 are different Numbers (s1-) > v2 and s2 - > v2 rotates in the opposite direction), indicating that p1 and p2 are located on both sides of L2. Similarly, whether p3 and p4 straddle L1 can be determined. If any one of the four cross products is equal to 0, the end point of one line segment is on another line.

When the intersection of two line segments is determined, the intersection point can be solved. And, of course, you can do it using plane geometry, using point-slope equations. However, it is difficult to deal with the special case where the slope is 0, and multiple division will occur in the operation, so it is difficult to guarantee the accuracy. We're going to use the vector method here.

If the intersection point is (x0,y0), then the following equations must be established:

x0-x1=k1(x2-x1)

y0-y1=k1(y2-y1)

x0-x3=k2(x4-x3)

y0-y3=k2(y4-y3)

Among them, k1 and k2 are any constants that are not 0 (if they are 0, there are overlapping endpoints, which have been excluded above). Formula 1 is connected with formula 2, formula 3 is connected with formula 4, and k1 and k2 are eliminated to get:

x0(y2-y1)-x1(y2-y1)=y0(x2-x1)-y1(x2-x1)

x0(y4-y3)-x3(y4-y3)=y0(x4-x3)-y3(x4-x3)

Move the term containing the unknowns x0 and y0 to the left, and the constant term to the right, thus:

(y2-y1)x0+(x1-x2)y0=(y2-y1)x1+(x1-x2)y1

(y4-y3)x0+(x3-x4)y0=(y4-y3)x3+(x3-x4)y3

Let the two constant terms be b1 and b2, respectively:

b1=(y2-y1)x1+(x1-x2)y1

b2=(y4-y3)x3+(x3-x4)y3

The determinant of the coefficient is D, and the determinant of the coefficient obtained by replacing the coefficient of x0 with b1 and b2 is D1, and the determinant of the coefficient obtained by replacing the coefficient of y0 is D2, then:

|D|=(x2-x1)(y4-y3)-(x4-x3)(y2-y1)

|D1|=b2(x2-x1)-b1(x4-x3)

|D2|=b2(y2-y1)-b1(y4-y3)

Thus, the intersection coordinates can be obtained as follows:

x0=|D1|/|D|,y0=|D2|/|D|

Never put off till tomorrow what you can.

C + + / STL implementation

#include <iostream>
#include <cmath>
using namespace std;
struct POINTF {float x; float y;};
bool Equal(float f1, float f2) {
  return (abs(f1 - f2) < 1e-4f);
}
// To see if the two points are equal 
bool operator==(const POINTF &p1, const POINTF &p2) {
  return (Equal(p1.x, p2.x) && Equal(p1.y, p2.y));
}
// Compare the size of the two points. Compare them first x Coordinate, if the same then compare y coordinates 
bool operator>(const POINTF &p1, const POINTF &p2) {
  return (p1.x > p2.x || (Equal(p1.x, p2.x) && p1.y > p2.y));
}
// Take the cross product of two vectors 
float operator^(const POINTF &p1, const POINTF &p2) {
  return (p1.x * p2.y - p1.y * p2.x);
}
// Determine the position relation of two line segments and find the intersection point ( If there is ) . The return values are listed as follows: 
//[ A coincidence ]  coincide (6) . 1 The endpoints are coincident and collinear (5) , partial overlap (4)
//[ There is no coincidence ]  Two ends meet (3) It's on the line (2) The orthogonal (1) No pay, (0) , parameter error (-1)
int Intersection(POINTF p1, POINTF p2, POINTF p3, POINTF p4, POINTF &Int) {
  // Ensure the parameters p1!=p2 . p3!=p4
  if (p1 == p2 || p3 == p4) {
    return -1; // return -1 Represents at least 1 Line segments coincide with each other and cannot form a line segment 
  }
  // In order to facilitate calculation, the starting point of each line segment should be in front and the end point should be behind. 
  if (p1 > p2) {
    swap(p1, p2);
  }
  if (p3 > p4) {
    swap(p3, p4);
  }
  // Determine whether the two line segments are completely coincident 
  if (p1 == p3 && p2 == p4) {
    return 6;
  }
  // Find the vector made up of two line segments 
  POINTF v1 = {p2.x - p1.x, p2.y - p1.y}, v2 = {p4.x - p3.x, p4.y - p3.y};
  // Take the cross product of two vectors 0
  float Corss = v1 ^ v2;
  // If the starting points overlap 
  if (p1 == p3) {
    Int = p1;
    // The starting points are coincident and collinear ( parallel ) return 5 ; If it's not parallel, it intersects the endpoint and returns 3
    return (Equal(Corss, 0) ? 5 : 3);
  }
  // If the end points overlap 
  if (p2 == p4) {
    Int = p2;
    // The ends coincide and are collinear ( parallel ) return 5 ; If it's not parallel, it intersects the endpoint and returns 3
    return (Equal(Corss, 0) ? 5 : 3);
  }
  // If the two ends are end to end 
  if (p1 == p4) {
    Int = p1;
    return 3;
  }
  if (p2 == p3) {
    Int = p2;
    return 3;
  }// After the above judgment, the situation of the first and last point weighing each other has been ruled out 
  // Sort the line segments by starting coordinates. If the line segment 1 If the starting point is larger, the two line segments are swapped 
  if (p1 > p3) {
    swap(p1, p3);
    swap(p2, p4);
    // Update the original vector and its cross product 
    swap(v1, v2);
    Corss = v1 ^ v2;
  }
  // Handle situations where two line segments are parallel 
  if (Equal(Corss, 0)) {
    // Do vector v1(p1, p2) and vs(p1,p3) The cross product of, to determine whether or not collinear 
    POINTF vs = {p3.x - p1.x, p3.y - p1.y};
    // As a product outside 0 Then the two parallel line segments are collinear, and the following judge whether there is an overlap part 
    if (Equal(v1 ^ vs, 0)) {
      // before 1 The end of a line is greater than the end of the line 1 The starting point of the line is judged to be overlapped 
      if (p2 > p3) {
        Int = p3;
        return 4; // The return value 4 Represents line segment overlap 
      }
    }// if 3 If the points are not collinear, the two parallel segments must not be collinear. 
    // Neither collinear nor collinear parallel lines have an intersection 
    return 0;
  } // The following is the case of unevenness. A quick repulsion test is carried out first 
  //x Coordinates have been ordered and can be directly compared. y The coordinate is to find the maximum and minimum values of the two line segments 
  float ymax1 = p1.y, ymin1 = p2.y, ymax2 = p3.y, ymin2 = p4.y;
  if (ymax1 < ymin1) {
    swap(ymax1, ymin1);
  }
  if (ymax2 < ymin2) {
    swap(ymax2, ymin2);
  }
  // If rectangles with two line segments diagonally do not intersect, there is no intersection 
  if (p1.x > p4.x || p2.x < p3.x || ymax1 < ymin2 || ymin1 > ymax2) {
    return 0;
  }// Let's do the straddle test 
  POINTF vs1 = {p1.x - p3.x, p1.y - p3.y}, vs2 = {p2.x - p3.x, p2.y - p3.y};
  POINTF vt1 = {p3.x - p1.x, p3.y - p1.y}, vt2 = {p4.x - p1.x, p4.y - p1.y};
  float s1v2, s2v2, t1v1, t2v1;
  // Decide whether to cross the line according to the cross product result 
  if (Equal(s1v2 = vs1 ^ v2, 0) && p4 > p1 && p1 > p3) {
    Int = p1;
    return 2;
  }
  if (Equal(s2v2 = vs2 ^ v2, 0) && p4 > p2 && p2 > p3) {
    Int = p2;
    return 2;
  }
  if (Equal(t1v1 = vt1 ^ v1, 0) && p2 > p3 && p3 > p1) {
    Int = p3;
    return 2;
  }
  if (Equal(t2v1 = vt2 ^ v1, 0) && p2 > p4 && p4 > p1) {
    Int = p4;
    return 2;
  } // If it is not intersected on the line, the intersection is determined 
  if(s1v2 * s2v2 > 0 || t1v1 * t2v1 > 0) {
    return 0;
  } // The following is the case of intersection, see the algorithm in the documentation 
  // To calculate 2 The two constant terms of the order determinant 
  float ConA = p1.x * v1.y - p1.y * v1.x;
  float ConB = p3.x * v2.y - p3.y * v2.x;
  // Computing determinant D1 and D2 Divide by the determinant of the coefficients, and you get the intersection point 
  Int.x = (ConB * v1.x - ConA * v2.x) / Corss;
  Int.y = (ConB * v1.y - ConA * v2.y) / Corss;
  // Orthogonal return 1
  return 1;
}
// The main function 
int main(void) {
  // Randomly generated 100 Test data 
  for (int i = 0; i < 100; ++i) {
    POINTF p1, p2, p3, p4, Int;
    p1.x = (float)(rand() % 10); p1.y = (float)(rand() % 10);
    p2.x = (float)(rand() % 10); p2.y = (float)(rand() % 10);
    p3.x = (float)(rand() % 10); p3.y = (float)(rand() % 10);
    p4.x = (float)(rand() % 10); p4.y = (float)(rand() % 10);
    int nr = Intersection(p1, p2, p3, p4, Int);
    cout << "[(";
    cout << (int)p1.x << ',' << (int)p1.y << "),(";
    cout << (int)p2.x << ',' << (int)p2.y << ")]--[(";
    cout << (int)p3.x << ',' << (int)p3.y << "),(";
    cout << (int)p4.x << ',' << (int)p4.y << ")]: ";
    cout << nr;
    if (nr > 0) {
      cout << '(' << Int.x << ',' << Int.y << ')';
    }
    cout << endl;
  }
  return 0;
}

As for stl, it seems that it is not used much anymore. It is not out of date, but controlled use. Each project has its own use scenarios, and appropriate technologies are selected according to its own needs.

conclusion

That's the end of the C++/STL code example for determining the position of two line segments in a plane. Interested friends can continue to see this website:

C++ recursive algorithm example code

C++ function pointer details and code sharing

Introduction to C/C++ compiler optimization

If there are shortcomings, welcome to point out the message.