Add homogeneous intersection functions

[ianmackenzie]

• [ ] Axis2d.intersectionPoint : Axis2d -> Axis2d -> Maybe Point2d
• [ ] Plane3d.intersectionAxis : Plane3d -> Plane3d -> Maybe Axis3d
• [x] LineSegment2d.intersectionPoint : LineSegment2d -> LineSegment2d -> Maybe Point2d
• [ ] Triangle3d.intersectionLineSegment : Triangle3d -> Triangle3d -> Maybe LineSegment3d

[mpizenberg]

Hi, I mentionned last time in elm discuss that I had some addition to LineSegment2d and it was for the intersection so glad to see that it was already planned :). The interface I implemented though is a bit different. What I did was with this interface:

type RelativePosition
    = Parallel
    | Collinear
    | Intersection Point2d
    | NonIntersection Point2d

relativeTo : LineSegment2d -> LineSegment2d -> RelativePosition

It includes your interface by saying Intersection Point2d is equivalent to Just Point2d and the rest is equivalent to Nothing. So if you don't like the additional stuff, I can definitely simplify my implementation. Or keep it private and implement the intersection function on top of it.

[ianmackenzie]

Does your current implementation use any kind of tolerance, or (for example) are line segments only considered to be parallel if they have exactly the same direction? I suspect in many cases if you care about checking for parallel or collinear line segments you will want to do so within a tolerance, but exactly how that tolerance should be defined is not clear to me (especially for collinearity). How was your client code (the code using your interface) using the various cases of the union type?

Oh, and it couldn't be called relativeTo, in OpenSolid that name is taken =) Perhaps something like classify?

[mpizenberg]

Good point, currently only exact parallelism is taken into account (same for collinearity). I guess another function with an angle tolerance would make sense, but also make the computation a little heavier since cross product would not be enough. A normalization would be required to have reliable angle thresholds.

I confess, for now my only use of relativeTo was in the polygon self intersection algorithm. And it only searched for intersection:

eventIntersection : Event -> Event -> Maybe Point2d
eventIntersection ( id1, _, seg1 ) ( id2, _, seg2 ) =
    if cyclicDistance id1 id2 <= 1 then
        Nothing
    else
        case LineSegment2d.relativeTo seg1 seg2 of
            LineSegment2d.Intersection point ->
                Just point

            _ ->
                Nothing

The reason I implemented a more complete type was

1. Because I think this union type is more specific and explicit than a Maybe
2. Because anyway the computation process of intersection gave me those informations

PS: in my code I actually used relationshipWith instead of relativeTo for the name of the function, but here I thought, since we say "what is the relative position of two lines?", it felt right to call this relativeTo (espacially in the context of piping)

[ianmackenzie]

LineSegment2d.intersectionPoint implemented in #17.