Problem with the function Curve.Intersect(Curve)

[BenoitE&A]

Hi all,

I have a problem when I use this function with 2 lines intersecting each other in the case where they are parallel. See code below.

            XYZ pt1 = new XYZ();
            XYZ pt2 = new XYZ(1, 0, 0);
            XYZ pt3 = new XYZ(-1, 0, 0);

                     
            SetComparisonResult scr = Line.CreateBound(pt1, pt2).Intersect(Line.CreateBound(pt1, pt3), out IntersectionResultArray ira);
            if (scr == SetComparisonResult.Overlap)
                monMessage += "\n Case 1 overlap" + DonneXYZ(ira.get_Item(0).XYZPoint);
            if (scr == SetComparisonResult.Disjoint)
                monMessage += "\n Case 1 disjoint";
            if (scr != SetComparisonResult.Overlap && scr != SetComparisonResult.Disjoint)
                monMessage += "\n Case 1 problem";

This returns the Case 1 problem (not overlap, not disjoint).

If the 2 lines are not parallel to each other the result is overlap (correct)

            XYZ pt4 = new XYZ(0, 1, 0);
            SetComparisonResult scr2 = Line.CreateBound(pt1, pt2).Intersect(Line.CreateBound(pt1, pt4), out IntersectionResultArray ira2);
            if (scr2 == SetComparisonResult.Overlap)
                monMessage += "\n Case 2 overlap" + DonneXYZ(ira2.get_Item(0).XYZPoint);
            if (scr2 == SetComparisonResult.Disjoint)
                monMessage += "\n Case 2 disjoint";
            if (scr2 != SetComparisonResult.Overlap && scr != SetComparisonResult.Disjoint)
                monMessage += "\n Case 2 problem";

I also tried to get a curve with tangent parallel with the other curve :

            Arc myArc = Arc.Create(new XYZ(0, 1, 0), 1.0, -0.5 * Math.PI, 0.0, XYZ.BasisX, XYZ.BasisY);
            SetComparisonResult scr3 = myArc.Intersect(Line.CreateBound(pt1, pt3), out IntersectionResultArray ira3);
            if (scr3 == SetComparisonResult.Overlap)
                monMessage += "\n Case 2 overlap "+DonneXYZ(ira3.get_Item(0).XYZPoint);
            if (scr3 == SetComparisonResult.Disjoint)
                monMessage += "\n Case 2 disjoint";
            if (scr3 != SetComparisonResult.Overlap && scr != SetComparisonResult.Disjoint)
                monMessage += "\n Case 2 problem";

And the result is correct (overlap).

So it appears that the only incorrect result is when you have 2 parallel lines.

But it is a mess in my code (unexpected errors that I have to deal with) so if this could be fixed if would be great!

Benoit

[jeremytammik]

Dear Benoit,

Thank you for your report.

Your source code is more readable if you add it using the 'Insert Code' button '<i>'.

So, you say that you have a problem with the intersection of two parallel lines?

Point P = (-1,0,0)
Point O = (0,0,0)
Point Q = (0,0,+1)
Line A from P to O
Line B from O to Q

These two lines have one single common point in (0,0,0).

Whether that is to be considered an intersection depends completely on your point of view.

If the lines are considered as closed sets of points in space, they intersect in one point.

If they are considered as open sets in space, they do not intersect.

Both of these way of looking at geometrical elements are completely valid.

Mathematically speaking, you can consider this equivalent question:

Question: Do the two intervals [-1,0] and [0,1] intersect?

Answer: The two closed intervals [-1,0] and [0,1] do intersect, in one single point 0. The intersection is infinitesimally small and has a volume of zero. The two open intervals (-1,0) and (0,1) do not intersect. There is also no intersection between the two intervals if one of them is open and the second closed.

These cases can only be distinguished precisely using exact arithmetic:

https://stackoverflow.com/questions/24352127/exact-arithmetic-in-c

https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

The Revit API, just like most other current geometrical programming environments, does not specify which paradigm is considered valid.

In fact, it cannot, because it does not work with exact arithmetic.

As long as we are working with imprecise double precision floating point numbers, these two cases cannot be distinguished.

The line A is considered totally equivalent to the line

Line4 A' from P to (-0.000000000000000000001,0,0)

The only way I see for you to handle your problem properly is to perform a fuzzy comparison of the edge cases such as these, cf.:

