I’m working on a script that iteratively checks for line-line-intersections of a set of line segments that lie within the same plane.
I’ve noticed that sometimes, two nearly parallel line segments have an intersection at a parameter very close to 0.5, which roughly translates to a mid point.
I’m using Rhino.Geometry.Intersect.Intersection.LineLine() to compute the intersections.
I would like to understand what causes this?
I’ve currently fixed the bug that thus emerged, by computing the “two-dimensional” vector cross product of the line segment directions and checking its z-value as a scalar.
If this scalar is between the negative and positive absolute model tolerance (i.e. 0.001), I simply skip the intersection computation for near parallel lines.
This fixes the issue, but I would still want to know how this happens!
Are the lines very very close together, say to 6 or 7 decimal places? I noticed a few years ago when 2 polyline vertices get as close as that, but distinct, they can be treated as coincident.
You’re welcome. I’m just reading the docs now, but I assume they haven’t taken the classical approach of the ancient Greeks, and defined parallel lines as intersecting at infinity, which in some unusual co-ordinate system is at (0.5, 0.5)?
Is this an example of this situation described in the docs?:
Remarks:
If the lines are exactly parallel, meaning the system of equations used to find a and b has no numerical solution, then False is returned. If the lines are nearly parallel, which is often numerically True even if you think the lines look exactly parallel, then the closest points are found and True is returned. So, if you care about weeding out “parallel” lines, then you need to do something like the following:
bool rc = Intersect.LineLine(lineA, lineB, out a, out b, tolerance, segments);
if (rc)
{
double angle_tol = RhinoMath.ToRadians(1.0); // or whatever
double parallel_tol = Math.Cos(angle_tol);
if ( Math.Abs(lineA.UnitTangent * lineB.UnitTangent) >= parallel_tol )
{
... do whatever you think is appropriate
}
}
Dim rc As Boolean = Intersect.LineLine(lineA, lineB, a, b, tolerance, segments)
If (rc) Then
Dim angle_tol As Double = RhinoMath.ToRadians(1.0) 'or whatever
Dim parallel_tolerance As Double = Math.Cos(angle_tol)
If (Math.Abs(lineA.UnitTangent * lineB.UnitTangent) >= parallel_tolerance) Then
... do whatever you think is appropriate
End If
End If
This statement from the documentation totally fits my case, and like mentioned above I use the vector cross product to weed out nearly parallel and parallel lines before checking for intersections. They seem to use the dot product which is another way.
I still want to know why parallel lines have an intersection near their mid points though.
What Rhino version are using? Just tried your file in Rhino 8.18.25076.15001 and can’t seem to reproduce the isse (your code doesn’t implement the overload James is referring to, but this one), if I understood you correctly:
I’m using 8.18.25084.13002 from yesterday on macOS.
You’re right about that, but what James has explained above and what is remarked under the other constructor in the docs, makes totally sense in my case, and it is even necessary to prevent bugs, since even for these nearly parallel lines, the “return code” is True and two parameters are found.
As James said, this is just “what the algorithm found”, which is almost purely noise for two almost parallel lines.
One reason these points could end up in the middle of your lines would be if the noise made it seem like one of them was just slightly out of plane, with one end slightly raised and one end slightly lowered relative to xOy.
Yeah that’s weird and I can reproduce the different behaviors. I’ll dig into that a little bit more.
Thanks, I’ve since changed the if-statment to: if 1.0 - tolerance <= abs(l1.UnitTangent * l2.UnitTangent) <= 1.0 + tolerance:
The reasoning is that I don’t need the normal vector that the three-dimensional cross product provides and the dot product theoretically requires 4 operations less to be calculated.
Anyway, without looking at the docs I guess the IsParallelTo method does something similar, because its return values looks suspiciously like what the vector dot product of two normal vectors spits out.
double angle_tol = RhinoMath.ToRadians(1.0); // or whatever
double parallel_tol = Math.Cos(angle_tol);
if ( Math.Abs(lineA.UnitTangent * lineB.UnitTangent) >= parallel_tol )
{
// lines are almost parallel
//... do whatever you think is appropriate
}
i.e., compare the dot product of two unit vectors against the cosine of the angle tolerance. It’s very close to what you are doing too, but this way there is a physical value that explains the tolerance number.
There are probably a few ways to make that use the fewest number of floating point operations but I’m not sure it’s worth caring about 3 or 4 extra multiplications.
The right-hand side comparison is not needed here, if you find a dot product of two unit vectors that is bigger than 1.0 + tolerance, there’s a big bug somewhere.
