I am participating in the nuggets Community game creative submission Contest. For details, please see: Game Creative Submission Contest

Main Contents:

  • Dot product and cross product
  • Determine the position of the point in relation to the line
  • Determine whether two line segments intersect and calculate the intersection point
  • Judge two line segments to merge and calculate their overlap
  • Todo merges two overlapping line segments

Dot product

  • Formula: a, b = (ax, ay) (bx, by) = axbx + ayby = | a |, | | b, cosine theta. The result is a scalar quantity.
  • Calculate the vector b in vector projection on a unit vector) : projection length = | | b · cosine theta; Projection = a. | | b cosine theta
  • Calculate the Angle between two vectors: cos theta = a. b/(| a | | | b) = > theta = arccos (a, b/(| | | | b, a))
  • The larger the dot product is, the smaller the Angle between the two vectors is. Can be used to judge the size of the included Angle.
    • The dot product result == 1: the included Angle θ == 0;
    • Dot product results > 0:0 <= Angle θ <90;
    • The dot product result == 0: the included Angle θ == 90;
    • The dot product results were < 0:90 < included Angle θ < 180;
    • The dot product result == -1: the Angle θ == 190.

Cross product

  • The calculation formula is: A ×b=(AX, AY,az)×(bx,by,bz)=(AyBz-AZby, AZBx-axbz,axby-aybx).
  • The result is a vector perpendicular to a and B, which can be used to judge the relative position of vectors A and B (clockwise or counterclockwise).
  • | | = a * b | a |, | | b, sine theta equals to a and b for both sides of the area of the parallelogram

The position of a point in relation to a line

Known conditions: point M, line segment L (endpoints A, B), judge the position relationship between point and line

Calculation method 1:

Line formula: A * X + b * Y + c = 0

Derivation formula:

  1. Substitute the end points of line segments into the line formula: A * A.x + B * A.y + C = 0 A * B.x + B * B.y + C = 0
  2. Two type of addition, subtraction, respectively: (+ B.x A.x) * a + (A.y + B.y) * b + 2 c = 0 (A.x – B.x) * a + (A.y – B.y) * b = 0
  3. Formulation Jane: b = (B.x – A.x)/(A.y – B.y) * a c = – a * (A.y * * B.y B.x – A.x)/(A.y – B.y)
  4. The original expressed in a linear formula: a * X + (B.x – A.x)/(A.y – B.y) * a * Y – a * (A.y * * B.y B.x – A.x)/(A.y – B.y) = 0
  5. Formula on both sides at the same time, in addition to a, linear formula expressed in point a/B: X + (B.x – A.x)/(A.y – B.y) * Y – (A.y * * B.y B.x – A.x)/(A.y – B.y) = 0
  6. Continue to Jane: (A.y – B.y) * X + (B.x – A.x) * Y – (A.y * * B.y B.x – A.x) = 0
  7. The left-hand side of the formula is equal to 0, the point is on the line, the left side of the formula is greater than 0, the point is on the right side of the line, the left side of the formula is less than 0, the point is on the left side of the line.
  8. Substitute the target point M into the formula: (A.y – B.y) * M.x + (B.x – A.x) * M.y – (A.y * B.x – A.x * B.y) A.y * M.x – B.y * M.x + B.x * M.y – A.x * M.y – A.y * B.x + A.x * B.y
  9. Final finishing: (B.y – M.y) * (A.x – M.x) – (A.y – M.y) * (B.x – M.x)

Code implementation:

// The position of point and line, target point M, AB public float PointOfLine(Vector2 A,Vector2 B) {// Return value > 0 on the right, = 0 on the right, < 0 on the left side return (B.y - M.y) * (A.x - M.x) - (A.y - M.y) * (B.x - M.x); } public bool IsPointOnLine(Vector2 A,Vector2 B) {return IsZero(PointOfLine(M,A,B)); }Copy the code

Calculation Method 2:

Steps for judging the position of point and straight line segment:

  1. Point M coincides with endpoint A or B;
  2. If the line segment has no slope or the slope is 0, determine whether M is on the line AB, and determine whether M is on the line segment;
  3. The line segment has a slope. Determine whether the slope of line segment MA and BM is consistent

Code implementation:

