The contents of this article are very basic, mainly for beginners like me, so please ask all the algorithm emperors to take a quick look
Quote
It is known that line segment 1 (a,b) and line segment 2 (c,d) , where abcd is the endpoint, find the intersection point p of the line segment. (parallel or collinear are considered disjoint)
Algorithm 1: Find the intersection point of the straight line where the two line segments are located, and then determine whether the intersection point is on the two line segments.
When finding the intersection point of a straight line, we can find it through the general equation of ax+by+c=0 of the straight line (abc in the equation is a coefficient, not the end point mentioned above. In addition, point oblique equations and oblique intercept equations can also be used, not here for now).
Then, based on the positional relationship between the intersection point and the end point of the line segment, we can determine whether the intersection point is on the line segment.
The formula is as follows:
<code>function segmentsIntr(a, b, c, d){ /** 1 Solve the system of linear equations and find the intersection of line segments. **/ // If the denominator is 0, it is parallel or collinear, and does not intersect var denominator = (by - ay)*(dx - cx) - (ax - bx)*(cy - dy); if (denominator==0) { return false; } // The intersection coordinate of the straight line where the line segment is located (x , y) var x = ( (bx - ax) * (dx - cx) * (cy - ay) + (by - ay) * (dx - cx) * ax - (dy - cy) * (bx - ax) * cx ) / denominator ; var y = -( (by - ay) * (dy - cy) * (cx - ax) + (bx - ax) * (dy - cy) * ay - (dx - cx) * (by - ay) * cy ) / denominator; /** 2 Determine whether the intersection is on two segments**/ if ( // The intersection is on line segment 1 (x - ax) * (x - bx) <= 0 && (y - ay) * (y - by) <= 0 // And the intersection is also on line segment 2 && (x - cx) * (x - dx) <= 0 && (y - cy) * (y - dy) <= 0 ){ // Return to the intersection p return { x : x, y : y } } //Otherwise, the disjoint return false } </code>The algorithm first has a clear and easy-to-understand idea, but its performance is not high. Because it calculates the intersection before it is uncertain whether the intersection is valid (on the online segment), which takes a lot of time.
If the intersection point is finally found to be invalid, then the previous calculation will be in vain. Moreover, the entire calculation process is also very complicated.
So is there a way to tell whether there is an effective intersection point first and then calculate it?
Obviously the answer is yes. So some algorithms are found.
Algorithm 2: Determine whether the two end points of each line segment are on both sides of the other line segment. Then find the intersection of the straight line where the two line segments are located, otherwise they do not intersect.
The first step is to determine whether two points are on both sides of a certain line segment. Projection method can usually be used:
Find the normal vector of the line segment, then project the point onto the normal line, and finally judge the relationship between the point and the line segment based on the projected position.
See the picture below
The projection on the normal line segment cd of point a and point b is shown in the figure. At this time, we also need to project the line segment cd on our normal line (just select one of point c or point d).
Mainly used for reference.
In the figure, the projection of point a and point b are projected on both sides of point c projection, indicating both sides of line segment cd of line segment ab.
Similarly, just judge whether CD is on both sides of the line segment ab again.
Finding normals, projection and other things sound very complicated, but in fact it is indeed quite complicated for me. I didn't know much about geometry knowledge a few months ago (I forgot all the knowledge of geometry when I was studying:'( )'
Fortunately, learning and implementation are not complicated, and there are formulas to follow.
Find the normal of line segment ab:
var nx=by - ay, ny=ax - bx; var normalLine = { x: nx, y: ny }; Note: where the geometric meanings of normalLine.x and normalLine.y represent the direction of the normal line, not the coordinates.
Find the projection position of point c on the normal line:
var dist= normalLine.x*cx + normalLine.y*cy;
Note: The "projection position" here is a scalar, which represents the distance to the origin of the normal, not the coordinates of the projection point.
It is usually enough to know this distance.
After we calculate the projection of points a (distA), point b (distB), and point c (distC) in the figure, we can easily judge the relative position based on their respective sizes.
When distA==distB==distC, the two segments are collinear
When distA==distB!=distC, the two line segments are parallel
When distA and distB are on the same side of distC, the two line segments do not intersect.
When distA and distB are on the opposite side of distC, whether the two line segments intersect needs to be judged again whether the relationship between point c and line segment ab.
The previous steps only implement "judging whether line segments intersect". When the result is true, we need to further find the intersection point.
Let’s talk about the process of finding the intersection point later. Let’s first look at the complete implementation of this algorithm:
function segmentsIntr(a, b, c, d){ //Normal N1 var nx1 = (by - ay), ny1 = (ax - bx); //Normal N2 var nx2 = (dy - cy), ny2 = (cx - dx); //Two normals are multiplied, if the result is 0, it means that the line segment ab and segment cd are parallel or collinear, and do not intersect var denominator = nx1*ny2 - ny1*nx2; if (denominator==0) { return false; } //Projection on normal N2 var distC_N2=nx2 * cx + ny2 * cy; var distA_N2=nx2 * ax + ny2 * ay-distC_N2; var distB_N2=nx2 * bx + ny2 * by-distC_N2; // The projection of point a and point b are on the same side of point c projection (for the case on the line segment, this example is treated as disjoint); if ( distA_N2*distB_N2>=0 ) { return false; } // //Judge the relationship between point c point d and line segment ab, the principle is the same as above // // Projection on normal N1 var distA_N1=nx1 * ax + ny1 * ay; var distC_N1=nx1 * cx + ny1 * cy-distA_N1; var distD_N1=nx1 * dx + ny1 * dy-distA_N1; if ( distC_N1*distD_N1>=0 ) { return false; } // Calculate the intersection coordinates var fraction= distA_N2 / denominator; var dx= fraction * ny1, dy= -fraction * nx1; return { x: ax + dx , y: ay + dy }; }The method used to find the coordinates of the intersection point in the end looks a bit strange, and it feels like it is inconspicuous.
In fact, it is similar to the algorithm in Algorithm 1, except that many of the calculation terms in it have been calculated in advance.
In other words, the part of the algorithm to find the coordinates of the intersection point in two miles is actually made of linear equations of a straight line.
Now let’s compare algorithm one and algorithm two in a simple and rough and unscientific way:
1. In the best case, the complexity of the two algorithms is the same
2. In the worst case, the calculation amount of algorithm 1 and algorithm 2 is almost the same
3. However, algorithm 2 provides more "early end conditions", so on average, algorithm 2 should be better.
After actual testing, the actual situation is indeed the case.
The two previous algorithms are basically common and can cope with most situations. But in fact, there is a better algorithm.
This is what I have just learned recently (I learned it now and sold it now, don't mind it...)
Algorithm 3: Determine whether the two end points of each line segment are on both sides of the other line segment. If you find the intersection of the straight line where the two line segments are located, otherwise they will not intersect.
(Huh? Why does it feel the same as Algorithm 2? Don't doubt it is indeed the same... )
The so-called Algorithm 3 is actually just an improvement to Algorithm 2. The main improvements are:
The positional relationship between points and line segments is not judged by normal projection, but by the area of triangles composed of points and line segments.
Let’s first review the triangle area formula: It is known that the three points a(x,y) b(x,y) c(x,y) of the triangle area is:
<code>var triArea=( (ax - cx) * (by - cy) - (ay - cy) * (bx - cx) ) /2 ; </code>
Because the area of a parallelogram (two vectors are adjacent sides) composed of two vectors forking == the two vectors, the above formula is not difficult to understand.
Moreover, since vectors have directions, the area also has directions. Usually, we use counterclockwise as positive and clockwise as negative.
The key points of the improved algorithm are:
If the positive and negative signs of the triangle area formed by "line segment ab and point c" are different from the triangle area formed by "line segment ab and point d",
Then point c and point d are located on both sides of line segment ab.
As shown in the figure below:
The triangle shown by the dotted line in the figure has different winding directions (the order of definition of the three sides), so the positive and negative symbols of the area are different.
Let's look at the code first:
Since we only need to judge the symbol, we do not need to divide the following by 2 in the preceding triangle area formula.
function segmentsIntr(a, b, c, d){ // 2 times the area of the triangle abc var area_abc = (ax - cx) * (by - cy) - (ay - cy) * (bx - cx); // 2 times the area of the triangle abd var area_abd = (ax - dx) * (by - dy) - (ay - dy) * (bx - dx); // If the area symbols are the same, the two points do not intersect on the same side (in the case of the point on the line segment, this example is treated as disjoint); if ( area_abc*area_abd>=0 ) { return false; } // 2 times the area of the triangle cda var area_cda = (cx - ax) * (dy - ay) - (cy - ay) * (dx - ax); // 2 times the area of the triangle cdb // Note: There is a small optimization here. There is no need to calculate the area with the formula, but it is derived by adding and subtracting the three known areas. var area_cdb = area_cda + area_abc - area_abd ; if ( area_cda * area_cdb >= 0 ) { return false; } // Calculate the intersection coordinates var t = area_cda / ( area_abd- area_abc ); var dx= t*(bx - ax), dy= t*(by - ay); return { x: ax + dx , y: ay + dy }; }Finally, the part that calculates the intersection coordinates is the same as the algorithm.
Based on algorithm 2, Algorithm 3 greatly simplifies the calculation steps and the code is more streamlined. It can be said that it is the best among the three algorithms. The same is true for the actual test results.
Of course, we must be honest, in Javascript, the time complexity of the three algorithms is actually similar for ordinary calculations (especially under the V8 engine).
In my test case, I also conducted abnormal million-level line segment intersection tests to widen the gap between the three algorithms.
Summarize
However, with the attitude of striving for excellence and learning, pursuing a better algorithm always has its positive significance. The above are several algorithms that use js to achieve line segment intersection points. The content is not very profound. I hope it will be helpful to everyone to learn js.