# Is a point on a given line?

Hello,

I need to do some math to figure whether a given point is on a given line. With my ideas and searching on various websites, I currently have this code, which works only sometimes:

``````Public Function IsOnALine(Extends pnt As Point, LineStart As Point, LineEnd As Point, Tolerance As Double) as Boolean
if LineStart=nil or LineEnd=nil then Return False

dim d1,d2,d3,x1,x2,x3,xd,y1,y2,y3,yd As Double

//Use the leftmost point for x1
if LineStart.X<=LineEnd.X then
x1= LineStart.X.x
y1= LineStart.X.y
x2=LigneFin.x
y2=LigneFin.y
Else
x1=LigneFin.x
y1=LigneFin.y
x2= LineStart.X.x
y2= LineStart.X.y
end if

if pnt.x<x1 or pnt.y<y1 or pnt.x>x2 or pnt.y>y2 then Return False 'Point is outside of the â€śrectangleâ€ť surrounding the line; no need for more math

//Vertical and horizontal lines will always return true at this point (this avoids dividing by 0):
xd=x2-x1
yd=y2-y1

if xd=0 or yd=0 then Return True

//Now, the "fun" part; the point is inside the rectangle of the non-vertical-nor-horizontal line:
if (LineStart.X.x< LineEnd.x)=(LineStart.X.y< LineEnd.y) then 'An attempt to solve one of my issues (doesn't work when false)
d1=yd/xd 'Divide y delta by x delta (ratio)
Else
d1=xd/yd
end if
d2=y1-x1*d1
d3=pnt.x*d1+d2

Return pnt.y-Tolerance<=d3 and d3<=pnt.y+Tolerance
End Function
``````

This mostly works, as long as both ends have both x and y greater/less than the other end (but not always, I donâ€™t know why).
If one end has x greater than x of the other end and, on the contrary, y is greater for the latter than for the former, the function fails (my attempt with â€śd1=xd/ydâ€ť is about that).

Most results on the Internet arenâ€™t even working, so I finally prefer to ask here. Whatâ€™s wrong with the code above?

Ok, I solved it. Other than an error in earlier portion in my code, which made this method never called for top-right to bottom-left lines, hereâ€™s the working code (in case someone stumble into this issue):

``````Public Function IsOnALine(Extends pnt As Point, LineStart As Point, LineEnd As Point, Tolerance As Double) as Boolean
if LineStart=nil or LineEnd=nil then Return False

dim d1,d2,d3,x1,x2,xd,y1,y2,yd As Double

x1= LineStart.x
y1= LineStart.y
x2= LineEnd.x
y2= LineEnd.y

if pnt.x<min(x1,x2) or pnt.y<min(y1,y2) or pnt.x>max(x1,x2) or pnt.y>max(y1,y2) then Return False

xd=x2-x1
yd=y2-y1

if xd=0 or yd=0 then Return True

d1=yd/xd
d2=y1-x1*d1
d3=pnt.x*d1+d2

Return pnt.y-Tolerance<=d3 and d3<=pnt.y+Tolerance
End Function
``````

I used 1 for tolerance.

would seem that distance of a point from a line would be ideal

a distance of 0 would be â€śits on the lineâ€ť

3 Likes

I see one problem with the way you apply the tolerance in that code.

You are using a vertical tolerance. Letâ€™s assume you set it to 1 (as you mentioned). If the line is horizontal a point that is at a distance of up to 1 from the line will cause your method to return true.

If the line is not horizontal a point that is at a distance of 1 from the line will return false. Letâ€™s take the example of a line with a slope of 45 Âş, and a point at at distance of 1 from the line. The vertical distance from the line to the point is now the square root of 2, which is greater than 1:

The effect gets more significant for higher slopes, and in the case of an almost vertical line, a point located very close to the line could return false as well.

If this could be a problem you should check Normanâ€™s suggestion.

Also, you are not applying any tolerance to vertical or horizontal lines. This may be by design.

Julen

1 Like

That did it, thanks!
In fact, I saw this page earlier, but I didnâ€™t try the formulas there (not that I dislike maths, but given the poor readability of the equations on Wikipedia (mostly because of the font used) and the fact that I already tried several non-working solutions from elsewhere before, I didnâ€™t take time to try this one).

So, given your reply, I tried anywayâ€¦ First time, it didnâ€™t work and I thought â€śanother formula that doesnâ€™t suit my needs, oh wellâ€¦â€ť. I then double-checked my code andâ€¦
Those damn times where you notice youâ€™ve written â€śxâ€ť instead of â€śyâ€ť in one occurrence (especially since, on my Swiss keyboard layout, x and y are neighbours, so typing one instead of the other is easy).

And, I had a problem with the formula about polygons too (the â€śrayâ€ť method for â€śis a point inside a polygon?â€ť would work randomly, because it relies on the â€śis a point on a line?â€ť method which didnâ€™t work). With this repaired function, the polygon method got fixed alongâ€¦!

Very nice, thank you!

If a line is horizontal, there are two possible ways:
1: the mouse is out of the line. This condition is caught earlier in code (the bound rectangle is checked) and â€śfalseâ€ť is already returned.
2: the mouse is on the line. â€śif xd=0 or yd=0 then Return Trueâ€ť would handle these vertical or horizontal lines.
That being said, I understand your point is about the next paragraphâ€¦

Youâ€™re right, I was seeing this wrong. I did realise a point with a distance of 1 would mean 1.41 difference for x and y with a 45Â° slope (Pythagore), but, instead of thinking the approach was wrong, I thought â€śdoesnâ€™t matter, Iâ€™ll adjust the tolerance to 2â€ť.
The problem with this was also clear to me: given different slopes, the tolerance would need to adapt (an almost-horizontal line would be detected too â€śearlyâ€ť while a vertical one might not even been detected). Back to square 1, I was stuck hereâ€¦

My drawings are antialiased. Ideally, Iâ€™d like a tolerance of 0 everywhere. For now, it almost looks working. But, yes, good remark.
Thank you.

Another approach that can additionally be used to check if a point is inside a polygon: create an additional picture and draw your line with a thickness that includes the tolerance. Then get the color of the pixel corresponding to the position of the point. If the color is that of the background the point is not on the line. If the color corresponds to that of the line (which includes the tolerance) then itâ€™s a hit.

The same can be used for polygons, draw them (filled) on a sepparate picture and follow the same procedure to check if the point is in. No math needed.

Julen

Thanks. This is the approach I used in the earlier versions of this application.
I eventually thought using maths would be faster than drawing to buffer pictures, especially since the objects may move/resize, so Iâ€™m actually refactoring my code toward the math method.

Do you mean math would actually be slower than letting the framework draw to a buffer picture and check the pixelâ€™s colour (i.e. my previous method)?
I havenâ€™t made any benchmark, just saw the buffer pictureâ€™s way was somehow slowâ€¦

I really doubt drawing to a picture then looking for pixels of a given color would be faster ESP if you used moderate or aggressive compile options

No, I didnâ€™t mean to imply that. I think the code should be easier to read, though.

Julen

Yes, me too. Itâ€™s just I thought the quoted sentence was suggesting this.

Granted, but itâ€™s this kind of code you put in a module and, once completed, you donâ€™t check again (the formula wonâ€™t ever change).
Thanks.