0

I have a class LineSegment with a function called bool LineSegment::intersect(LineSegment &otherLineSegment, Point &intersectionPoint, bool continuous=false). I added the continuous parameter since I was too lazy to inherit from my LineSegment class to create a Line class (or vice versa). What this argument does is basically make it possible to check for intersection between two line segments both as line segment but also as if these are lines (that is they span infinitely in both directions). intersectionPoint holds the intersection point between the two objects if intersect(...) returns true.

  • The first case covers the situation where we need to know if two line segments really intersect or not.
  • The second case covers the situation where even though two line segments don't intersect we still need to know if - in case we view these two line segments as part of two lines - an intersection occurs somewhere.

For the purpose of doing this check I use the algorithms provided here (for line intersection) and here (for line segment intersection).

The problem I'm having is when I have two coinsiding line segments which means that there are infinite number of intersections between the two. For example let's take the line segment l1(Point(0, 1), Point(1, 1)) and l2(Point(-1, 1), Point(2, 1)). If we visualize both we get

[Point(-1, 1)------[(0, 1)------(1, 1)]------Point(2, 1)]

A continuous check (that is if line intersect) returns true (with the intersection point being Point(2, 1) which isn't even part of l2 and directly contradicts the property of an intersection point that it can be calculated using the equation for either one of the lines/line segments) in this case while line segment intersection returns false.

How do I handle this situation? I can of course check for both and if I get such a mismatch I can say "Well, you have coinciding lines". However this doesn't help me further since:

  • Double-checking is expensive and has to be done for every pair of line segments I want
  • Overlapping means that there are infinite points of intersection (of course this is not the case when working with machine floating point numbers since (due to storage and accuracy) we have a limited (but still big enough) set of numbers in that interval). This is obviously is impossible to handle so an exception has to be made

On the other hand I can also not just let this be and create undefined or incorrect behaviour in my code. A possible solution would be to check for the angle between two vectors (each part of the respective line/line segment) and if the angle is 0 or very, very close to it (to handle rounding errors) the lines coincide. This still doesn't help me in determining what to do with this information?

Community
  • 1
  • 1
rbaleksandar
  • 8,713
  • 7
  • 76
  • 161
  • Someone perhaps can help you with efficiently determining whether two lines or line segments coincide. No one can tell you what to do with the resulting information. – n. m. could be an AI Nov 08 '16 at 15:28
  • I meant how is such information usually handled when working with line and line segment intersections? There should be some general practice for this case...or am I wrong? – rbaleksandar Nov 08 '16 at 15:30
  • No, it depends on what your application is doing. If you want to prevent the user from creating coinciding lines, you inform the user and cancel new line creation. If you e.g. compute the intersection of two 2D polygons you have to know that two lines coincide *and* the entire segment where they coincide (i.e. one point is not enough). – n. m. could be an AI Nov 08 '16 at 15:55
  • You can return code instead of boolean. For true segment intersection, for line intersection, for parallel lines, for coincide and so on. – MBo Nov 08 '16 at 17:16

0 Answers0