. Thanks to Paul Bourke for the code, and thanks to IdeasVacuum for pointing to that website here on the forum.
My code is a corrected and extended version. The original code returns wrong results for examples
above. And it always returns only 1 point as result, whereas I decided to return 2 points as result if applicable, in order not to lose any information.
Code: Select all
EnableExplicit
#Epsilon = 0.000001
Structure PointD
x.d
y.d
EndStructure
Macro IsBetween (_x_, _a_, _b_)
; Is _x_ between _a_ and _b_?
; It doesn't matter whether _a_ is the minimum and _b_ is the maximum, or vice versa.
(((_a_) <= (_x_) And (_x_) <= (_b_)) Or ((_b_) <= (_x_) And (_x_) <= (_a_)))
EndMacro
Procedure.i Intersect_Segments (*p1.PointD, *p2.PointD, *p3.PointD, *p4.PointD,
*ps1.PointD, *ps2.PointD, checkLines.i=#False)
; -- Determine the intersection of two lines or two line segments (in 2 dimensions).
; in : *p1, *p2 : points on line a or segment a
; *p3, *p4 : points on line b or segment b
; checkLines: #True for checking the intersection of two lines,
; #False for checking the intersection of two segments.
; out: *ps1 : intersection point (if existing), or
; *ps1, *ps2 : endpoints of overlapping part of the segments (if existing)
; return value: 0 if there is no intersection point
; 1 if there is exactly one intersection point
; 2 if the segments overlap (more than one point)
; -1 if the lines are coincident
;
; [http://www.purebasic.fr/english/viewtopic.php?f=12&t=53070]
Protected.d numera, numerb, denom, mua, mub
Protected.i ret=0
numera = (*p4\x-*p3\x)*(*p1\y-*p3\y) - (*p4\y-*p3\y)*(*p1\x-*p3\x)
numerb = (*p2\x-*p1\x)*(*p1\y-*p3\y) - (*p2\y-*p1\y)*(*p1\x-*p3\x)
denom = (*p4\y-*p3\y)*(*p2\x-*p1\x) - (*p4\x-*p3\x)*(*p2\y-*p1\y)
If Abs(denom) >= #Epsilon ; if the lines are not parallel
mua = numera / denom
mub = numerb / denom
If checkLines Or
(mua >= 0.0 And mua <= 1.0 And mub >= 0.0 And mub <= 1.0) ; if the intersection is along the segments
*ps1\x = *p1\x + mua * (*p2\x-*p1\x)
*ps1\y = *p1\y + mua * (*p2\y-*p1\y)
ProcedureReturn 1
Else
ProcedureReturn 0
EndIf
ElseIf Abs(numera) < #Epsilon And Abs(numerb) < #Epsilon ; if the lines are coincident
If checkLines
ProcedureReturn -1
Else ; do the segments share one or more points?
If IsBetween(*p1\x, *p3\x, *p4\x) And IsBetween(*p1\y, *p3\y, *p4\y)
*ps1\x = *p1\x
*ps1\y = *p1\y
ret + 1
EndIf
If IsBetween(*p3\x, *p1\x, *p2\x) And IsBetween(*p3\y, *p1\y, *p2\y)
If ret = 0
*ps1\x = *p3\x
*ps1\y = *p3\y
ret + 1
ElseIf *ps1\x <> *p3\x Or *ps1\y <> *p3\y
*ps2\x = *p3\x
*ps2\y = *p3\y
ret + 1
EndIf
EndIf
If IsBetween(*p2\x, *p3\x, *p4\x) And IsBetween(*p2\y, *p3\y, *p4\y)
If ret = 0
*ps1\x = *p2\x
*ps1\y = *p2\y
ret + 1
ElseIf ret = 1 And (*ps1\x <> *p2\x Or *ps1\y <> *p2\y)
*ps2\x = *p2\x
*ps2\y = *p2\y
ret + 1
EndIf
EndIf
If IsBetween(*p4\x, *p1\x, *p2\x) And IsBetween(*p4\y, *p1\y, *p2\y)
If ret = 1 And (*ps1\x <> *p4\x Or *ps1\y <> *p4\y)
*ps2\x = *p4\x
*ps2\y = *p4\y
ret + 1
EndIf
EndIf
ProcedureReturn ret ; 0, 1, or 2
EndIf
Else ; if the lines are parallel, but not coincident
ProcedureReturn 0
EndIf
EndProcedure
CompilerIf #PB_Compiler_IsMainFile
; -- Demo
Macro ShowResult (_label_, _expected_result_, _checkLines_=#False)
Debug _label_ + ":"
count = Intersect_Segments(p1, p2, p3, p4, ps1, ps2, _checkLines_)
If count <> _expected_result_
Debug "ERROR: count = " + count
EndIf
If count = 0
Debug "no intersection"
ElseIf count = -1
Debug "coincident"
Else
Debug "(" + StrD(ps1\x,2) + ", " + StrD(ps1\y,2) + ")"
If count = 2
Debug "(" + StrD(ps2\x,2) + ", " + StrD(ps2\y,2) + ")"
EndIf
EndIf
EndMacro
Define.PointD p1, p2, p3, p4, ps1, ps2
Define.i count
; Example a: The lines and the segments intersect.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 1.5 : p3\y = 1.0
p4\x = 3.0 : p4\y = 4.0
Debug "* Example a *"
ShowResult("Lines", 1, #True)
ShowResult("Segments", 1)
Debug "---------------"
; Example b: The lines intersect;
; the segments do not intersect.
p1\x = 1.0 : p1\y = 3.0
p2\x = 1.8 : p2\y = 2.5
p3\x = 1.5 : p3\y = 1.0
p4\x = 3.0 : p4\y = 4.0
Debug "* Example b *"
ShowResult("Lines", 1, #True)
ShowResult("Segments", 0)
Debug "---------------"
; Example c: The lines intersect;
; an end point of one segment is on the other segment.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 2.0 : p3\y = 2.5
p4\x = 3.0 : p4\y = 4.0
Debug "* Example c *"
ShowResult("Lines", 1, #True)
ShowResult("Segments", 1)
Debug "---------------"
; Example d: The lines intersect;
; an end point of one segment is on the other line,
; but not on the other segment.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 4.0 : p3\y = 1.5
p4\x = 3.0 : p4\y = 4.0
Debug "* Example d *"
ShowResult("Lines", 1, #True)
ShowResult("Segments", 0)
Debug "---------------"
; Example e: The lines are parallel.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 2.0 : p3\y = 4.0
p4\x = 4.0 : p4\y = 3.0
Debug "* Example e *"
ShowResult("Lines", 0, #True)
ShowResult("Segments", 0)
Debug "---------------"
; Example f: The lines are coincident;
; the segments are not in contact.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 4.0 : p3\y = 1.5
p4\x = 5.0 : p4\y = 1.0
Debug "* Example f *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 0)
Debug "---------------"
; Example g: The lines are coincident;
; the segments share one end point.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 3.0 : p3\y = 2.0
p4\x = 5.0 : p4\y = 1.0
Debug "* Example g *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 1)
Debug "---------------"
; Example h: The lines are coincident;
; the segments share multiple points.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 2.0 : p3\y = 2.5
p4\x = 5.0 : p4\y = 1.0
Debug "* Example h *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 2)
Debug "---------------"
; Example i: The lines are coincident;
; one segment contains the other segment.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 0.5 : p3\y = 3.25
p4\x = 5.0 : p4\y = 1.0
Debug "* Example i *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 2)
Debug "---------------"
; Example j: The lines and the segments are coincident.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 1.0 : p3\y = 3.0
p4\x = 3.0 : p4\y = 2.0
Debug "* Example j *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 2)
CompilerEndIf
