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

DRAWING

Detect if a line intersects a rectangle


I don't want to bet, but I'm curious to know what the result is. The code below is a little clunky and takes about .02 ticks to do the job. It could be sped up by avoiding the BLOCKOVE statement and using SANE, but at least it gives a ballpark idea of how the algorithm works. Let me know how fast yours was.

'NOTE: This routine assumes that the line extends across the screen. If you have a line
' segment that stops just before intersecting with a rectangle, the routine will
' give an intersection result.
_pt=4
_xx=2
_yy=0

CLEAR LOCAL
  _equalTo=1
  _greaterThan=2
  _lessThan=3
  DIM e.pt(2),v.pt(4),y#,i%,compare%,y%,result%,oldResult%,intersect%
' e stands for endpoint and v stands for vertex.
' Number vertices clockwise starting from the top left corner.
LOCAL FN lineInRect%(endPoint&,rect&)
' copy the endpoint array for easy access
  BLOCKMOVE endPoint&,@e(1),2*_pt
' assign the vertices of the rectangle to points
  CALL SETPT(v(1),rect&.left%,rect&.top%)
  CALL SETPT(v(2),rect&.right%,rect&.top%)
  CALL SETPT(v(3),rect&.right%,rect&.bottom%)
  CALL SETPT(v(4),rect&.left%,rect&.bottom%)
  FOR i%=1 TO 4
    oldResult%=result%
    y#=(e.yy%(2)-e.yy%(1))/(e.xx%(2)-e.xx%(1))*(v.xx%(i%)-e.xx%(1))+e.yy%(1)
    y%=v.yy%(i%)
    SELECT
      CASE y#>y% : result%=_greaterThan
      CASE y#<y% : result%=_lessThan
      CASE y#=y% : result%=_equalTo : intersect%=_true : i%=4
    END SELECT
    LONG IF i%>1
      LONG IF result%<>oldResult%
        intersect%=_true
        i%=4
      END IF
    END IF
  NEXT i%
END FN=intersect%

CLEAR LOCAL
  DIM endPt.pt(2),intersect%,startTime&,finishTime&,i%