// Check whether the target point M is on the line segment. The line AB public bool IsPointOnLine (Vector2 Vector2 M, A, Vector2 B) {/ / with the endpoint overlap the if (M = = A | | M = = B) return true; If (IsZero(a.x-b.x) &&iszero (a.x-m.x)) {// If (IsZero(a.x-b.x) &&iszero (a.x-m.x)) {// If (IsZero(a.x-b.x) &&iszero (a.x-m.x)) { The point on the line segment / / if ((M.y < B.y && M.y > A.y) | | (M.y < A.y && M.y > B.y)), reduction as follows: If ((A.y - M.y) * (M.y - B.y) > 0.0 f) {return true; } return false; } / / in the same horizontal else if (IsZero (A.y - B.y) && IsZero (A.y - M.y)) {if ((A.x - M.x) * (M.x - B.x) > 0.0 f) {return true; } return false; Else {// point on the line, MA and MB have the same slope, and have something in common M, MA and MB coincide, On line AB if the point M (IsZero ((A.y - M.y)/(A.x - M.x) - (M.y - B.y)/(M.x - B.x))) {/ / decision point on the line, if the point between two endpoints, The point on the line if (((A.y - M.y) * (M.y - B.y) > 0) && ((A.x - M.x) * (M.x - B.x) > 0)) {return true; } } return false; }}Copy the code

Determine whether two line segments intersect

Known conditions: Line segment L1 (endpoints A and B), line segment L2 (endpoints C and D)

The intersection relation of two line segments (not considering the case of overlap, if the line segments overlap, only one point is returned) :

  • Complete intersection: the endpoints of line segment AB are on both sides of line segment CD, and the endpoints of line segment CD are also on both sides of line segment AB;
  • Incomplete intersection: one end of A line segment is on another line segment (for example, endpoint A is on line segment CD, and if endpoint B is also considered to overlap, the overlap situation is not distinguished temporarily)
  • Disjoint: Both ends of a line segment are on the same side of another line segment

First, calculate the position relationship between each endpoint and the line, and judge the position relationship between segments

Code implementation:

