Check if the mouse is over a Bézier curve

Question

My approach was to loop trough the curve and check the mouse distance to various points

But the points get closer together as the curve get steeper, and if the mouse distance threshold is too high it prioritizes the first point in the loop instead of the closet to the mouse.

is there a way to get uniform points in it? Or to check if the mouse is over the Bézier curve and get the position in the curve?

Answer 1

There are two main approaches - subdivision of curve into small line segments and analytical solution.

For the second case you have to build polynomial for squared distance from point to curve depending on parameter t, differentiate it, and find zeros of result (5-th order polynomial). Then choose minimum from distances to point at t[i], t=0, t=1. Another point of view - get projection of point onto curve, so curve tangent in this point is perpendicular to vector point-curvepoint, it should give the same expression.

About uniform points - it is rather hard problem because curve length could not be calculated analytically. But subdivision gives quite good approximation.

Answer 2

I do it like this:

1. subdivide you curve to few chunks

   tne number of chunks depends on the order of curve. As I usually use cubics I empirically find out that ~8 chunks is enough (for my purposes).

2. compute the closest point to a chunk

   So simply handle each chunk as line and compute closest point on the line to the mouse position (minimal perpendicular distance). By computing it for each chunk and remember the closest one.

   

   Now after this we know which chunk contain the "closest" point so from the intersection between line and perpendicular line to it going through mouse position from previous step we should have a parameter u=<0,1> telling us where on the chunk line the closest point is and we also know the curve parameter t of both endpoints of the chunk line (t0,t1). From this we can approximate t for the closest point simply by doing this:

   t = t0 + (t1-t0)*u
   

   On the image t0=0.25 and t1=0.375. This is sometimes enough but if you want better solution so after this just set:

   dt = (t1-t0)/4
   t0 = t-dt
   t1 = t+dt
   

   Use the t0,t,t1 to compute 3 endpoints of 2 chunks and look for the closest point again. You can recursively do this few times as with each iteration you increase precision of the result

   

The perpendicular distance of point to a line is computed by computing intersection between the line and axis perpendicular to it going through the point in question. So if the line is defined by endpoints p0,p1 and the queried point (mouse) is q then the axis in 2D will be:

dp=p1-p0        // line direction
dq=(dp.y,-dp.x) // axis direction is perpendicular to dp
dq/= |dq|       // normalize
p(u) = p0+dp*u  // point on line
p(v) = q +dq*v  // point on axis
u = <0,1>       // parameter on line
v = <-inf,+inf> // parameter on axis

And we want to know u,v from

p0+dp*u = q +dq*v

which is system of 2 linear equations in 2D. In 3D you need to exploit cross product to obtain the dq and the system would contain 3 equations. Solving this sytem will give you u,v where u will tell you where in the chunk the closest point is and |v| is the perpendicular distance itself. Do not forget that if u is not in the range <0,1> then you have to use closer endpoint of the line as the closest point.

The system can be solved either algebraically (but beware the edge cases as there are 2 solutions for the equations in 2D) or use inverse matrix...