LOCAL FN CallRoutine(x1,y1,x2,y2,rect&,numCalls%)
  CLS
  CALL SETPT(endPt(1),x1,y1)
  CALL SETPT(endPt(2),x2,y2)
  CALL MOVETO(endPt.xx%(1),endPt.yy%(1))
  CALL LINETO(endPt.xx%(2),endPt.yy%(2))
  CALL FRAMERECT(#rect&)
  startTime&=FN TICKCOUNT
  FOR i%=1 TO numCalls%
    intersect%=FN lineInRect(@endPt(1),rect&)
  NEXT i%
  finishTime&=FN TICKCOUNT
  PRINT
  SELECT intersect%
    CASE _true: PRINT "The line INTERSECTS the rectangle."
    CASE _false: PRINT "The line DOES NOT INTERSECT the rectangle."
  END SELECT
  PRINT "Routine called";numCalls%;"times."
  PRINT "Start time:";startTime&
  PRINT "Finish time:";finishTime&
  PRINT "Time elapsed: ";finishTime&-startTime&;" ticks."
  PRINT "Press any key."
  DO
  UNTIL LEN(INKEY$)
END FN

CLEAR LOCAL
  DIM rect.8
LOCAL FN PassValues
  WINDOW #1,"",(0,30)-(SYSTEM(_scrnWidth),SYSTEM(_scrnHeight))
  CALL SETRECT(rect,100,100,200,200)
  FN CallRoutine(10,10,250,250,@rect,1)
  FN CallRoutine(200,10,300,300,@rect,1)
  FN CallRoutine(200,10,300,300,@rect,100)
END FN

CLS
FN PassValues
DO
UNTIL LEN(INKEY$)

wave


Okay, no bet. I ran your code on my machine and it's faster than I expected. While my code is not an order of magnitude better, it is 30 percent faster. Your program took about 43-46 ticks to run (after I altered it to draw 500 random lines) whereas, my program took 30 ticks to about the same thing. However, please keep in mind that my program draws double lines and other such cute stuff to show what's happening and that takes time. Also, my program handles all forms of lines. In other words, there are no special exception cases.

I'll do better than tell you how fast/good it is, I'll provide you with the code.

This program is an example of how one can get the toolbox calls to do some of the work for you. It is better/faster to use QuickDraw functions over your own code (when and wherever possible). There is a lot of power in those calls.

Here's the code:

'--------- line in region demo - should run "as is" ---

COMPILE 0, _dimmedVarsOnly
DIM gRectRgn&
DIM gCount&
DIM gCount2&

END GLOBALS

'===========================
'---------------------- set up the window ----------------------
'===========================

LOCAL FN StartUp
  WINDOW OFF
  WINDOW 1, "Line in region demo",(0,0)-(600,500),_docNoGrow
  COORDINATE WINDOW
  gCount& = 0
  gCount2& = 0
END FN

'===========================
'------------------- init the test region ----------------------
'===========================

LOCAL FN initRgn
  DIM x0,x1,y0,y1
  DIM testRect.8

'------------- make a rectangle a region ------------
  x0 = 100
  y0 = 50
  x1 = x0 + 200
  y1 = y0 + 200

  COLOR = _zBlue
  gRectRgn& = FN NEWRGN 'get rect region
  CALL SETRECT(testRect,x0,y0,x1,y1) 'set the rect
  CALL RECTRGN(gRectRgn&,testRect) 'convert rect to region
  CALL CLOSERGN(gRectRgn&) 'close
  CALL PENSIZE(4,4)
  CALL FRAMERGN(gRectRgn&) 'frame
  CALL PENNORMAL

END FN

'===========================
'-------------------- demo lines in rrect ----------------------
'===========================

LOCAL FN demo(x,y,dx,dy)
  DIM x0,y0,x1,y1
  DIM rectRgn&
  DIM testRect.8
  DIM lineRgn&
  DIM dest1Rgn&

'-------------------- draw the line -----------------
' make the line 3 pixels wide to be able to see it.

  COLOR _zBlack
  CALL MOVETO(x,y)
  CALL LINETO (x+dx,y+dy)
  CALL LINETO(x-3,y)
  CALL LINETO(x,y)

'------- draw the line in a region structure --------
  lineRgn& = FN NEWRGN 'get line region
  CALL OPENRGN
  CALL MOVETO(x,y)
  CALL LINETO (x+dx,y+dy)
  CALL LINETO (x+dx-3,y+dy)
  CALL LINETO(x-3,y)
  CALL LINETO(x,y)
  CALL CLOSERGN(lineRgn&) 'close

'------------ create an empty region (dest1) ---------
  dest1Rgn& = FN NEWRGN 'get dest1 region
  CALL OPENRGN
  CALL CLOSERGN(dest1Rgn&) 'close

'--- get the difference between the line and rect ----
  CALL SECTRGN(gRectRgn&,lineRgn&,dest1Rgn&)

'--- check to see if the region is empty (no hit) ----
  LONG IF FN EMPTYRGN(dest1Rgn&)
    INC(gCount&) 'if no intersection then
    increment
  END IF

'-------------- paint the difference red --------------

  COLOR _zRed
  CALL PAINTRGN(dest1Rgn&)

'--------------- dispose of regions ------------------

  CALL DISPOSERGN(lineRgn&) 'dispose
  CALL DISPOSERGN(dest1Rgn&) 'dispose

END FN

'===========================
'--------------------- do breaks -------------------------------
'===========================

LOCAL FN doBreak
  END
END FN

'===========================
'-------------------------- main -------------------------------
'===========================

DIM a$, i
DIM x,y,dx,dy
DIM start&, finish&

FN StartUp
FN initRgn

start& = FN TICKCOUNT

FOR i = 1 TO 500
  x = RND(400)
  y = RND(200)
  dx = RND(100)
  dy = RND(100)
  FN demo(x,y,dx,dy)
  INC(gCount2&)
NEXT

finish& = FN TICKCOUNT

COLOR = _zBlack
CALL MOVETO (0,400)
PRINT gCount2& ;" lines with ";gCount2&-gCount&;" hits in
";finish&-start&;" ticks."
PRINT
PRINT "This includes the time to draw the lines and to compute random x & y's."
PRINT
INPUT "Press any key to end...";a$

CALL DISPOSERGN(gRectRgn&) 'dispose last region

END