Vector2 public Vector2 public Vector2 public Vector2 public Vector2 LineCross(vector2a, vector2b, vector2c, vector2d) {float pointPosA = PointOfLine(A,C,D); float pointPosB = PointOfLine(B,C,D); float pointPosC = PointOfLine(C,A,B); float pointPosD = PointOfLine(D,A,B); // Completely intersect: The ends of segment AB are on either side of segment CD, If (pointPosA * pointPosB < 0 &&pointposc * pointPosD < 0) {return GetCrosPoint(A,B,C,D); if(pointPosA * pointPosB < 0 &&pointposc * pointPosD < 0); } if(IsZero(pointPosA)) return A; if(IsZero(pointPosB)) return B; if(IsZero(pointPosC)) return C; if(IsZero(pointPosD)) return D; / / if they do not meet the above conditions, the disjoint / / judgment conditions: pointPosA * pointPosB > 0 | | pointPosC * pointPosD > 0 return null; }Copy the code

Calculate the intersection of two intersecting line segments

Equation of the line: Y = aX + b

Case processing of intersecting line segment (the premise is that line segment intersection has been determined) :

  1. If both lines have no slope, or if they have the same slope, then they’re parallel
    • There is no intersection
  2. Else if only one line segment has no slope
  • Method 1: Solve the formula
    • The calculation formula (assuming that line segment AB has no slope and line segment CD does) is as follows:
    • The equation of a line for segment AB: The line has no slope, X = Ax
    • Line equation of line segment CD:
      • Calculate the slope based on two points: a2 = (d.y-c.y)/(d.x-c.x)
      • Intercept: b = y-ax = (c.y-c.x * a2)
      • Substitute the slope into the formula to obtain the line: Y = A2 * X + (c.y-c.x * a2)
    • Calculate the intersection according to the two line formulas
      • x = A.x;
      • y = a2 * (A.x – C.x) + C.y;
  • Method two: the relationship between three sides of a triangle
    • Let’s assume that segment AB has no slope, segment CD has a slope, and the intersection is M
    • The intersection point M is on segment AB, and its x-coordinate is the same as that of any point on the segment
    • The intersection point M is on line segment CD, CM and CD are on the same line, and the slope of the two line segments is equal
    • (M.y – C.y) / (M.x – C.x) = a2
    • M.y = a2 * (M.x – C.x) + C.y
    • M.x = A.x
    • M.y = a2 * (A.x – C.x) + C.y
  1. Else Both lines have slopes
    • Calculate the slope and intercept of two line segments; Solve equations.

Code implementation:

Vector2 public Vector2 public Vector2 public Vector2 public Vector2 GetCrosPoint(vector2a, vector2b, vector2c, vector2d) { Y = aX + b if(IsZero((a.x-b.x) - (c.x-d.x))) {return null; } else if(IsZero(A.x -- B.x)) {// if(A.x -- B.x) {// if(A.x -- B.x) {// if(A.x -- B.x) {// if(A.x -- B.x) {// if(A.x -- B.x) { A2 = (D.y - C.y)/(D.x - C.x) / / intercept: = Y - aX = b (C.y - C.x * a2) / / bringing slope to obtain linear formula: Y = a2 * X + (c.y-c.x * a2); y = a2 * (A.x - C.x) + C.y; // Method 2: Triangle relation (not recommended) // The calculation process is as follows: // The intersection point M is on the line segment AB, and its x coordinates are the same as any point of the line segment. // The intersection point M is on the line segment CD, CM and CD are on the same line. Two line segments equal slope / / (M.y - C.y)/(M.x - C.x) = a2 / / M.y = a2 * (M.x - C.x) + C.y / / M.x = A.x / / M.y = a2 * (A.x - C.x) + C.y // float a2 = (d.y-c.y)/(d.x-c.x); float x = A.x; float y = a2 * (A.x - C.x) + C.y; return new Vector2(x,y); } else if(IsZero(c.x-d.x)) {float x = C.x; float a1 = (B.y - A.y) / (B.x - A.x); float y = a1 * (C.x - A.x) + A.y; return new Vector2(x,y); } else {// Line segments all have slopes and are not equal // Solve the equation, Float a1 = (B.y - A.x) // float a1 = (B.y - A.x) // float a1 = (B.y - A.x) // float a1 = (B.y - A.x) // float a1 = (B.y - A.x) // float a1 = (B.y - A.x) / (B.x - A.x); float a2 = (D.y - C.y) / (D.x - C.x); float x = (a1 * A.x - a2 * C.x - A.y + C.y) / (a1 - a2); float y = a1 * x - a1 * A.x + A.y; return new Vector2(x,y); }}Copy the code

Judge whether two line segments coincide, and calculate the overlap part

Line segment overlap:

  • Inclusion overlap: A line segment is contained within another line segment, for example, the end points A and B of segment AB are both on segment CD;
  • Crossover coincidence: the end point A of segment AB is on segment CD, and the end point C of segment CD is on segment AB, and AC is not the same point;
  • Don’t overlap.

Judge and merge the two line segments to calculate their overlapping parts, such as line segment AB and line segment CD(the overlapping part is a line segment, return the two endpoints of the overlapping line segment, not considering the case of only one overlapping point) :

Public Vector2[] LineCoincide(vector2a, vector2b, vector2c, vector2d) {// // onLineA &&onlineb // onLineC &&onlineB // OnLineA &&onlinec &&a! // onLineA &&onlinec &&a! = C // onLineA && onLineD && A ! = D // onLineB && onLineC && B ! = C // onLineB && onLineD && B ! Bool onLineA = IsPointOnLine(A,C,D); bool onLineB = IsPointOnLine(B,C,D); bool onLineC = IsPointOnLine(C,A,B); bool onLineD = IsPointOnLine(D,A,B); //coincide01 if(onLineA && onLineB) return new Vector2[] { A,B }; else if(onLineC && onLineD) return new Vector2[] { C,D }; //coincide02 if(onLineA && onLineC && (A ! = C)) return new Vector2[] { A,C }; else if(onLineA && onLineD && (A ! = D)) return new Vector2[] { A,D }; else if(onLineB && onLineC && (B ! = C)) return new Vector2[] { B,C }; else if(onLineB && onLineD && (B ! = D)) return new Vector2[] { B,D }; Return null; }Copy the code

Just determine whether the two line segments overlap, line AB and line CD

public bool IsLineCoincide(Vector2 A,Vector2 B,Vector2 C,Vector2 D) { bool onLineA = IsPointOnLine(A,C,D); bool onLineB = IsPointOnLine(B,C,D); bool onLineC = IsPointOnLine(C,A,B); bool onLineD = IsPointOnLine(D,A,B); if((onLineA && onLineB) || (onLineC && onLineD)) return true; if((onLineA && onLineC && (A ! = C)) || (onLineA && onLineD && (A ! = D)) || (onLineB && onLineC && (B ! = C)) || (onLineB && onLineD && (B ! = D))) return true; return false; }Copy the code
Float == 0 bool IsZero(float floatValue) {if(floatValue > -0.00001f & floatValue < 0.00001f) return true; else return false; }Copy the code