Is the mouse on a line?

BlitzPlus Forums/BlitzPlus Programming/Is the mouse on a line?

nazca(Posted 2003) [#1]
I've been toying around with my own code to find this out, but it's not accurate, plus it only works half the time!

So could someone find/make me up a code that returns true if the mouse is being passed over a line (given x1,x2,y1,y2)

thanks!


Bremer(Posted 2003) [#2]
I think you can do the following:

If mousex() <= x2 and mousex() => x1 and mousey() <= y2 and mousey() => y1 then

I'm not home, so I can't test it, but I think it works.

Let me know, otherwise I'll find out when I get home.


Anthony Flack(Posted 2003) [#3]
Nope, that would be, "is mouse inside this box?".

I'm pretty sure that there is code to find a point on a line in the code archives, have you checked there first?


sswift(Posted 2003) [#4]
Finding a point on a line is not the answer. He doesn't want to know if the mouse is ON the line, he wants to know if it's passed over it.

To do that, first, calcualte the normal of the line:
http://www.blitzbasic.com/codearcs/codearcs.php?code=450

Then, using Nx and Ny for A and B do this:

For an arbitary point (px,py), the distance to the line is:

distance = A*px + B*py + D

Astute readers will notice that this is a hacked up version of the plane equation, which is how I derived all this stuff, by pretending the line was the intersection of a 3D plane intersecting 2D space and canceling out all the Z stuff with 0's.


Anyhow, now that you know the distance, know that the distance here is either positive, or negative. Which it is depends on which side of the line you specified you are on.

You can then use this to dtermine that the mouse cursor moved from one side of a line to the other during a frame, and thus that the mouse crossed the line.


Also, this is probably not important for you, but I forget which way the line normal will point. I forget whether the normal, and thus the positive side of the line, points to the left or right if you are at point 1 on the line looking at point 2. I think it's to the left. If someone wants to figure that out and tell me then I'll update the code archives to reflect that.


Bot Builder(Posted 2003) [#5]
Completly untested BTW:

if (MouseX()-X2)/(mouseY()-Y2)=(y2-y1)/(x2-x1) and (mousex()<=x1 and mousex()=>x2) or (mousex()=>x1 and mousex()<=x2) and (mousey()<=y1 and mousey()=>y2) or (mousey()=>x1 and mousey()<=x2) then
;do whatever
endif

This is supposed to test if the slope of the line and the slope relative to a point from the mouse is the same. Then it does a box check to confirm that it is between the points. you do however, run into problems with vertical lines. in this case, do a special-case check.


Dr Derek Doctors(Posted 2003) [#6]
I have an intersecting line algorythm if you like. As long as you store the old co-ordinates of the mouse each frame then it'd be a piece of cake to check whether the line described by the mouse between this frame and the last intersected with another line... Want it?


Dr Derek Doctors(Posted 2003) [#7]
Nothing to see here! Move along!


sswift(Posted 2003) [#8]
I have a duplicate post checking function if you'd like it. It checks to see if all the characters in one post are the same as another!


Dr Derek Doctors(Posted 2003) [#9]
I'm gonna' blame this one on the website I think... :)


sswift(Posted 2003) [#10]
This is why I use Mozilla. It does not automatically refresh, it ASKS you when you refresh, if you submitted post data, if you want to resubmit it. :-)


Bremer(Posted 2003) [#11]
I know that my code checks to see if the mouse is inside a box, but if x1 and x2 is the same or y1 and y2 is the same, then it actually checks to see if the mouse is on the line. But it only works for vertical and horizontal lines not diagonals. Ah well.


BlitzSupport(Posted 2003) [#12]
Haven't tested this extensively, but works for this demo at least... ;)

; -------------------------------------------------------
; Graphics Gems is your friend!
; -------------------------------------------------------
; http://www.graphicsgems.org/
; -------------------------------------------------------

; -------------------------------------------------------
; PointOnLine () - returns True if point is on the line.
; -------------------------------------------------------
; x and y are the co-ords of the point to check; px, py,
; qx, qy define the line...
; -------------------------------------------------------

Function PointOnLine (x, y, px, py, qx, qy)
	If ((px = qx) And (py = qy))
		If ((x = px) And (y = py))
			Return 2
		Else
			Return 0
		EndIf
	EndIf
    If (Abs ((qy - py) * (x - px) - (y - py) * (qx - px)) => (Max (Abs (qx - px), Abs (qy - py)))) Then Return 0
	If (x < px) Or (x > qx) Or (y < py) Or (y > qy) Then Return 0
    Return True
End Function

; -------------------------------------------------------
; Used by above function...
; -------------------------------------------------------

Function Max (a, b)
	If a > b Then Return a Else Return b
End Function

; -------------------------------------------------------
; D E M O . . .
; -------------------------------------------------------

Graphics 640, 480, 0, 2
SetBuffer BackBuffer ()

Repeat

	Cls
	
	Line 100, 100, 400, 300
	
	If PointOnLine (MouseX (), MouseY (), 100, 100, 400, 300)
		Text 20, 20, "On the line!"
	EndIf
	
	Flip
	
Until KeyHit (1)

End



sswift(Posted 2003) [#13]
It would be very bad to use that in a user interface. Do you know how hard it would be to hold your mouse over a single pixel? :-)

If what he wants to know is if the mouse is close to the line, then he should use that function I linked to above, and instead of simpyl determining if the distance is greater than or less than 0, use the distance and see if it is below a certain amount.

Ie:

If abs(distance) < 10 then mouse is less than 10 pixels away from the line.


nazca(Posted 2003) [#14]
thanks everyone! I have it working fine now :)


cyberseth(Posted 2003) [#15]
I need some code to find out if a line intersects an image. What's the fastest way of doing this? I'd rather not plot along the points of the line and do ImageRectCollide checks for each point on the line. If there's a quicker way of checkign, I would be most grateful.


MuffinRemnant(Posted 2003) [#16]
cyberseth:

this is the same math as a clipping routine i.e. you're effectively clipping the line to a rectangle but instead of drawing that line you just need a function to return 'True' if any part of it *would* be drawn. There are lots of ways to do it but search on the net for the Sutherland-(SomeonewhosnameIcantremember) algorithm (try Google->Sutherland->clipping) for a speedy way.


Oldefoxx(Posted 2003) [#17]
As I read the original problem, the question is how to detect if the mouse has passed over a line, not just
intersected it. After all, if you are interested in whether
it intersected it, you want to know if it rests on just one pixel of that line. That is a very fine determination to make, and difficult to achieve manually. Crossing over the line is a more general case.

It's obvious then that you have to track where the mouse was, then determine where it is now. draw a line between the cordinates involved. It constructed line intersects the line you are concerned with, then it did indeed cross the line. Visually, the problem might look like an X, but turned to the angles indicated by the four points.

Since each line can be expressed as an equation, if you set one equation to equal the other, the solution should be the point of intersection. If you can't find a real solution that lies between the values for the X's and Y's of each line, then the two lines do not intersect between those points.

An interesting point is that since X and Y are bound by a linear relationship (these are presumably straight lines),
you only have to check to see if the interecet point is between the X's at the end points, or the Y's at the end points, as it is not necessary to check for both the X's and Y's at the end points.

Another way of possibly looking at the problem is to take the old mouse x-y coordinate and construct a triangle with the end points of the line in question. Then after the mouse moves, take the new mouse x-y coordinate and construct another triangle with the end points of the line in question. If the triangle deflects in the opposite direction, then the line has been crossed. I dn't think that this offers any improvements, but it was another approach that I considered. I also thought about "boxing" the four points. That is, If I could draw a line from the old mouse x-y to one end of the line, then from that end point to the new mouse x-y position, back to the other end of the line, then close the box by returning to the old mouse x-y point again, what would I prove? Well, for one thing, and none of the interior angles is greater than 180 degrees (sum total is 360 degrees), then the box was formed with the old and new mouse points on either side of the line or on the line, meaning it had been crossed or intersected by the mouse.

The intersect of an image is probably easier, since you consider the image to be a rectangle, and here you just want to see if the mouse point lies within the rectangular coordinates. Most images are vertically or horizontally aligned, meaning no special tricks with line slopes or diagonals.


poopla(Posted 2003) [#18]
Did someone not pay attention in their linear algebra course? :) You could easily solve this as a system of equations with a vertical or horizontal line at the point the mouse is. Then you simply have to compare the solution to the system to the position of the mouse x/y.... so I suppose you would have to find solutions for the X and Y of the mouse, but still not hard. I'll write a funciton if someone else hasnt already ( I didnt read the whole thread ) someone give me a heads up :).


Oldefoxx(Posted 2003) [#19]
I will give two approaches: First a line (x1,y1mx2,y2), and two points: (x3,y3) (the old mouse position), and (x4,y4) (the new mouse position). For the mouse to have just crossed the line, the two points must be on opposite sides of the line (x1,y1,x2,y2). The easiest way to check
this is to consider that an invisible "line: joins the
old and new mouse points, which would then have the
co-points of (x3,y3,x4,y4). If the mouse trail or line
crosses the actual line, the two lines are said to intersect at one point, which we could consider (x5,y5).

By first deriving the equations for the two lines, then
solving for a common solution (solution of simultaneous equations), we would either find a real solution, meaning that they cross or would cross if extended infinately, or we would not get any solution, meaning the lines must be parallel.

To find the equation for the first line, you would use the
formula (x2-x1)*(y-y1)=(y2-y1)**x-x1). Note that in this
form there is no risk of a divide-by-zero error, which makes it preferable to the Y=mX+C slope form. You don't know what Y and X are yet, so when you solve the equation,
replace the Y with "Y", and the X with "X", and just put
in the known values for x1,y1,x2,and y2. As you resolve the
equation, you will end up with some_value * "X" - some_value * "Y" + some_value (for "C"). You still don't know what "X" and "Y" are in terms of a value, but the above represents an equation for the first line.

Then you do the same for the second line or "trail":
(x4-x3)&(y-y3)=(y4-y3)*(x-x3). Perform the reduction in the same manner, and again you will end up with Some_value * "X" - some_value * "Y" + some_value (again, the y offset).

Now you have two equations, which can be solved simultaneously to determine if there is a value for X and a value for Y that would satisfy both. Although you can use
substitution and elimination methods to end up solving for
just one unknown (either X or Y), then use that value back in the original equations to find the missing variable (find Y if you have X, or find X if you have Y), the simplest thing to do with a computer is a brute force approach involving fixed rules and no variations. Such a rule is Cramer's Rule, and if you apply it properly, it will tell you if there is a point where the two lines would intersect.

But hold on, it would still tell you that even if the two points represent end points of the line, and so you still need to determine if that point exists on both lines, between both sets of X values, or both sets of Y values. So X would have to be (x1<=X<=x2 OR x1>=X>=x2) AND (x3<=X<=x4 OR x3>=X>=x4), or you can make the same checks
using the equivalent points along the Y-axis against Y.

You can find the complete solution in my program, "X-Y 2D Graph", under the 2D Graphics portion of the forums. Look in the program in the section where I actually draw the
lines, and you will also see where I find the equation for
the lines. All this information is ported in the GP#() array to a function called Cramer that decides if the two lines intersect or not. If they do, it returns the (x,y) intersection point. If they do not, then it returns
(---,---).