http://thebuildingcoder.typepad.com/blog/2017/06/sensors-bim-ai-revitlookup-and-fuzzy-comparison.htm...

I would say that this is not a bug, and there is no way to decide whether parallel lines that meet in one single point intersect or not.

Any such attempt would be completely pointless  🙂

Your software needs to be implemented in a way that takes this possibility into account.

Exact comparison would be required to answer this precisely.

This is definitely not possible using floating point arithmetic.

I hope this clarifies.

Best regards,

Jeremy

[BenoitE&A]

Hey Jeremy,

Your explainations are interesting. Still the bottom of the problem remains:

- the way this subject is coded in Revit makes the results of very similar intersection problems non consistant. 

Case 1 : intersection between [(0,0) ; (1,0)] and [(0,0) ; (-1,0)] returns neither overlap nor disjoint

Case 2 : intersection between [(0,0) ; (1,0)] and [(0,0) ; (0,1)] returns overlap 

Case 3 : intersection between [(0,0) ; (1,0)] and the arc of center (0,10E9) and of radius 10E9 ending in (0,0) (which is locally a Line) returns overlap. 

- this problem arises only for Line which are parallel, not for the other types of Curves.

As I explained, this rises unexpected errors which should be avoided and can be difficult to find. So I believe the Curve.intersect method should be updated on this particular point. Except if there is a better argument not to do so...

Benoit

[jeremytammik · Accepted solution]

Dear Benoit,

Thank you for your update.

As you can tell, I find the topic interesting and really want to help find a satisfactory solution.

If this only applies to parallel lines, I would suggest solving it for that case, because it is not hard to do.

I added IsParallel and IsCollinear predicates to The Building Coder samples for this:

  public static bool IsParallel( XYZ p, XYZ q )
  {
    return p.CrossProduct( q ).IsZeroLength();
  }

  public static bool IsCollinear( Line a, Line b )
  {
    XYZ v = a.Direction;
    XYZ w = b.Origin - a.Origin;
    return IsParallel( v, b.Direction )
      && IsParallel( v, w );
  }

Next step would be to check for the overlap including the required fuzziness in case lines are collinear..

However, I will also discuss with the development team whether they agree with you and the official API intersection functionality should take this into account as well.

Best regards,

Jeremy

[BenoitE&A]

Thanks Jeremy, I have indeed solved the problem for myself (once you have found it, not difficult...).

Benoit

[jeremytammik]

Care to share? Thank you!

[jeremytammik]

Dear Benoit,

The development team replies regarding the return value:

I believe the documentation covers this case and the return is "Subset":

http://www.revitapidocs.com/2018.1/3310a68d-b67a-79cb-ea54-deb00d9f60d9.htm

SetComparisonResult.Subset - The inputs are parallel lines with only one common intersection point, or the curve used to invoke the intersection check is a line entirely within the unbound line passed as argument curve. If the former, the output argument has the details of the intersection point

The customer didn't indicate what the return value was for them; if it is subset, that matches what we have told them it would be.

Best regards,

Jeremy

[jeremytammik]

Published for posterity:

http://thebuildingcoder.typepad.com/blog/2017/12/project-identifier-and-fuzzy-comparison.html#3

Benoit, I added a new little question for you in there, by the way  🙂

Cheers,

Jeremy

[BenoitE&A]

Hey Jeremy,

Thanks for the reply. 

Indeed this answer (SetcomparisonResult.Subset) works for my problem and is much more elegant than my previous solution (which was in essence : check if SetComparisonResult is either Overlap or Disjoint, and if it is not, check if the 2 elements are line, are colinear and have same end. If so, do as if the case was Overlap).

Now it gives : 

if (scr != SetComparisonResult.Overlap && scr != SetComparisonResult.Disjoint && (scr!=SetComparisonResult.Subset && ira.Size==1)){bla bla bla}

And that's it!!

Bye.

Benoit

[BenoitE&A]

Little mistake...

This is better.

if (scr != SetComparisonResult.Overlap && scr != SetComparisonResult.Disjoint && !(scr==SetComparisonResult.Subset && ira.Size==1))

[jeremytammik]

Dear Benoit,

Thank you for your update, appreciation, confirmation and sample snippet, which I added to the post.

Cheers,

Jeremy