Detecting coincident subset of two coincident line segments

Question

This question is related to: - How do I determine the intersection point of two lines in GDI+? (great explanation of algebra but no code) - How do you detect where two line segments intersect? (accepted answer doesn't actually work) But note that an interesting sub-problem is completely glossed over in most solutions which just return null for the coincident case even though there are three sub-cases: - coincident but do not overlap - touching just points and coincident - overlap/coincident line sub-segment For example we could design a C# function like this: ``` public static PointF[] Intersection(PointF a1, PointF a2, PointF b1, PointF b2) ``` where (a1,a2) is one line segment and (b1,b2) is another. This function would need to cover all the weird cases that most implementations or explanations gloss over. In order to account for the weirdness of coincident lines, the function could return an array of PointF's: - zero result points (or null) if the lines are parallel or do not inter…

Accepted Answer

Sounds like you have your solution, which is great. I have some suggestions for improving it.

The method has a major usability problem, in that it is very confusing to understand (1) what the parameters going in mean, and (2) what the results coming out mean. Both are little puzzles that you have to figure out if you want to use the method.

I would be more inclined to use the type system to make it much more clear what this method does.

I'd start by defining a type -- perhaps a struct, particularly if it was going to be immutable -- called LineSegment. A LineSegment consists of two PointF structs representing the end point.

Second, I would define an abstract base type "Locus" and derived types EmptyLocus, PointLocus, LineSegmentLocus and perhaps UnionLocus if you need to represent the locus that is the union of two or more loci. An empty locus is just a singleton, a point locus is just a single point, and so on.

Now your method signature becomes much more clear:

```
static Locus Intersect(LineSegment l1, LineSegment l2)
```

This method takes two line segments and computes the locus of points that is their intersection -- either empty, a single point, or a line segment.

Note that you can then generalize this method. Computing the intersection of a line segment with a line segment is tricky, but computing the intersection of a line segment with a point, or a point with a point, or anything with the empty locus is easy. And it's not hard to extend intersection to arbitrary unions of loci. Therefore, you could actually write:

```
static Locus Intersect(Locus l1, Locus l2)
```

And hey, now it becomes clear that Intersect could be an extension method on locus:

```
static Locus Intersect(this Locus l1, Locus l2)
```

Add an implicit conversion from PointF to PointLocus and LineSegment to LineSegmentLocus, and you can say things like

```
var point = new PointF(whatever);
var lineseg = new LineSegment(somepoint, someotherpoint);
var intersection = lineseg.Intersect(point);
if (intersection is EmptyLocus) ...
```

Using the type system well can massively improve the readability of a program.

Detecting coincident subset of two coincident line segments

Solution

Problem

Related problems