What algorithm determines the nearness of a point to a Bezier curve?

Question

I wish to determine when a point (mouse position) in on, or near a curve defined by a series of B-Spline control points.

The information I will have for the B-Spline is the list of n control points (in x,y coordinates). The list of control points can be of any length (>= 4) and define a B-spline consisting of (n−1)/3 cubic Bezier curves. The Bezier curves are are all cubic. I wish to set a parameter k,(in pixels) of the distance defined to be "near" the curve. If the mouse position is within k pixels of the curve then I need to return true, otherwise false.

Is there an algorithm that gives me this information. Any solution does not need to be precise - I am working to a tolerance of 1 pixel (or coordinate).

I have found the following questions seem to offer some help, but do not answer my exact question. In particular the first reference seems to be a solution only for 4 control points, and does not take into account the nearness factor I wish to define.

Position of a point relative to a Bezier curve

Intersection between bezier curve and a line segment

EDIT: An example curve:

 e, 63.068, 127.26   
    29.124, 284.61   
    25.066, 258.56   
    20.926, 212.47   
        34, 176  
    38.706, 162.87  
    46.556, 149.82  
    54.393, 138.78 

The description of the format is: "Every edge is assigned a pos attribute, which consists of a list of 3n + 1 locations. These are B-spline control points: points p0, p1, p2, p3 are the first Bezier spline, p3, p4, p5, p6 are the second, etc. Points are represented by two integers separated by a comma, representing the X and Y coordinates of the location specified in points (1/72 of an inch). In the pos attribute, the list of control points might be preceded by a start point ps and/or an end point pe. These have the usual position representation with a "s," or "e," prefix, respectively."

EDIT2: Further explanation of the "e" point (and s if present).

In the pos attribute, the list of control points might be preceded by a start point ps and/or an end point pe. These have the usual position representation with a "s," or "e," prefix, respectively. A start point is present if there is an arrow at p0. In this case, the arrow is from p0 to ps, where ps is actually on the node’s boundary. The length and direction of the arrowhead is given by the vector (ps −p0). If there is no arrow, p0 is on the node’s boundary. Similarly, the point pe designates an arrow at the other end of the edge, connecting to the last spline point.

Answer 1

You may do this analitically, but a little math is needed.

A Bezier curve can be expressed in terms of the Bernstein Basis. Here I'll use Mathematica, that provides good support for the math involved.

So if you have the points:

pts = {{0, -1}, {1, 1}, {2, -1}, {3, 1}};  

The eq. for the Bezier curve is:

f[t_] := Sum[pts[[i + 1]] BernsteinBasis[3, i, t], {i, 0, 3}];

Keep in mind that I am using the Bernstein basis for convenience, but ANY parametric representation of the Bezier curve would do.

Which gives:

Now to find the minimum distance to a point (say {3,-1}, for example) you have to minimize the function:

d[t_] := Norm[{3, -1} - f[t]];  

For doing that you need a minimization algorithm. I have one handy, so:

NMinimize[{d[t], 0 <= t <= 1}, t]  

gives:

 {1.3475, {t -> 0.771653}}  

And that is it.

HTH!

Edit Regarding your edit "B-spline with consisting of (n−1)/3 cubic Bezier curves."

If you constructed a piecewise B-spline representation you should iterate on all segments to find the minima. If you joined the pieces on a continuous parameter, then this same approach will do.

Edit

Solving your curve. I disregard the first point because I really didn't understand what it is.

I solved it using standard Bsplines instead of the mathematica features, for the sake of clarity.

Clear["Global`*"];
(*first define the points *)
pts = {{
        29.124, 284.61}, {
        25.066, 258.56}, {
        20.926, 212.47}, {
        34, 176}, {
        38.706, 162.87}, {
        46.556, 149.82}, {
        54.393, 138.78}};

(*define a bspline template function *)

b[t_, p0_, p1_, p2_, p3_] :=
                  (1-t)^3 p0 + 3 (1-t)^2 t p1 + 3 (1-t) t^2 p2 + t^3 p3;

(* define two bsplines *)
b1[t_] := b[t, pts[[1]], pts[[2]], pts[[3]], pts[[4]]];
b2[t_] := b[t, pts[[4]], pts[[5]], pts[[6]], pts[[7]]];

(* Lets see the curve *)

Show[Graphics[{Red, Point[pts], Green, Line[pts]}, Axes -> True], 
 ParametricPlot[BSplineFunction[pts][t], {t, 0, 1}]]

. ( Rotated ! for screen space saving )

(*Now define the distance from any point u to a point in our Bezier*)
d[u_, t_] := If[(0 <= t <= 1), Norm[u - b1[t]], Norm[u - b2[t - 1]]];

(*Define a function that find the minimum distance from any point u \
to our curve*)
h[u_] := NMinimize[{d[u, t], 0.0001 <= t <= 1.9999}, t];

(*Lets test it ! *)
Plot3D[h[{x, y}][[1]], {x, 20, 55}, {y, 130, 300}]

This plot is the (minimum) distance from any point in space to our curve (of course the value over the curve is zero):

Answer 2

First, render the curve to a bitmap (black and white) with your favourite algorithm. Then, whenever you need, determine the nearest pixel to the mouse position using information from this question. You can modify the searching function so that it will return distance, so you can easilly compare it with your requirements. This method gives you the distance with tolerance of 1-2 pixels, which will do, I guess.

Answer 3

Definition: distance from a point to a line segment = distance from the original point to the closest point still on the segment.

Assumption: an algo to compute the distance from a point to a segment is known (e.g. compute the intercept with the segment of the normal to the segment passing through the original point. If the intersection is outside the segment, pick the closest end-point of the segment)

1. use the deCasteljau algo and subdivide your cubics until getting to a good enough daisy-chain of linear segments. Supplementary info the "Bezier curve flattening" section
2. consider the minimum of the distances between your point and the resulted segments as the distance from your point to the curve. Repeat for all the curves in your set.

Refinement at point 2: don't compute the actual distance, but the square of it, getting the minimum square distance is good enough - saves a sqrt call/segment.

Computation effort: empirically a cubic curve with a maximum extent (i.e. bounding box) of 200-300 results in about 64 line segments when flattened to a maximum tolerance of 0.5 (approx good enough for the naked eye).

1. Each deCasteljau step requires 12 division-by-2 and 12 additions.
2. Flatness evaluation - 8 multiplications + 4 additions (if using the TaxiCab distance to evaluate a distance)
3. the evaluation of point-to-segment distance requires at max 12 multiplications and 11 additions - but this will be a rare case in the context of Bezier flattening, I'd expect an average of 6 multiplications and 9 additions.

So, assuming a very bad case (100 straight segments/cubic), you finish in finding your distance with a cost of approx 2600 multiplications + 2500 additions per considered cubic.

Disclaimers:

1. don't ask me for a demonstration on the numbers in the computational effort evaluation above, I'll answer with "Use the source-code" (note: Java implementation).
2. other approaches may be possible and maybe less costly.

Regards,

Adrian Colomitchi