Intersecting Line Segments

[NotLKH]

I'm down to the final step of a progie of mine, just have to build an intersection test.


Whats the best way to determine if 2 line segments intersect.

I figure, given 2 line segments, 1-2, 3-4:

1. Test for parallelity, return False if parallel.
2. If Not parallel, calc intersection points of the 2 lines. (Call it 5)
3. Return False if one or more of the following distance comparisons are true:
   
   
   • 5 to 1 > 1 to 2
   • 5 to 2 > 1 to 2
   • 5 to 3 > 3 to 4
   • 5 to 4 > 3 to 4
4. Else return True.

Is there a more optimal strategy?

[wossname]

Sure, use counter-clockwise testing...

This algorithm has the 2 functions you require...

http://support.microsoft.com/default...;EN-US;q121960

You'll have to translate it into your language of choice, its not difficult though. You need the "CCW" (CounterClockWise) and "Intersect" functions. The code is tiny and very fast.

Its a brilliant article actually. Well worth reading the whole algorithm, I learned a lot from it.

NOTE: You'll have to use IE to view that page because it doesn't come out right in FireFox, that's MS for ya!

[NotLKH]

Thanks Woss!

I added a little extra, because in my progie, if an endpoint is shared between two line segments, then its considered non-intersecting.

s0, this is what it turned out to be:

Public Function ARE_PTS_EQUAL(ByRef mPt1 As pt, ByRef mPt2 As pt) As Boolean
    If (mPt1.mX = mPt2.mX) And (mPt1.mY = mPt2.mY) Then
        ARE_PTS_EQUAL = True
    Else
        ARE_PTS_EQUAL = False
    End If
End Function
Public Function MS_INTERSECT(ByRef mPt1 As pt, ByRef mPt2 As pt, ByRef mPt3 As pt, ByRef mPt4 As pt) As Boolean
    If ARE_PTS_EQUAL(mPt1, mPt3) Or ARE_PTS_EQUAL(mPt1, mPt4) Or ARE_PTS_EQUAL(mPt2, mPt3) Or ARE_PTS_EQUAL(mPt2, mPt4) Then
        MS_INTERSECT = False
    Else
        MS_INTERSECT = ((CCW(mPt1, mPt2, mPt3) * CCW(mPt1, mPt2, mPt4)) <= 0) And ((CCW(mPt3, mPt4, mPt1) * CCW(mPt3, mPt4, mPt2)) <= 0)
    End If
End Function
Public Function CCW(ByRef mPt0 As pt, ByRef mPt1 As pt, ByRef mPt2 As pt) As Integer
    Dim dX1 As Long
    Dim dX2 As Long
    Dim dY1 As Long
    Dim dY2 As Long
 
    dX1 = mPt1.mX - mPt0.mX
    dX2 = mPt2.mX - mPt0.mX
    dY1 = mPt1.mY - mPt0.mY
    dY2 = mPt2.mY - mPt0.mY
 
    If (dX1 * dY2 > dY1 * dX2) Then
      CCW = 1
    Else
      CCW = -1
    End If
End Function

Much nicer than what I had designed.
I actually have something similar to CCW:

Public Function SIGN_OF_SIDE(ByRef tPt As pt, ByRef mPt1 As pt, ByRef mPt2 As pt) As Integer
    Dim MyOut As Double
    MyOut = (tPt.mY - mPt1.mY) * (mPt2.mX - mPt1.mX) - (tPt.mX - mPt1.mX) * (mPt2.mY - mPt1.mY)
    SIGN_OF_SIDE = Sgn(MyOut)
End Function

and using that instead of CCW returns identical results for the intersection test.

So, Now I've got a Mesh Generator!
I'm trying to eventually make a contour mapper.

[cpatzer]

THANK YOU NotLKH YOUR POST TOTALLY SOLVED MY PROBLEM!!!!

[NotLKH]

Your Quite Welcome!


cough, reputation, cough

[cpatzer]

I had converted it to VB.NET but not realized that shared points were being considered.

Thanks again.