[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

How to calculate if a dot lies on a line

Posted on 2006-04-11
9
Medium Priority
?
269 Views
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.

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

0
Comment
Question by:swansonplace
9 Comments
 
LVL 9

Assisted Solution

by:gabeso
gabeso earned 500 total points
ID: 16427885
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 86

Assisted Solution

by:Mike Tomlinson
Mike Tomlinson earned 500 total points
ID: 16428606
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
 
LVL 86

Expert Comment

by:Mike Tomlinson
ID: 16428681
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 25

Assisted Solution

by:InteractiveMind
InteractiveMind earned 500 total points
ID: 16430162
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

by:InteractiveMind
ID: 16430282
You may want to get the 'absolute' (modulus) value of the distance, before comparison ...
0
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 16430418
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

by:
RNMcLean earned 500 total points
ID: 16433191
  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
 

Author Comment

by:swansonplace
ID: 16453537
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

by:InteractiveMind
ID: 16453646
Cheers, Celia.
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
If you are a mobile app developer and especially develop hybrid mobile apps then these 4 mistakes you must avoid for hybrid app development to be the more genuine app developer.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…
Starting up a Project

834 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