2.1. Analytic geometry algorithm
For example, when judging the intersection of two line segments in a plane, we can easily solve the algebraic equation of two straight lines through analytical geometry:

(y−y2)/(y1−y2)=(x−x2)/(x1−x2)
Then the binary quadratic equation is solved. It is easy to get the code of the corresponding algorithm:

//Judge the intersection of two line segments
bool IsIntersect(double px1, double py1, double px2, double py2, double px3, double py3, double px4, double py4)
{
bool flag = false;
double d = (px2 - px1) * (py4 - py3) - (py2 - py1) * (px4 - px3);
if (d != 0)
{
double r = ((py1 - py3) * (px4 - px3) - (px1 - px3) * (py4 - py3)) / d;
double s = ((py1 - py3) * (px2 - px1) - (px1 - px3) * (py2 - py1)) / d;
if ((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1))
{
flag = true;
}
}
return flag;
}
It can be seen that this algorithm is not rigorous. In fact, it lacks the judgment of some extreme conditions, such as parallel to the coordinate axis and parallel to two straight lines. Additional judgment is needed. At the same time, a lot of multiplication and division are used, and the efficiency of the algorithm is not high.

2.2. Ipsilateral method
The idea of this algorithm is that if two line segments intersect, the two ends of one line segment must be on the opposite side of the two ends of the other line segment. Then the problem can be transformed into whether the point is on the same side of a line segment. The same side judgment can be realized by the method of vector cross multiplication, that is, to judge whether the direction of the last cross multiplication is the same.

This algorithm is the same as the same side / opposite side judgment algorithm introduced in this article. I think it is an excellent and fast algorithm. However, this algorithm can judge the qualitative judgment, but can not judge the accurate intersection quantitatively. Moreover, in the actual use process, it seems that the accuracy is not very accurate (personal experimental conclusions, especially the points on the edge of the triangle).

2.3. Vector equation method
2.3.1. principle
Given the starting point O and ending point E of the line segment in space, it is obvious that the direction vector D is:

D=E−O
At this time, it can be determined that a point P on the line segment is:

P=O+tD
Where t is the scalar whose range satisfies 0 < = T < = 1.

This equation is the vector equation of a certain point on the line segment. If the intersection of two line segments is required, it is obvious that the two line segments can be combined:

{P=O1+t1D1P=O2+t2D2
Upper formula - lower formula, including:

t1D1−t2D2=O2−O1=O12(1)
Expand on a plane, that is, use the X and Y components:

[D1.xD1.y−D2.x−D2.y][t1t2]=[O12.xO12.y]
Then this problem is transformed into solving a system of linear equations with two rows and two columns. If there is a solution, it indicates that there is an intersection and can be solved directly. Linear equations with 2 rows and 2 columns can be solved directly by Clem's law.

2.3.2. realization
The specific C + + implementation code is as follows:

//Space line
template
class LineSegment
{
public:
Vec3 startPoint;
Vec3 endPoint;
Vec3 direction;

Vec3<T> min;
Vec3<T> max;

LineSegment()
{
}

LineSegment(Vec3<T> start, Vec3<T> end)
{
    startPoint = start;
    endPoint = end;
    direction = end - start;
    CalMinMax();
}

inline void Set(Vec3<T> start, Vec3<T> end)
{
    startPoint = start;
    endPoint = end;
    direction = end - start;
    CalMinMax();
}

inline void CalMinMax()
{
    min.x() = std::min<T>(startPoint.x(), endPoint.x());
    min.y() = std::min<T>(startPoint.y(), endPoint.y());
    min.z() = std::min<T>(startPoint.z(), endPoint.z());

    max.x() = std::max<T>(startPoint.x(), endPoint.x());
    max.y() = std::max<T>(startPoint.y(), endPoint.y());
    max.z() = std::max<T>(startPoint.z(), endPoint.z());
}

//Two line segments intersect
inline static bool Intersection2D(LineSegment & line1, LineSegment & line2, Vec3<T>& insPoint)
{
    double D = -line1.direction.x() * line2.direction.y() + line1.direction.y() * line2.direction.x();
    if(D == 0.0)
    {
        return false;
    }

    auto O12 = line2.startPoint - line1.startPoint;
    T D1 = -O12.x() * line2.direction.y() + O12.y() * line2.direction.x();
    T D2 = line1.direction.x() * O12.y() - line1.direction.y() * O12.x();

    T t1 = D1 / D;
    if(t1<0 || t1 > 1)
    {
        return false;
    }

    T t2 = D2 / D;
    if(t2<0 || t2 > 1)
    {
        return false;
    }

    insPoint = line1.startPoint + line1.direction * t1;     //The Z value calculated in this way is inaccurate

    return true;
}  

};
USB Microphone https://www.soft-voice.com/
Wooden Speakers https://www.zeshuiplatform.com/
Amazon evaluation www.yisuping.com cn
Shenzhen website construction www.sz886.com com