PureBasic Forumhttps://www.purebasic.fr/english/ Intersection of two line segmentshttps://www.purebasic.fr/english/viewtopic.php?f=12&t=53070 Page 1 of 1

 Author: Little John [ Thu Jan 24, 2013 3:42 pm ] Post subject: Intersection of two line segments Hi,calculating the intersection of two (infinite) lines or (finite) line segments is a problem which is pretty easy to understand, and so seems simple at the first glance. However, some special cases have to be taken into account, and "out there on the internet" I saw code that did not do so properly. In order to realize some typical cases, firstly I show several figures. These figures give the expected results, so that we can check whether the results of our code are correct.If you are only interested in the code, go directly to the second post.//Edit 2016-05-21:Extended the above text.Extended figure b.Changed the captions of the figures.     Fig. a                                                                                                     Fig. bThe lines and the segments intersect.                                                     The lines intersect;                                                                                                             the segments do not intersect.     Fig. c                                                                                                    Fig. dThe lines intersect;                                                                                The lines intersect;an end point of one segment is on the other segment.                             an end point of one segment is on the other line,                                                                                                             but not on the other segment.     Fig. e                                                                                                    Fig. fThe lines are parallel.                                                                            The lines are coincident,                                                                                                             the segments are not in contact.     Fig. g                                                                                                     Fig. hThe lines are coincident;                                                                        The lines are coincident;the segments share one end point.                                                          the segments share multiple points.     Fig. i                                                                                                     Fig. jThe lines are coincident;                                                                        The lines and the segments are coincident.one segment contains the other segment.The figures were created with the excellent open source program GeoGebra.

 Author: Little John [ Thu Jan 24, 2013 3:43 pm ] Post subject: Re: Intersection of two line segments Works also with PB 5.20The following procedure is based on C code from http://paulbourke.net/geometry/pointlineplane/. 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 f and g 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.See also Intersection of two circles.//Edit 2016-05-21:Changed the parameters that take the output (no linked list needed anymore).By means of the new optional parameter 'checkLines', now it's not only possible to check the intersection of two (finite) line segments, but also of two (infinite) lines.Code:EnableExplicit#Epsilon = 0.000001Structure PointD   x.d   y.dEndStructureMacro 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_)))EndMacroProcedure.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   EndIfEndProcedureCompilerIf #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

 Author: eddy [ Thu Jan 24, 2013 3:57 pm ] Post subject: Re: Intersection of two line segments HiIs it fast enough for sprite polygon collision ?

 Author: Little John [ Thu Jan 24, 2013 3:58 pm ] Post subject: Re: Intersection of two line segments eddy wrote:HiIs it fast enough for sprite polygon collision ?Hi,I don't know. Please test yourself. Regards, Little John

 Author: luis [ Thu Jan 24, 2013 4:29 pm ] Post subject: Re: Intersection of two line segments Nice, thank you

 Author: STARGÅTE [ Thu Jan 24, 2013 4:30 pm ] Post subject: Re: Intersection of two line segments eddy wrote:HiIs it fast enough for sprite polygon collision ?Little John code is for line-line-collision, a polygon is a surface, there you check whether a point is in the triangle.Or you mean a polyline?@Little John: line-line-collision is ok, but have you a code for check bézier curve collision?

 Author: Little John [ Thu Jan 24, 2013 5:30 pm ] Post subject: Re: Intersection of two line segments STARGÅTE wrote:@Little John: line-line-collision is ok, but have you a code for check bézier curve collision?I don't have such code, sorry.

 Author: eddy [ Thu Jan 24, 2013 5:35 pm ] Post subject: Re: Intersection of two line segments Sorry I meant polyline.

 Author: IceSoft [ Thu Jan 24, 2013 5:53 pm ] Post subject: Re: Intersection of two line segments You should use the Chipmunk4PB wrapper for collision detection.

 Author: said [ Fri Jan 25, 2013 8:24 pm ] Post subject: Re: Intersection of two line segments Interesting, thanks for sharing and for the link

 Author: mestnyi [ Sun Dec 21, 2014 11:31 am ] Post subject: Re: Intersection of two line segments http://www.purebasic.fr/english/viewtopic.php?f=12&t=43460&p=458232#p458232

 Author: Little John [ Fri May 20, 2016 11:22 pm ] Post subject: Re: Intersection of two line segments Code extended and slightly improved.For details see 1st and 2nd post.

 Page 1 of 1 All times are UTC + 1 hour Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Grouphttp://www.phpbb.com/