Solved

# How to calculate if a dot lies on a line

Posted on 2006-04-11
265 Views
What is the formula to find out if a third dot lies between two points?
I have (x,y) coordinates for positions A and B.  I want to know if postion C is on
the same line that a and b are on.

I thought to use the formula y = mx + b to find the generic formula for the line for the known points A and B. After that plug in the x,y points for C in the line, and
if the line is still true, then line C is in part of the line.  But, I do not know how
to do this mathematically.  Any suggestions.

y
|                      .
|                  .    B
|                  C
|     .
|___A__________________x

0
Question by:swansonplace

LVL 9

Assisted Solution

A(x1,y1) and B(x2,y2) are on a line.

calculate:  (y2-y1)/(x2-x1) - that is the gradent of the line - call it 'm'

then for all points on the line: y=mx+c

so A(x1,y1) is on this line so: y1=m.x1+c so c=y1-(m*x1)

so now you have the equation of the line:

to check c(x3,y3) test: y3=m*x3+c

if it matches then it is on the line.
0

LVL 85

Assisted Solution

I have used this approach with great success:

(it's VB.Net but is easily convertiblel to VB6)

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim endPointA As New Point(0, 0)
Dim endPointB As New Point(3, 3)
Dim somePoint As New Point(1, 1)

Dim dist As Single
dist = Line.PointToLineDist(somePoint.X, somePoint.Y, endPointA.X, endPointA.Y, endPointB.X, endPointB.Y)
If dist = 0 Then
MsgBox("on line")
Else
MsgBox("NOT on line")
End If
End Sub

Public Class Line

Public Shared Function PointToPointDist(ByVal Ax As Single, _
ByVal Ay As Single, ByVal Bx As Single, ByVal By As Single) _
As Single
' PointToPointDist = SquareRoot((Bx - Ax)^2 + (By - Ay)^2)
Return Math.Sqrt((Bx - Ax) * (Bx - Ax) + (By - Ay) * (By - Ay))
End Function

Public Shared Function PointToLineDist( _
ByVal Px As Single, ByVal Py As Single, _
ByVal Ax As Single, ByVal Ay As Single, _
ByVal Bx As Single, ByVal By As Single) As Single
Dim q As Single

If (Ax = Bx) And (Ay = By) Then
' A and B passed in define a point, not a line.
' Point to Point Distance
Return PointToPointDist(Px, Py, Ax, Ay)
Else
' Distance is the length of the line needed to connect the point to
' the(segment)such that the two lines would be perpendicular.

' q is the parameterized value needed to get to the intersection
q = ((Px - Ax) * (Bx - Ax) + (Py - Ay) * (By - Ay)) / _
((Bx - Ax) * (Bx - Ax) + (By - Ay) * (By - Ay))

' Limit q to 0 <= q <= 1
' If q is outside this range then the Point is somewhere past the
' endpoints of our segment.  By setting q = 0 or q = 1 we are
' measuring the actual distacne from the point to one of the
If q < 0 Then q = 0
If q > 1 Then q = 1

' Distance
Return PointToPointDist( _
Px, Py, (1 - q) * Ax + q * Bx, (1 - q) * Ay + q * By)
End If
End Function

End Class
0

LVL 85

Expert Comment

I used this type of function for hit testing the mouse on a line segment so I would test to see if the PointToLineDist() was less than a certain amount (say 3 pixels) and consider that a "hit".
0

LVL 25

Assisted Solution

In my opinion, a slightly quicker way of doing this (whilst also keeping in mind that you may want to allow a small room for error - as ~IM mentioned), is to calculate the distance from A to C, and the distance from C to B. You then add them up, and subtract this value from the distance of A to B, and if it's within a certain threshold limit, then it's a hit (where the treshold would be 0 if you wanted it _exactly_ on the line).

mathematically:

d = sqrt( (Ax-Bx)² + (Ay-By)² ) - [sqrt( (Ax-Cx)² + (Ay-Cy)² ) + sqrt( (Bx-Cx)² + (By-Cy)² )]
IF d <= threshold THEN
"it's a hit !!"
ELSE
"n00b !!"

Programmatically:

if ( sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) ) - ( sqrt( (A.x-C.x)*(A.x-C.x) + (A.y-C.y)*(A.y-C.y) ) + sqrt( (B.x-C.x)*(B.x-C.x) + (B.y-C.y)*(B.y-C.y) ) ) <= threshold )
{
// hit
} else
{
// miss
}
0

LVL 25

Expert Comment

You may want to get the 'absolute' (modulus) value of the distance, before comparison ...
0

LVL 25

Expert Comment

There is a slight disadvantage to my technique however, which I should probably cough up ...

As you can see here:

http://s147645075.websitehome.co.uk/line-hit-errors.jpg

the errors must minimalize as you approach A and B. But as the threshold approaches 0, this effect becomes less significant.. (Somewhere around 0.01 would probably be good).
0

LVL 2

Accepted Solution

The distance of (x0,y0) from the line running through (x1,y1) and (x2,y2) is...

Abs[(y1 - y0)(x2 - x1) - (y2 - y1)(x1 - x0)]
/Sqrt[(x1 - x2)**2 + (y1 - y2)**2]

And you'll get a zero divide only if X1 and X2 coincide, which they surely won't, will they? Watch out for integer overflow if you're using 16-bit integers: dot positions might reach 2,000 so a product might reach 4,000,000 which is rather in excess of 32,768.
If all you're interested in is a hit or not a hit, only the numerator need be computed.
But remember that if you are calculating in terms of dots (pixel positions as integers), whether a dot is lit as being "on" the line is a more delicate issue, as its centre (or lower lh corner, or whatever is taken as the reference location) might be half a dot width from the mathematical line. To see what I mean, get some graph paper and regard each square as a "dot". Draw a line from (0,0) to say (7,5) and then mark those squares you think should constitute the displayed line. Then consider how close to the mathematical line a square can be before being deemed on the line. Some unlit squares might have corners on or over the mathematical line...
0

Author Comment

Hello,

I took a little from each answer.  Each one being a great help.  As a result, I split the points between all.  Wow. Thanks.

Celia
0

LVL 25

Expert Comment

Cheers, Celia.
0

## Featured Post

I know it’s not a new topic to discuss and it has lots of online contents already available over the net. But Then I thought it would be useful to this site’s visitors and can have online repository on vim most commonly used commands. This post h…
Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…