Intersecting Line Segments
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:
- Test for parallelity, return False if parallel.
- If Not parallel, calc intersection points of the 2 lines. (Call it 5)
- 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
- Else return True.
Is there a more optimal strategy?
Re: Intersecting Line Segments
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!
Re: Intersecting Line Segments
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:
VB Code:
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:
VB Code:
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.
:wave:
Re: Intersecting Line Segments
THANK YOU NotLKH YOUR POST TOTALLY SOLVED MY PROBLEM!!!!
1 Attachment(s)
Re: Intersecting Line Segments
Your Quite Welcome!
:wave:
cough, reputation, cough
Re: Intersecting Line Segments
I had converted it to VB.NET but not realized that shared points were being considered.
Thanks again.