How to calculate if a dot lies on a line

Posted on 2006-04-11
Last Modified: 2010-04-17
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.

 |                      .
 |                  .    B
 |                  C
 |     .

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.
    LVL 85

    Assisted Solution

    by:Mike Tomlinson
    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")
                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)
                ' 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
    LVL 85

    Expert Comment

    by:Mike Tomlinson
    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".
    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).


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


    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
    LVL 25

    Expert Comment

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

    Expert Comment

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

    As you can see here:

    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).
    LVL 2

    Accepted Solution

      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...

    Author Comment


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

    LVL 25

    Expert Comment

    Cheers, Celia.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Enabling OSINT in Activity Based Intelligence

    Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

    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…

    779 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    14 Experts available now in Live!

    Get 1:1 Help Now