STABEL Line Line Intersection 2D/3D

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

STABEL Line Line Intersection 2D/3D

Post by D.J.Peters »

file: "LineLine.bi"

Code: Select all

#ifndef __LinLine_bi__
#define __LinLine_bi__

#include "string.bi"

type tReal as double

const as tReal EPS = 0.000001

function strReal(byref v as const tReal) as string
  const as string FMT = "0.000000"
  var r = format(v,FMT)
  var n = len(r)
  if n then
    for i as integer = 0 to n-1
      if r[i]=asc(",") then r[i]=asc("."):exit for
    next
  end if
  return r
end function 


type Vector2
  declare operator cast as string
  as tReal x,y
end type
operator Vector2 . cast as string 
  return "[" & strReal(x) & ", " & strReal(y) & "]"
end operator

type Vector3
  declare operator cast as string
  as tReal x,y,z
end type
operator Vector3 . cast as string 
  return "[" & strReal(x) & ", " & strReal(y) & ", " & strReal(z) & "]"
end operator

type Line2
  declare operator cast as string
  as Vector2 a,b
end type
operator Line2 . cast as string
  return a & " - " & b
end operator

type Line3
  declare operator cast as string
  as Vector3 a,b
end type
operator Line3 . cast as string
  return a & " - " & b
end operator

function LineLineIntersect2D(byref l1 as const Line2, _
                             byref l2 as const Line2, _
                             byref p as Vector2) as boolean
  
  var y10 = l1.b.y - l1.a.y
  'if y10=0 then return false
  var y32 = l2.b.y - l2.a.y   
  'if y32=0 then return false
    
  var x23 = l2.a.x - l2.b.x      
  var x01 = l1.a.x - l1.b.x      
  var d = y10*x23 - y32*x01
  if d = 0 then return false
  var x10 = l1.b.x - l1.a.x
  if x10=0 then return false
  var x32 = l2.b.x - l2.a.x
  if x32=0 then return false


  var C1 = y10*l1.a.x + x01*l1.a.y
  var C2 = y32*l2.a.x + x23*l2.a.y
  var PX = (x23*C1 - x01*C2)/d
  var PY = (y10*C2 - y32*C1)/d
  var tx0 = (PX - l1.a.x)/x10
  var ty0 = (PY - l1.a.y)/y10
  var tx1 = (PX - l2.a.x)/x32
  var ty1 = (PY - l2.a.y)/y32
  if (((tx0 >= 0 andalso tx0 <= 1) orelse (ty0 >= 0 andalso ty0 <= 1)) _
      andalso _
      ((tx1 >= 0 andalso tx1 <= 1) orelse (ty1 >= 0 andalso ty1 <= 1))) then
    p.x = PX
    p.y = PY
    return true
  end if
  return false
end function



function LineLineIntersect3D(byref l1 as const Line3, _
                             byref l2 as const Line3, _
                             byref s  as Line3, _
                             byref t1 as tReal, byref t2 as tReal) as boolean
 
  dim as Vector3 dif=any,l1dir=any,l2dir=any
  dim as tReal l1dot=any,l2dot=any,dot=any,ldl1dot=any,ldl2dot=any
  dim as tReal numerator=any,denominator=any
  ' Line1 direction
  l1dir.x = l1.b.x - l1.a.x
  l1dir.y = l1.b.y - l1.a.y
  l1dir.z = l1.b.z - l1.a.z
  if (abs(l1dir.x) < EPS andalso abs(l1dir.y) < EPS andalso abs(l1dir.z) < EPS) then return false
  ' Line2 direction
  l2dir.x = l2.b.x - l2.a.x
  l2dir.y = l2.b.y - l2.a.y
  l2dir.z = l2.b.z - l2.a.z
  if (abs(l2dir.x) < EPS andalso abs(l2dir.y) < EPS andalso abs(l2dir.z) < EPS) then return false
  ' Line1 Line2 difference
  dif.x = l1.a.x - l2.a.x
  dif.y = l1.a.y - l2.a.y
  dif.z = l1.a.z - l2.a.z
  ' DOT(Line1 direction)
  l1dot = l1dir.x*l1dir.x + l1dir.y*l1dir.y + l1dir.z*l1dir.z
  ' DOT(Line2 direction)
  l2dot = l2dir.x*l2dir.x + l2dir.y*l2dir.y + l2dir.z*l2dir.z
  ' DOT(Line1 direction,Line2 direction)
  dot = l1dir.x*l2dir.x + l1dir.y*l2dir.y + l1dir.z*l2dir.z
  ' denominator 
  denominator = l1dot*l2dot - dot*dot
  if abs(denominator) < EPS then return false
  ' DOT(Line difference, Line1 direction)
  ldl1dot = dif.x*l1dir.x + dif.y*l1dir.y + dif.z*l1dir.z
  ' DOT(Line difference, Line2 direction)
  ldl2dot = dif.x*l2dir.x + dif.y*l2dir.y + dif.z*l2dir.z
  ' numerator
  numerator = ldl2dot*dot - ldl1dot*l2dot

  t1 = numerator/denominator
  s.a.x = l1.a.x + l1dir.x*t1
  s.a.y = l1.a.y + l1dir.y*t1
  s.a.z = l1.a.z + l1dir.z*t1
 
  t2 = (ldl2dot + dot*t1)/l2dot
  s.b.x = l2.a.x + l2dir.x*t2
  s.b.y = l2.a.y + l2dir.y*t2
  s.b.z = l2.a.z + l2dir.z*t2
 
  return true
