Point on Line Segment
BlitzPlus Forums/BlitzPlus Programming/Point on Line Segment
| ||
| Does any one know any code to see if a point is on a line segment? thanks! |
| ||
| Try here: http://astronomy.swin.edu.au/~pbourke/geometry/ |
| ||
Not sure whose function but I think this will do the trick:; =========================== ; Constants/Functions ; =========================== Const w=640 , h=480 Const pgup=201 , pgdown=209 Graphics w,h SetBuffer BackBuffer() x1=225 : y1=170 : x2=400 : y2=356 ClsColor 80,80,80 ;=========================== ; Main Loop ;=========================== While Not KeyHit(1) Cls x=MouseX() : y=MouseY() Color 96,96,96 : Line x1,y1,x2,y2 Color 0,255,0 : Oval x1,y1,2,2,0 : Oval x2,y2,2,2,0 Color 255,255,255 Line x-10,y-10,x+10,y+10 Line x+10,y-10,x-10,y+10 Color 240,20,160 result=Between(x,y,x1,y1,x2,y2) Text 10,30,"Between Result="+Str$(result) Flip Wend End ; Is an object at x#,y# between two coordinate pairs? ; Returns 1 if YES otherwise 0 Function Between(x#,y#,x1#,y1#,x2#,y2#) dx#=x2-x : dy#=y2-y : dl#=Sqr(dx*dx+dy*dy) tx#=x1-x : ty#=y1-y : tl#=Sqr(tx*tx+ty*ty) Return (dx/dl)*(tx/tl)+(dy/dl)*(ty/tl)<-.99 End Function |
| ||
This should do the trick. Set radius to the tickness of the line.Function IsOnLine(px#,py#,ax#,ay#,bx#,by#,radius#=1.5) Local vx#,vy#,wx#,wy#,c1#,c2#,bb#,dd# vx# = bx - ax vy# = by - ay wx# = px - ax wy# = py - ay c1# = wx*vx + wy*vy If c1 <= 0 If ((px-ax)^2+(py-ay)^2)=>(radius^2) Then Return False End If c2# = vx*vx + vy*vy If c2<=c1 If ((px-bx)^2+(py-by)^2)=>(radius^2) Then Return False End If bb# = c1 / c2 If Sqr((ax + (bb*vx)-px)^2 + (ay + (bb*vy)-py)^2)<radius Then Return True End Function Fredborg |
| ||
| Here is a way to do it: First, suppose the line has coordinates (x1,y1) and (x2,y2), and that the point you are interested in is at (x3,y3). If the point is somewhere along the path of the line, then it must fit between the pairs (x1,y1) and (x2,y2). If it doesn't then you are not on the same line (although if the line were extended, it might still cross your point). So, for the first test, you want to know of x3 is between x1 and x2. Then you want to know if y3 is between y1 and y2. Only if both those answers are true would it be possible to tell if the point lies in the vicinity of the line. But wait, that isn't enough. The coordinates (x1,y1) and (x2,y2) not only detail a straight line, but they are also the coordinates for a rectangle that could be constructed with the opposite end points at those locations. In other words, all we have extablished so far is that the point lies within the rectangle formed between those end points. This would only be a line if the points were either vertical or horizontal to each other. So next we check to see if x1=x2 or y1=y2. If so, then it is a straight line and we have a match. But the line is not vertical or horizontal, so now we want to see if the slope of a line constructed between (x3,y3) and (x1,y1) matches the slope of a line constructed between (x1,y1) and (x2,y2). We saved this step for last for two reasons: (1) It involves division, which is slower than just comparing values to each other, and (2) with division we have to be careful not to divide by zero, so some additional checks are required, What we are looking at is that if two lines have the same slope (ratio between their respective X and Y coordinates), and share the same end point, and the other end point lies somewhere this side of the far endpoint, then the shorter line is a subpart of the longer line, and the points along both lines where they coincide are points on the other line as well. So how would this whole thing look? online=false if x3>=x1 and x2<=x2 or x3<=x1 and x3>=x2 then ;has to be within the right area if y3>=y1 and y3<=y2 or y3<=y1 and y3>=y2 then ;now we are in the same rectangle or line if x1=x2 or y1=y2 then ;vertical or horizontal line, so yes! online=true elseif x1=x3 and y1=y3 or x2=x3 and y2=y3 then ;lies right on an end point, so still yes! online=true elseif (x1-x3)/(y1-y3) = (x1-x2)/(y1-y2) then ;okay we have a slope match, so yes! online=true elseif (x2-x3)/(y2-y3) = (x1-x2)/(y1-y2) then ;okay, we check the slope facing the other way online=true ;in case we were pointed wrong! endif endif endif And that should do it. Now if you want to get rid of the divides, you can transpose the equations by taking the divisors across the equal signs and performing multiplies instead. If you do this, then it is unnecessary to test to avoid division by zero. That code would look like this: if (x1-x3)*(y1-y2) = (x1-x2)*(y1-y3) then ;okay we have a slope match, so yes! online=true elseif (x2-x3)*(y1-y2) = (x1-x2)*(y2-y3) then ;okay, we check the slope facing the other way online=true ;in case we were pointed wrong! endif So if you really reason it out a bit, the problem can be a lot easier to solve than you expected. |
| ||
| I decided to complete my X-Y 2D Graoh program and post it on this site in the Code Archives (look under 2D Graphics). The code is way overkill for the question you asked, but I think it will help you understand things better. You are describing a point and line relationship, whereas in its present incarnation, my program is concerned with two lines and whether they intersect. The Slope form above actually takes less work overall, but you can consider all the points in your situation as representing lines, even a triangle. That is, you start with the LINE (x1,y,x2,y2) and the PLOT(x3,y3) Now to find if the point X3.y3) is on the line between (x1,y1) and (x2,y2), you can construct the additional lines of (z1,y1) to (x2,y2) and (x2,y2) to (x3,y3). That gives you three straight lines and three equations to derive and play with using Cramer's Rule, or matrix arithmetic. But there is a simpler way: Use the Distance formula, which is D=SQR((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)). Of course for x1, x2, y1, and y2, you would substitute x3 and y3 as necessary. If you end up with a result that D1=D2+D3, where D1 is the longest side, then you know that the point (x3,y3) must lie on the line (x1,y2,x2,y2) because if it did not, then D1 would always be less than D2+D3. That is because the distance along any two sides of a triangle is always longer than the length of the third side. Aside from the Slope solution indicated above, you can think about describing one or two more lines: The line (x1,y2,x3,y3) and the line (x2,y2,x3,y3). You can then derive the equations for either or both of these lines, and using Cramer's Rule, determine the X and Y intersect points). |
| ||
This should do it, though it's maybe too precise for any practical use...?
; -------------------------------------------------------
; Graphics Gems is your friend!
; -------------------------------------------------------
; www.graphicsgems.org/
; -------------------------------------------------------
; -------------------------------------------------------
; PointOnLine () - returns True if point is on the line.
; -------------------------------------------------------
; x and y are the co-ords of the point to check; px, py,
; qx, qy define the line...
; -------------------------------------------------------
Function PointOnLine (x, y, px, py, qx, qy)
If ((px = qx) And (py = qy))
If ((x = px) And (y = py))
Return 2
Else
Return 0
EndIf
EndIf
If (Abs ((qy - py) * (x - px) - (y - py) * (qx - px)) => (Max (Abs (qx - px), Abs (qy - py)))) Then Return 0
If (x < px) Or (x > qx) Or (y < py) Or (y > qy) Then Return 0
Return True
End Function
; -------------------------------------------------------
; Used by above function...
; -------------------------------------------------------
Function Max (a, b)
If a > b Then Return a Else Return b
End Function
; -------------------------------------------------------
; D E M O . . .
; -------------------------------------------------------
Graphics 640, 480, 0, 2
SetBuffer BackBuffer ()
Repeat
Cls
Line 100, 100, 400, 300
If PointOnLine (MouseX (), MouseY (), 100, 100, 400, 300)
Text 20, 20, "On the line!"
EndIf
Flip
Until KeyHit (1)
End
|
| ||
| I had a final thought about using the distance formula for checking to see if a point lies on a line. It is\ true that a point lies on a straight line if and only if D1=D2+D3, but it also holds that the following would be true as well: D2^2=D2^2+D3^2. Now working backwards with the distance formula, instead of taking the square roots of D1, D2, and D3, you could just check the outcome of the parftial results before using the Sqr() function: (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) ==> D1 (squared length) (x2-x3)*(x2-x3)+(y2-y3)*(y2-y3) ==> D2 (squared length) (x1-x3)*(x1-x3)+(y1-y3)*(y2-y3) ==> D3 (squared length) And if D1=D2+D3, then (x3,y3) lies on the line (x1,y2,x2,y2) There are three basic ways to try to speed up programs: (1) fewer computations, (2) faster computations, and (3) more efficient computations. Using integers and integer arithmetic instead of floating point calculations can vastly speed up calculations, and the tradeoffs in numerical accuracy may be acceptable. Avoiding division and most trig and log/power functions will also help (this includes the Sqr() function). And assigning temporary results that will be used more than once to a variable, then using the variable instead of doing the computation again, can also help. The rethink of using the distance formula above avoided three unnecessary calls to Sqr(), which helps. Another example is using some temporary variables in the distance formula: t1=x1-x2 t2=y1-y2 D1=t1*t1+t2*t2 t1=x1-x3 t1=y1-y3 D2=t1*t1+t2*t2 t1=x2-x3 t2=y2-y3 D3=t1*t1+t2*t2 if D1=D2+D3 then ... Note that since positive or negative numbers, times themselves, always give a positive result, and the sum of positive numbers is always positive, so you do not have to use Abs() anywhere here before checking the results. Also note that this process calls for an extremely close result for D1, D2, and D3 to get a good result, and in some cases the round off or truncated results with integers will be slightly wide of the mark. You can accomodate some slight variation if you do the following instead: If Abs(D1-D2-D3)<2 then ... |
| ||
Pointless, but I had a brainwave for another way to do it -- check the angles between x0/y0 and y0/y1, compared to x0/y0 and the point you're testing...; Approximately on line (could use some checks for x/y ; being < or > the given points)... Graphics 640, 480, 0, 2 SetBuffer BackBuffer () x0 = 100 y0 = 300 x1 = 400 y1 = 100 Repeat Cls x2 = MouseX () y2 = MouseY () Color 255, 255, 255 Line x0, y0, x1, y1 Color 255, 0, 0 Line x0, y0, x2, y2 ang1 = ATan2 (y1 - y0, x1 - x0) ang2 = ATan2 (y2 - y0, x2 - x0) Color 255, 255, 255 Text 20, 20, "Angle (white) : " + ang1 Text 20, 40, "Angle (red) : " + ang2 If ang1 = ang2 Text 20, 80, "On the line!" EndIf Flip Until MouseHit (1) End |
| ||
| Concerning pointless: The angle of Y/X is the Tangent (Tan) of the line. If you remember your trig, as you approach the vertical and X gets smaller, the result of Y/X becomes very large. When X becomes zero, the result use to be defined as infinite, but now I understand it is just considered undefined. That means you have to have a separate check to make sure that X is not zero, and have a different expression if it is. That, plus the fact that Y/X involves division, a much slower process than using multiplication, means two strikes against this approach. But many people use it, simply because it is sort of self-evident if you are familiar with any graphing at all. You might recall that parallel lines have the same slope, and if they have the same C value, as in Y=mX+C, then they lie along the same line. But again, you have a situation where the length of the line is assumed to be infinite, and yet the point will not be on the line if it lies beyond the lines given end points. The distance approach resolves all those issues pretty well. |
   |