Point on Line Segment

Archives Forums/BlitzPlus Programming/Point on Line Segment

starfox(Posted 2003) [#1]
Does any one know any code to see if a point is on a line segment?

thanks!


elias_t(Posted 2003) [#2]
Try here:

http://astronomy.swin.edu.au/~pbourke/geometry/


EOF(Posted 2003) [#3]
Not sure whose function but I think this will do the trick:
format_code('; ===========================
; 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')


fredborg(Posted 2003) [#4]
This should do the trick. Set radius to the tickness of the line.

format_code('
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


Oldefoxx(Posted 2003) [#5]
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.


Oldefoxx(Posted 2003) [#6]
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).


BlitzSupport(Posted 2003) [#7]
This should do it, though it's maybe too precise for any practical use...?

format_code('
; -------------------------------------------------------
; 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
')


Oldefoxx(Posted 2003) [#8]
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 ...


BlitzSupport(Posted 2003) [#9]
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...

format_code('
; 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
')


Oldefoxx(Posted 2003) [#10]
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.