------------------------------------------------------------------------------ Performs intersection of the projection of two finite 3D lines onto a 2D plane. An intersection is found if the projection of the two lines onto the plane perpendicular to the cross product of the two lines intersect. The parameters (u,v) are the parametric coordinates of the lines at the position of closest approach.
| 88 | // The parameters (u,v) are the parametric coordinates of the lines at the |
| 89 | // position of closest approach. |
| 90 | int vtkLine::Intersection(const double a1[3], const double a2[3], const double b1[3], |
| 91 | const double b2[3], double& u, double& v, double tolerance, int tolType) |
| 92 | { |
| 93 | double a21[3], b21[3], b1a1[3]; |
| 94 | double c[2]; |
| 95 | double *A[2], row1[2], row2[2]; |
| 96 | |
| 97 | // Initialize |
| 98 | u = v = 0.0; |
| 99 | |
| 100 | // Determine line vectors. |
| 101 | vtkMath::Subtract(a2, a1, a21); |
| 102 | vtkMath::Subtract(b2, b1, b21); |
| 103 | vtkMath::Subtract(b1, a1, b1a1); |
| 104 | |
| 105 | // Compute the system (least squares) matrix. |
| 106 | A[0] = row1; |
| 107 | A[1] = row2; |
| 108 | row1[0] = vtkMath::Dot(a21, a21); |
| 109 | row1[1] = -vtkMath::Dot(a21, b21); |
| 110 | row2[0] = row1[1]; |
| 111 | row2[1] = vtkMath::Dot(b21, b21); |
| 112 | |
| 113 | // Compute the least squares system constant term. |
| 114 | c[0] = vtkMath::Dot(a21, b1a1); |
| 115 | c[1] = -vtkMath::Dot(b21, b1a1); |
| 116 | |
| 117 | // Solve the system of equations. Check for colinearity. |
| 118 | if (vtkMath::SolveLinearSystem(A, c, 2) == 0) |
| 119 | { |
| 120 | // The lines are colinear. Therefore, one of the four endpoints is the |
| 121 | // point of closest approach |
| 122 | double minDist = VTK_DOUBLE_MAX; |
| 123 | const double* p[4] = { a1, a2, b1, b2 }; |
| 124 | const double* l1[4] = { b1, b1, a1, a1 }; |
| 125 | const double* l2[4] = { b2, b2, a2, a2 }; |
| 126 | double* uv1[4] = { &v, &v, &u, &u }; |
| 127 | double* uv2[4] = { &u, &u, &v, &v }; |
| 128 | double t = 0; |
| 129 | for (unsigned i = 0; i < 4; i++) |
| 130 | { |
| 131 | double dist = vtkLine::DistanceToLine(p[i], l1[i], l2[i], t); |
| 132 | if (dist < minDist) |
| 133 | { |
| 134 | minDist = dist; |
| 135 | *(uv1[i]) = t; |
| 136 | *(uv2[i]) = static_cast<double>(i % 2); // the corresponding extremum |
| 137 | } |
| 138 | } |
| 139 | return OnLine; |
| 140 | } // if colinear |
| 141 | |
| 142 | // The lines are not colinear, check for intersection. |
| 143 | // However if they are nearly parallel then the solution |
| 144 | // found by vtkMath::SolveLinearSystem may be very inaccurate. |
| 145 | // We hence need to check the solution against a tolerance criterion. |
| 146 | u = c[0]; |
| 147 | v = c[1]; |
no test coverage detected