end function

#endif ' __LinLine_bi__
file: "LineLineTest2D.bas"

Code: Select all

#include once "LineLine.bi"

Dim As Line2 LineA, LineB
dim as integer mx,my,ox,oy

LineA.a.x=100
LineA.a.y=240
LineA.b.x=500
LineA.b.y=240

LineB.a.x=0
LineB.a.y=0
LineB.b.x=639
LineB.b.y=479

dim as Vector2 p
dim as tReal   t

screenres 640,480,32
windowtitle "move the mouse"

Line (LineA.a.x, LineA.a.y) - (LineA.b.x, LineA.b.y), RGB(255,0,0)
Line (LineB.a.x, LineB.a.y) - (LineB.b.x, LineB.b.y), RGB(0,255,0)

while inkey()=""

  if GetMouse(mx,my)=0 andalso (mx<>oy orelse my<>oy) then
    cls
    ox=mx:oy=my
    LineB.b.x=mx :LineB.b.y=my
    Line (LineA.a.x, LineA.a.y) - (LineA.b.x, LineA.b.y), RGB(255,0,0)
    Line (LineB.a.x, LineB.a.y) - (LineB.b.x, LineB.b.y), RGB(0,255,0)
    If LineLineIntersect2D(LineA, LineB, p) Then   
      Circle (p.x, p.y), 5, RGB(255,255,0)
    End If
  end if  

  Sleep 10
wend
Last edited by D.J.Peters on Oct 22, 2021 23:33, edited 1 time in total.
UEZ
Posts: 972
Joined: May 05, 2017 19:59
Location: Germany

Re: STABEL Line Line Intersection 2D/3D

Post by UEZ »

Thanks for sharing. :-)

I don't know if I understood it correctly but

Code: Select all

...
Dim As Line2 LineA, LineB, Segment
Dim As tReal t1, t2

LineA.a.x=100
LineA.a.y=100
LineA.b.x=200
LineA.b.y=100
LineB.a.x=50
LineB.a.y=50
LineB.b.x=250
LineB.b.y=100

Print "Line A " & LineA
Print "Line B " & LineB
If LineLineIntersect(LineA, LineB, Segment, t1, t2) Then
	Print "t1,t2 " & strReal(t1),strReal(t2)
	Print "segment " & Segment
	Print
	Screen 18, 32

	Line (LineA.a.x, LineA.a.y) - (LineA.b.x, LineA.b.y), &hFFFF0000
	Line (LineB.a.x, LineB.a.y) - (LineB.b.x, LineB.b.y), &hFF00FF00
	Circle (Segment.a.x, Segment.a.y), 5, &h7FFFFF00
End If
Sleep
LineLineIntersect should return false or?
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Re: STABEL Line Line Intersection 2D/3D

Post by D.J.Peters »

@UEZ you are right I changed the code and added a 2D test (see first post).

Joshy
UEZ
Posts: 972
Joined: May 05, 2017 19:59
Location: Germany

Re: STABEL Line Line Intersection 2D/3D

Post by UEZ »

Now it's ok. Thx.
Post Reply