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 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.
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…!
Thanks for your reply.
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.
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…
(especially since, on my Swiss keyboard layout, x and y are neighbours, so typing one instead of the other is easy).