FB II Compiler

PG PRO

Debugging

Memory

System

Mathematics

Resources

Disk I/O

Windows

Controls

Menus

Mouse

Keyboard

Text

Fonts

Drawing

Sound

Clipboard

Printing

Communication

ASM

Made with FB

MATHEMATICS

Find point where two lines cross


Use regions -- page 298-299 of the Handbook.

Two parts:

1. Check to see if the two lines cross. Make each end point of the line one pixel different (wider -- add some thickness to the line). For example, if your line goes from x,y - x1,y1, then make it an region by using (x,y) - (x+1,y+1) - (x1,y1) - (x1+1, y1+1). Do the same for the other line. Then use the two regions in the CALL XORRGN to find if they cross. If the dest& is NOT empty, then the lines cross.

2. If they cross, then find the point where they cross by using the region handle of the dest& region record -- where destH&..BBox.top% ... destH&..BBox.bottom% should be the point.

Using the toolbox is actually faster than using trig computations to find the point.

Tedd

http://www.mhri.edu.au/~pdb/geometry/lineline2d/

A great page with the formulas already there.

Otherwise,

For a line y=mx+b where m is slope (rise over run-> y/x typically) and "b" is the offset from the origin for x, you can solve both lines for various x and y. If they ever equal out, then you have an intersection. But the method on his page can be used more efficiently, and it is set up to do exactly what you want.

Anyone ever needing any computational geometry help and code should bookmark:

http://www.mhri.edu.au/~pdb/ (Great site)
http://www.magic-software.com/ (Great for code of all kinds, including imaging, if you can read C++ and are more math minded)

For file formats of any type:

http://www.mhri.edu.au/~pdb/
http://www.wotsit.org/

For graphics tutorials for rendering, and other:

http://freespace.virgin.net/hugo.elias/
http://www.gameprogrammer.com/

Do not mis-type and go to www.gameprogramming.com, or you will end up somewhere not even remotely related.:)

PS I figured that Tedd would be sending out some region method while I typed this, and darn if I wasn't right!

Robert Covington

Consider (x11,y11) and (x12, y12) to be the end points of Line 1 and (x21,y21), (x22, y22) to be the end points of Line 2 and (x,y) to be the point where they intersect.

Slope of Line 1: m1 = (y12-y11) / (x12-x11)
Slope of Line 2: m2 = (y22-y21) / (x22-x21)
LONG IF m1=m2

   '// lines do not intersect

XELSE

   x = (m1*x11 + m2*x21 - y11 + y21) / (m1 - m2)
   y = y11 + m1*(x - x11)

END IF
You may want to check these calculations yourself:

Slope of Line 1: m1 = (y - y11) / (x - x11) ........ (A)
Slope of Line 2: m2 = (y - y21) / (x - x21) ........ (B)
Chris

Thank you Robert, Chris and Tedd for your help in solving this problem for me. I put together a little demo below incase any one else needs this function.
'-------------
LOCAL FN DrawRoundPt(x,y)
  DIM rect.8                                      'define a rectangle record
  l=x-2:t=y-2:r=x+2:b=y+2
  CALL SETRECT(rect,l,t,r,b)
  CALL PAINTOVAL(rect)
END FN
'-------------
LOCAL FN DrawSqPt(x,y)
  DIM rect.8                                      'define a rectangle record
  l=x-2:t=y-2:r=x+2:b=y+2
  CALL SETRECT(rect,l,t,r,b)
  CALL PAINTRECT(rect)
END FN
'----------
LOCAL FN DrawLine(X1&,Y1&,X2&,Y2&)

  PLOT X1&,Y1& TO X2&,Y2&
  FN DrawRoundPt(X1&,Y1&)
  FN DrawSqPt(X2&,Y2&)
END FN
'----------
LOCAL FN findIntersect(X1&,Y1&,X2&,Y2&,X3&,Y3&,X4&,Y4&,Xptr&,Yptr&,u1Ptr&,u2Ptr&)
  UaTop#=(X4&-X3&)*(Y1&-Y3&)-(Y4&-Y3&)*(X1&-X3&)
  UaBot#=(Y4&-Y3&)*(X2&-X1&)-(X4&-X3&)*(Y2&-Y1&)
  Ua#=UaTop#/UaBot#
  UbTop#=(X2&-X1&)*(Y1&-Y3&)-(Y2&-Y1&)*(X1&-X3&)
  UbBot#=(Y4&-Y3&)*(X2&-X1&)-(X4&-X3&)*(Y2&-Y1&)
  Ub#=UbTop#/UbBot#

  X&=X1&+ Ua#*(X2&-X1&)
  Y&=Y1&+ Ua#*(Y2&-Y1&)

  'return the x and y values
  & Xptr&, X&
  & Yptr&, Y&

  'return the distance between start and end points
  BLOCKMOVE (@Ua#),u1Ptr&,12
  BLOCKMOVE (@Ub#),u2Ptr&,12
END FN
'----------

LOCAL FN drawCircleAroundPts(X&,Y&)
  x=X&:y=Y&
  DIM rect.8
  l=x-3:t=y-3:r=x+4:b=y+4
  CALL SETRECT(rect,l,t,r,b)
  CALL FRAMEOVAL (rect)
  l=x-9:t=y-9:r=x+10:b=y+10
  CALL SETRECT(rect,l,t,r,b)
  CALL FRAMEOVAL (rect)
END FN
'--------------
LOCAL FN IntersectLines(wd,ht)

  'dont draw in scroll bar area
  wd=wd-16:ht=ht-16:H=wd/2

  'create two random lines
  X1&=RND(H):X2&=RND(H)+H:X3&=RND(H):X4&=RND(H)+H
  Y1&=RND(ht):Y2&=RND(ht):Y3&=RND(ht):Y4&=RND(ht)

  'draw the lines
  COLOR _zblack
  FN DrawLine(X1&,Y1&,X2&,Y2&)
  COLOR _zblue
  FN DrawLine(X3&,Y3&,X4&,Y4&)

  'FN findIntersect is the fn that does the work.
  'it returns 4 values
  'X& and Y& are the x and y valuses for the point of intersection
  'U1# and U2# are is the distance between the end points of each line
  'that the lines cross. For example if line 2 crosses line 1
  'half way between the start and end point then U1# will equal .5
  U1ptr&=(@U1#)
  U2ptr&=(@U2#)
  FN findIntersect(X1&,Y1&,X2&,Y2&,X3&,Y3&,X4&,Y4&,@X&,@Y&,U1ptr&,U2ptr&)
  LONG IF U1#<0 OR U1#>1 OR U2#<0 OR U2#>1        'if the lines dont cross
    COLOR _zyellow
  XELSE
    COLOR _zred
  END IF
  FN drawCircleAroundPts(X&,Y&)
END FN
'-----------------------
wd=SYSTEM(_scrnWidth)-20
ht=SYSTEM(_scrnHeight)-60
WINDOW #1,"myWindow",(0,0)-(wd,ht),_doc+_noGoAway
DO
  CLS
  FN IntersectLines(wd,ht)
  COLOR _zblack
  PRINT "If the two lines cross then the intersection point will be circled in red,"
  PRINT "otherwise the circles will be yellow,"
 PRINT
PRINT "Press mouse button to create a new random pair of lines"
  PRINT "Press a keyboard key to quit"
  DO
    x=LEN(INKEY$)
  UNTIL FN BUTTON OR x>0

UNTIL x>0