I have two segments that are on the same line. Each segment is defined by a start and end vector. I need to find the segment of their overlap, if there is any. I can think of an inefficient way of doing it, by creating a plane with the normal of the line with its position at one of the segment endpoints, and doing distance checking with a lot of if statements. But there must be a simpler way of doing it, keeping in mind the segments are definitely on the same line. Anyone know? This is for triangle-triangle collision I''m implementing, using this approach. ~CGameProgrammer( );

If the start of one segment is less than the start of the second segment, then this first segment is the segment furthest to the left.

Now, if the start of the second segment is less than the end of the first segment (the segment farthest to the left), then they are overlapping. Also, if the difference between the start of the first segment and the end of the second segment is less than the length of the sum of the two segments, then they are overlapping.

Beginners and experts will find answers here.

given segments (v1, v2) and (v3, v4)

1. Compute line vector v = v2 - v1
pick a non-zero coordinate of v
e.g. if v = (0,1,0) then pick the y coordinate
2. without loss of generality assume the x coordinate is chosen
if( v1.x > v2.x ) swap v1, v2
if( v3.x > v4.x ) swap v3, v4
vA = (v1.x > v3.x ? v1 : v3 );
vB = (v2.x < v4.x ? v2 : v4 );
if( vA.x < vB.x ) return vA, vB --- overlapped segment
otherwise, no overlap!

If the segments are on the same line, they intersect if and only if the axis-aligned bounding boxes for the segments intersect. The intersection volume of the two AABBs tightly encapsulates the overlapping part of the two segments, and directly determines this subsegment. In other words, all you need to do is a couple of min/max operations. Incredibly simple.

Christer Ericson
Sony Computer Entertainment, Santa Monica

Despite Christer Ericson''s advice which seems perfectly suited, I feel compelled to add my two cents.

Knowing they are on a straight line, you can reduce the vectors down to one scalar e.g.

(v1,v2) ,(v3,v4)=>
(0,|(v2-v1)|),(|(v3-v1)|,|(v4-v1)|)

Then it only takes two (or 4 if the vertices are unordered) comparisons to work out intersection. I''m not sure, this looks faster than AABB to me, and would leave neater code (except for if the box overlap was done with an external function which is more than likely).

On the minus side, it does absolutly require the points to be co-linear, or else it would behave rather oddly.

quote:

---

Original post by sadwanmage
Despite Christer Ericson''s advice which seems perfectly suited, I feel compelled to add my two cents.

Knowing they are on a straight line, you can reduce the vectors down to one scalar e.g.

(v1,v2) ,(v3,v4)=>
(0,|(v2-v1)|),(|(v3-v1)|,|(v4-v1)|)

Then it only takes two (or 4 if the vertices are unordered) comparisons to work out intersection. I''m not sure, this looks faster than AABB to me, and would leave neater code (except for if the box overlap was done with an external function which is more than likely).

On the minus side, it does absolutly require the points to be co-linear, or else it would behave rather oddly.

---

The lines are colinear because they are both segments on the intersection of two planes, which is a line. Your idea is good, though modified -- getting the magnitude of the two vectors is worse than several comparisons because sqrt() is very slow. However your method would work perfectly well using the dot product of each vector with itself -- magnitude squared.

~CGameProgrammer( );

Convert both segments to parametric form, i.e.

 X = Mt + B  

X, M and B are vectors. M and B should be the same for both segments. Now it is just a matter of finding the overlap of the t values of the endpoints.