Line-Bezier Intersect Demo

This code has been declared by its author to be Public Domain code.

Line-Bezier Intersect Demo by Andy_A

2006

Check for intersection between Line Segment and Bezier Curve

As noted in the code, change the number of Bezier line segments to be plotted to a high number (approx. 5000 - 10,000) for highest accuracy. Though when plotting so many line segments you may get more than one set of coordinates for the point of intersection. This is due to the mathematics being more accurate than the graphics.

If you want a fast check just use 8-10 line segments. It won't be absolutely correct but should suffice for most purposes.

Instructions:
Press a key to generate random line segments and Bezier curves.
Press [ESC] to exit.

;Line Segment/Bezier Curve Intersect Demo
;  	By: Andy Amaya
; Date: Nov 07, 2006

AppTitle "Line-Bezier Intersection Demo by Andy_A"
Graphics 800,600,32,2
SetBuffer BackBuffer()

;set high for accuracy, set low for speed
numBezierPoints% = 5000

Dim p%(numBezierPoints + 1,3), result%(numBezierPoints + 1)
Global intersectX%, intersectY%, n%
SeedRnd MilliSecs()


While KeyHit(1) = 0
	Cls
	x1% = Rand(175,799) : y1% = Rand(60,599)
	x2% = Rand(175,799) : y2% = Rand(60,599)
	Color 0,0,255
	Line(x1,y1, x2,y2)

	x3% = Rand(175,799) : y3% = Rand(60,599)
	x4% = Rand(175,799) : y4% = Rand(60,599)
	x5% = Rand(175,799) : y5% = Rand(60,599)
	x6% = Rand(175,799) : y6% = Rand(60,599)

	Color 255,255,0
	bezier(x3,y3, x4,y4, x5,y5, x6,y6, numBezierPoints)

	lineCount% = 0
	For j% = 0 To n%
		result(j) = linesIntersect(x1,y1, x2,y2, p(j,0),p(j,1), p(j,2),p(j,3) )
		If result(j)=1 Then
			lineCount = lineCount+1
			Color 0,255,0
			Text(130,lineCount*14,"X,Y="+Str(intersectX)+","+Str(intersectY))	
			Text(5,lineCount*14,"Segment "+Str(j)+"="+Str(result(j) ) )
		End If
	Next

	Flip
	WaitKey()
Wend
End

;Source: http://Local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
;Intersection point of two lines
;(2 dimensions)

Function linesIntersect(x1%,y1%, x2%,y2%, x3%,y3%, x4%,y4%)

    numeratorA#  = (x4-x3)*(y1-y3)-(y4-y3)*(x1-x3)
    numeratorB#  = (x2-x1)*(y1-y3)-(y2-y1)*(x1-x3)
    denominator# = (y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)

    If denominator = 0.0 Then
;        Text(10,20,"No intersection")
;        If numeratorA = 0.0 And numeratorB = 0.0 And denominator = 0.0 Then
;            Text(10,40,"Lines are coincident")
;        Else
;            Text(10,40,"Lines are parallel")
;        End If
        Return False
    Else
        Ua# = numeratorA/denominator
        Ub# = numeratorB/denominator
        range1% = Ua >= 0.0 And Ua <= 1.0
        range2% = Ub >= 0.0 And Ub <= 1.0
        If range1 And range2 Then
			intersectX% = Floor(x1 + Ua*(x2-x1)+.5)
			intersectY% = Floor(y1 + Ua*(y2-y1)+.5)

			;highlight point of intersection
			Color 255,0,0
			Oval intersectX-3, intersectY-3, 7, 7, True

			Return True
		Else
;			Text(10,20,"No intersection")
			Return False
		End If
	End If
End Function

;Source:   http://www.wikipedia.org/wiki/Bezier_curve
;The parametric form of the curve is:
;P(t) = A(1 - t)3 + 3Bt(1 - t)2 + 3Ct2(1 - t) + Dt3    Where 0.0 <= t <= 1.0
Function bezier (x0%, y0%, x1%, y1%, x2%, y2%, x3%, y3%, rate%)

	xt# = 1.0 / rate    ;rate = number of line segments defining Bezier curve
	xp# = 1.0 - xi#

	tmpX1# = x0
	tmpY1# = y0
	n%=0
	While xi < 1.0
		xi# = xi# + xt#
		xp# = 1.0 - xi#
		
		xp2# = xp# * xp#
		xi2# = xi# * xi#

		t1# = xp2# * xp#
		t2# = xp2# * xi# * 3.0
		t3# = xi2# * xp# * 3.0
		t4# = xi2# * xi#
		tmpX2# = (t1 * x0) + (t2 * x1) + (t3 * x2) + (t4 * x3)
		tmpY2# = (t1 * y0) + (t2 * y1) + (t3 * y2) + (t4 * y3)

		;Store these points defining line segment to be drawn
		;they will be used in testing for intersection		
		p(n,0)=tmpX1
		p(n,1)=tmpY1
		p(n,2)=tmpX2
		p(n,3)=tmpY2
		;count number of line seg coords to store
		n=n+1
		
		Line tmpX1, tmpY1, tmpX2, tmpY2
		tmpX1 = tmpX2
		tmpY1 = tmpY2
	Wend
End Function

Comments

BlitzSupport

2006

Nice one, thanks.

Code Archives Forum