Code archives/Algorithms/Line-Bezier Intersect Demo
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
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
| ||
Nice one, thanks. |
Code Archives Forum