How to calculate if a dot lies on a line

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

swansonplaceAsked:
Who is Participating?
 
RNMcLeanCommented:
  Watch out for vertical lines if your calculation involves a gradient!
   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
 
gabesoSolution ArchitectCommented:
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
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
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
            ' endpoints(instead)
            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
Cloud Class® Course: Microsoft Windows 7 Basic

This introductory course to Windows 7 environment will teach you about working with the Windows operating system. You will learn about basic functions including start menu; the desktop; managing files, folders, and libraries.

 
Mike TomlinsonMiddle School Assistant TeacherCommented:
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
 
InteractiveMindCommented:
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
 
InteractiveMindCommented:
You may want to get the 'absolute' (modulus) value of the distance, before comparison ...
0
 
InteractiveMindCommented:
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
 
swansonplaceAuthor Commented:
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
 
InteractiveMindCommented:
Cheers, Celia.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.