Line Segment Intersection

[Nexus100]

Hi People that can do maths

Please help...

I need an line segment intersection routine, I have tried several and they either fail all the time, fail part of the time (ie. one line is vertical or horizontal) but generally do not succeed?

I am writing an application that allows the user to draw 2D planes of a shop front opening. For example there may be several planes at varying angles (these angles are of a limited range) but of course cannot intersect.....I just cannot get it to work other than get all the points from the 'new line' and check them against all the (plotted) points of the previous lines...this gets really too slow as we add more lines of course.....

I need a robust procedure that i send the coords of two lines and returns true or false on intersection!

Many many many thanks in advance!

Merry Christmas

[skywalk]

http://purebasic.fr/english/viewtopic.php?f=13&t=46964

[IdeasVacuum]

Hmm, the issue will be the length of the segments. If they are very tiny, it's difficult to get accurate results.

Try this:

Code: Select all

;Intersection of two lines and/or two line segments
;From C code: Paul Bourke www.paulbourke.net

Global gInsctX.d = 0.00
Global gInsctY.d = 0.00

Procedure LineIntersect(x1.d,y1.d, x2.d,y2.d, x3.d,y3.d, x4.d,y4.d)
;------------------------------------------------------------------
   Define DBL_EPSILON = 0.0001
   Protected mua.d, mub.d,denom.d,numera.d,numerb.d
   Shared gInsctX
   Shared gInsctY

   denom  = (y4-y3) * (x2-x1) - (x4-x3) * (y2-y1)
   numera = (x4-x3) * (y1-y3) - (y4-y3) * (x1-x3)
   numerb = (x2-x1) * (y1-y3) - (y2-y1) * (x1-x3)

   ;Are the lines coincident?
   If( (Abs(numera) < DBL_EPSILON) And (Abs(numerb) < DBL_EPSILON) And (Abs(denom) < DBL_EPSILON) )

      gInsctX = (x1 + x2) / 2
      gInsctY = (y1 + y2) / 2

      ProcedureReturn(#True)
   EndIf

   ;Are the lines parallel?
   If (Abs(denom) < EPS)

      gInsctX = 0
      gInsctY = 0
      ProcedureReturn(#False);
   EndIf

   ;Is the intersection along the line segments?
   mua = numera / denom
   mub = numerb / denom
   If (mua < 0 Or mua > 1 Or mub < 0 Or mub > 1)

      gInsctX = 0
      gInsctY = 0
      ProcedureReturn(#False)
   EndIf

   gInsctX = x1 + mua * (x2 - x1)
   gInsctY = y1 + mua * (y2 - y1)

   ProcedureReturn(#True)

EndProcedure

;Test LineA = point 1 to point 2, LineB = point 3 to point 4
PtX1.d = 3.25
PtY1.d = 4.25
PtX2.d = 18.75
PtY2.d = 10.25

PtX3.d = 6.5
PtY3.d = 14.0
PtX4.d = 21.0
PtY4.d = 1.5

Intersection = LineIntersect(PtX1,PtY1, PtX2,PtY2, PtX3,PtY3, PtX4,PtY4)

Debug Intersection  ;True
Debug gInsctX       ;13.298
Debug gInsctY       ; 8.139

[Nexus100]

Hi Ideas Vacuum

Thank you very very very very much...seems to work like a dream!

I have been trying variations of this with very random results....now it provides regular results!

Have a very merry Welsh Xmas!

Jason