3
$\begingroup$

I have implemented line segments intersetion test and at the very same test I want to include the fact that if two line segments overlap each other partially or fully , it will be flagged as no intersection.

Some hint to it would be great to have!

$\endgroup$
  • $\begingroup$ It would be helpful to see your code in this question to make the post self-contained. I'll add an answer that refers to your code but it will make more sense if the code is visible in the question. $\endgroup$ – trichoplax Apr 30 '16 at 0:52
1
$\begingroup$

The first step in your existing code calculates the orientations of one line segment relative to each of the two end points of the other line segment, using the cross product. This allows testing whether the other line segment has one end point anticlockwise and the other end point clockwise from the first line segment, indicating that the line on which the first segment lies cuts the other segment.

Rather than writing a new test, you can use these same orientations to test for line segments that overlap (including partial overlap). If both segments lie on the same line, then all four orientations calculated in your first step will be zero, because none of the end points are either clockwise or anticlockwise from the line, since they are on the line. Then it remains only to check whether the two segments on the same line overlap, by checking whether either of them has an end point between the end points of the other segment.

$\endgroup$
0
$\begingroup$

If you're working in 2D, it should be enough to just take the dot product of the normals of the lines and if it is -1 or 1 then the lines are parallel, and either don't overlap or fully overlap. 2 lines cannot "partially overlap". They either meet at a single point, at every point, or no points.

$\endgroup$
  • 1
    $\begingroup$ Two lines cannot partially overlap, but two line segments can. $\endgroup$ – trichoplax Apr 30 '16 at 0:42
  • $\begingroup$ Ah, good point. I was thinking infinite lines. I'll update when I have a minute. $\endgroup$ – user1118321 Apr 30 '16 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.