distance_to/nearest_t returning unexpected results

[KevinThierauf]

I'm trying to use the distance_to function to check whether a certain point is on a line, but have been receiving unexpected results. I wrote a basic test to showcase this issue (using the image library for displaying). Here is a simple example I've wrote to demonstrate:

for (x, y, pixel) in image.enumerate_pixels_mut() {
    let y = HEIGHT - y;
    let coord = Coord2(x as f64, y as f64);
    let distance = curve.distance_to(&coord);
    if distance.is_nan() {
        *pixel = Rgb([255, 255, 255]);
        panic!();
    } else {
        *pixel = Rgb([min(25 * distance as u32, 255) as u8, 0, 0]);
    }
}

Some curves work as expected, others run into issues. I've provided a couple of images using the curve Coord2(259, 322) Coord2(272, 329) Coord2(297, 341) Coord2(350, 397) (start, c1, c2, end) that hopefully help display this issue: https://imgur.com/a/N0A4BUJ

Quick image descriptions (in order of appearance):

1. image is closer to black when on the curve, moves towards red the farther away from the curve
2. same as 1, but with smoother interpolation (previous example has color increase red by 25 out of 255 points per pixel, this image only has the red increase by 1 out of 255 points per pixel).
3. same as 2, but with values > 200 set to pink (maybe a bit clearer?)
4. multiple curves rendered (including the one listed above) with some curves seeming to display correctly, others having some artifacts. pixels with a distance < 10 to curve are displayed.
5. same as 4, but with a thicker line (distance < 10). There are some additional artifacts that are much clearer on this image; there seem to be some random points well outside of the bezier curve range that are returning a distance much closer than they are).

The images also have a single pixel set to a turquoise color where there is a start/end/control point.

I hope this is helpful -- let me know if there's anything I can do to clarify. Thanks for the great library!

[Logicalshift]

Ah, the algorithm uses Newton-Raphson to find the closest point, and the 'gaps' effect you're seeing here is what happens if it starts from a bad guess. The algorithm only tries to optimise a single guess so occasionally it will choose poorly and wind up finding the start or end of the curve, creating a section with a much larger distance measurement than it should have.

I've added a change to the head of the v0.7 branch that starts to address this by trying to optimise all of the points instead of just the initial closest point - this works for a much wider variety of points but I suspect there are still cases where it can fail (the current approach divides the curve into arcs and uses the mid-points as the initial guesses).

I also spotted a slightly more subtle bug where the optimisation stops early if it moves outside the range 0<=t<=1 which could produce incorrect distances if the closest point was close to but not exactly on the start or end of the curve.

[KevinThierauf]

It's working great so far -- thanks so much!

[KevinThierauf]

Hi, I've found a few more outliers. Notably, the curve:

let curve = Curve {
    start_point: Coord2(269.1, 317.7),
    end_point: Coord2(322.4, 415.0),
    control_points: (Coord2(280.1, 332.7), Coord2(316.4, 414.1)),
};
panic!("{:?}", curve.nearest_point(&Coord2(296.0, 367.0)));

is returning Coord2(322.4, 415.0). Here is a quick graph showing this: https://www.desmos.com/calculator/uaani6pp3u (red is the point passed to nearest_point, blue is the returned point). I have another image which shows this for a number of different points: https://imgur.com/a/h8UzDOe (colors are interpolated by distance to the approximately closest bezier curve). You can see the effect of this band in the image (I added a very small 3x1 pink line at (296, 367), where the effect is most visible). Let me know if there's anything else I can provide. Thank you!!

[Logicalshift]

Ah, yes, I thought there might still be cases where the algorithm fails. I've gone for a new approach and implemented the algorithm from Graphics Gems: this should be much more solid as it actually solves for the roots of the quintic function (vs my old approach which took initial guesses based on the geometry of the curve)

I've added your example as a test case and it does find your example point correctly. However, I'm still working on this as I think there are still some cases for this particular curve that aren't resolving correctly - I think it already handles a much wider variety of cases though.

[Logicalshift]

Think I fixed the issues I found with the new algorithm, so I believe the latest version on the 0.7 branch should be very much more reliable than earlier versions.

Issues were a problem with the actual test, and the need to subdivide until control points were ordered, which was causing an issue sometimes when many possible solutions were close together.

[KevinThierauf]

Hi, Thanks! I tried the newest version but I'm getting a panic when I try to get the nearest point to a sufficiently far enough away point. Here is the graph: https://www.desmos.com/calculator/zsnlnra8x0 And the curve:

let coord = Coord2(644.0, 767.0);
let curve = Curve {
    start_point: Coord2(613.1741629120686, 691.31977047597),
    end_point: Coord2(684.1381074976954, 728.253746282104),
    control_points: (Coord2(666.1741629120686, 709.31977047597), Coord2(678.1381074976954, 703.253746282104)),
};
let nearest = curve.nearest_point(&coord);

The stacktrace:

   3: enum2$<core::result::Result<f64,roots::numerical::SearchError> >::unwrap
             at /rustc/90c541806f23a127002de5b4038be731ba1458ca\library\core\src\result.rs:1089
   4: flo_curves::bezier::roots::find_roots::find_x_intercept
             at C:\Users\Kevin\.cargo\git\checkouts\flo_curves-04bad137c6c068b5\70d916b\src\bezier\roots\find_roots.rs:77
   5: flo_curves::bezier::roots::find_roots::find_bezier_roots<flo_curves::geo::coordinate::Coord2,6>
             at C:\Users\Kevin\.cargo\git\checkouts\flo_curves-04bad137c6c068b5\70d916b\src\bezier\roots\find_roots.rs:111
   6: flo_curves::bezier::roots::nearest_point_bezier_root_finder::nearest_point_on_curve_bezier_root_finder<flo_curves::bezier::curve::Curve<flo_curves::geo::coordinate::Coord2> >
             at C:\Users\Kevin\.cargo\git\checkouts\flo_curves-04bad137c6c068b5\70d916b\src\bezier\roots\nearest_point_bezier_root_finder.rs:87
   7: flo_curves::bezier::nearest_point::nearest_point_on_curve
             at C:\Users\Kevin\.cargo\git\checkouts\flo_curves-04bad137c6c068b5\70d916b\src\bezier\nearest_point.rs:22
   8: flo_curves::bezier::curve::impl$4::nearest_point
             at C:\Users\Kevin\.cargo\git\checkouts\flo_curves-04bad137c6c068b5\70d916b\src\bezier\curve.rs:297

Is this intended behavior? If it is, would it be possible to return an option/result if the nearest point cannot be determined, instead of a panic? Thanks you!

[Logicalshift]

Ah: this was actually only two iterations away from succeeding.

I've replaced the solver with one that doesn't produce an error even where it doesn't converge and increased the number of iterations, so this shouldn't happen any more.