[BUG] Drawing series can hang under certain conditions

[JuliDi]

Describe the bug
Using the code in the following repo, plotters will hang when drawing the series. It only happens under very specific conditions, i.e., the specifically set stroke width and backend dimensions with a certain dataset.
It looks like there is something going on with an over-/underflow because when the bug occurs, the vertices vector has at least once the values (2147483647, 2147483647), which cause the x_span here

plotters/plotters-backend/src/rasterizer/polygon.rs

Line 124 in af0b63c

let (low, high) = if horizontal_sweep { x_span } else { y_span };

to be huge and the subsequent loop takes forever.

I am not sure where these might come from and wasn't able to pinpoint the exact issue with the debugger.

To Reproduce
The code to reproduce the issue can be found here for convenience: https://github.com/JuliDi/plotters-bug-demo including a set of data that triggers the bug.

Details

use plotters::prelude::*;
const PLOT_LINE_COLOR: RGBColor = RGBColor(0, 175, 255);
pub fn main() {
let data = vec![16.813898, 21.467485, 16.699194, 18.656145, 1.8458271, 6.958304, 4.668895, 3.4034894, 11.170396, 22.686535, 20.591629, 8.35795, 18.369057, 13.557362, 24.329618, 17.74448, 39.69061, 28.81381, 39.383015, 25.405262, 20.539597, 14.12167, 32.729282, 17.82943, 25.446245, 21.351706, 12.016595, 17.353453, 12.965088, 9.063063, 14.804887, 3.3717983, 18.540174, 16.883198, 23.810902, 11.066169, 7.347625, 11.817309, 6.2633786, 17.756893, 4.029601, 2.5398593, 10.924131, 24.878021, 28.928385, 12.491558, 11.346132, 9.482814, 16.11943, 16.64973, 10.3768425, 18.920292, 11.828327, 9.192125, 33.367313, 16.697374, 13.507518, 14.694922, 16.67566, 27.475872, 21.03208, 14.162327, 10.873885, 16.531784, 8.103211, 8.684803, 18.726849, 17.095837, 23.579023, 5.048337, 10.975269, 14.428657, 12.765751, 21.9303, 7.9336004, 20.152481, 12.144512, 1.0923405, 15.923292, 15.101516, 28.304052, 18.786118, 11.663957, 11.990492, 12.881969, 7.450888, 18.492188, 24.230925, 23.171167, 11.404102, 19.609896, 4.8243628, 13.179412, 17.68572, 9.867716, 5.25622, 18.082666, 30.46109, 20.762335, 19.089638, 24.995098, 13.9115095, 33.071114, 12.434493, 20.163658, 28.058327, 39.1902, 19.891376, 8.897499, 4.2061777, 21.742756, 7.37039, 17.926682, 11.314838, 19.42905, 15.376271, 20.434095, 11.794729, 16.583397, 21.013033, 31.112232, 15.628697, 28.886744, 27.737251, 21.806887, 5.764174, 7.6569896, 34.653584, 34.28854, 67.45283, 135.27437, 189.08481, 42.77188, 25.337303, 2.5914989, 34.182064, 18.974936, 19.168165, 23.921913, 20.48953, 26.52906, 3.7035255, 22.675589, 7.4574223, 22.76912, 9.460767, 27.8287, 12.066594, 15.412456, 26.818674, 32.694702, 21.808376, 23.520004, 6.5400176, 35.558197, 11.853939, 30.302734, 24.195833, 24.629995, 35.11812, 19.725723, 9.664452, 11.475963, 17.11769, 16.859127, 6.533736, 17.694416, 11.510996, 23.27193, 27.069403, 15.088213, 9.736533, 11.172734, 15.25471, 9.9892235, 15.910875, 25.13705, 17.351255, 13.522468, 2.7220654, 12.812791, 17.815294, 8.057408, 23.95524, 9.931442, 13.47129, 9.590451, 4.1158338, 25.822966, 17.54566, 16.215902, 10.901377, 10.184222, 19.054682, 11.37252, 14.23101, 18.637873, 29.038452, 18.053534, 12.394553, 12.092359, 15.310099, 31.077723, 11.126249, 9.835912, 21.09747, 12.272691, 17.513615, 18.027584, 10.414021, 10.325374, 12.878272, 29.663559, 23.240133, 10.942607, 3.6961594, 5.338874, 19.394537, 7.8832135, 13.525047, 8.452841, 9.082503, 21.842276, 17.172523, 18.812967, 3.000104, 13.053461, 10.148841, 14.264377, 19.06721, 10.129463, 19.937485, 23.757084, 17.275042, 32.77665, 15.181078, 21.922976, 25.597387, 37.654034, 26.974955, 38.232346, 18.491838, 23.584059, 11.730393, 18.376102, 8.435054, 22.3173, 23.999996, 12.698569, 3.2221498, 5.5601172, 8.75537, 1.2027137, 16.975645, 17.858566, 19.673578];

let width = 677u32;
let height = 799u32;

let backend = BitMapBackend::new("test.bmp", (width, height));

let root = backend.into_drawing_area();
root.fill(&WHITE).expect("error filling drawing area");

let data_y_min = data.iter().cloned().reduce(f32::min).unwrap().ceil();
let data_y_max = data.iter().cloned().reduce(f32::max).unwrap().floor();

let (y_min, y_max) = (data_y_min, data_y_max);

let x_min = 0;
let x_max = data.len();

let mut chart = ChartBuilder::on(&root)
    .x_label_area_size(28)
    .y_label_area_size(28)
    .margin(20)
    .build_cartesian_2d(
        (x_min as f64)..(x_max as f64),
        (y_min as f64)..(y_max as f64),
    )
    .expect("failed to build chart");

chart
    .configure_mesh()
    .draw()
    .expect("failed to draw chart mesh");


let area_series = AreaSeries::new(
    data.iter().enumerate().map(|(x, y)| (x as f64, *y as f64)),
    -1.0,
    PLOT_LINE_COLOR.mix(0.175),
)
    .border_style(ShapeStyle::from(PLOT_LINE_COLOR).stroke_width(2));


chart
    .draw_series(area_series)
    .expect("failed to draw chart data");

root.present().expect("error presenting");

println!("done");

}

Version Information
Latest master branch, commit af0b63c

[el-hult]

I have the same problem. It happens to be the case that f64::INFINITY as i32 == 2147483647

I tracked that infinity back to this section.

plotters/plotters-backend/src/rasterizer/path.rs

Lines 64 to 87 in 123764a

	let mut x = f64::INFINITY;
	let mut y = f64::INFINITY;
	// Well if the determinant is not 0, then we can actually get a intersection point.
	if (a0 * b1 - a1 * b0).abs() > f64::EPSILON {
	let u = (c0 * b1 - c1 * b0) / (a0 * b1 - a1 * b0);
	x = a_p.0 + u * a_t.0;
	y = a_p.1 + u * a_t.1;
	}
	let cross_product = a_t.0 * b_t.1 - a_t.1 * b_t.0;
	if (cross_product < 0.0 && d < 0.0) || (cross_product > 0.0 && d > 0.0) {
	// Then we are at the outer side of the angle, so we need to consider a cap.
	let dist_square = (x - triple[1].0 as f64).powi(2) + (y - triple[1].1 as f64).powi(2);
	// If the point is too far away from the line, we need to cap it.
	if dist_square > d * d * 16.0 {
	buf.push((a_p.0.round() as i32, a_p.1.round() as i32));
	buf.push((b_p.0.round() as i32, b_p.1.round() as i32));
	return;
	}
	}
	buf.push((x.round() as i32, y.round() as i32));

In some cases, you fail both the check on line 68 and 76, and then it computes a vertex to be placed at infinity. I am not sure if this should have been cought in some preconditions or so... Or if it is a plain bug.

[el-hult]

@JuliDi I took your code and simplified further. My most minimal reproduction is as per below.

use plotters::prelude::*;
pub fn main() -> Result<(), Box<dyn std::error::Error>> {
    let root = BitMapBackend::new("test.bmp", (1000, 1000)).into_drawing_area();
    let mut chart = ChartBuilder::on(&root)
        .build_cartesian_2d(0.0..1000.0, 0.0..1000.0)?;
    let data = [(336.0, 614.0), (339.0, 674.0),(341.0,714.0)];
    chart.draw_series(std::iter::once(PathElement::new(
        data,
        ShapeStyle::from(RED).stroke_width(2),
    )))?;
    Ok(())
}

Drawing an AreaSeries will create an outline (you asked for a border of thickness 2) and this triggers drawing a PathElement under the hood. When asking for a thickness > 1, it will call polygonize to create a polygon representing the thick line. It in turn dispatches to traverse_vertices, which is the code I have cited above. It simply seems to me there is a bug in that code.

A workaround could be to use border thickness 1.

[el-hult]

Okay, after some more debugging, I think I got it. It seems like a classical float-comparison bug. I'll try to create a fix.

[JuliDi]

@el-hult thanks for looking into this!
My workaround so far has also been to reduce the border thickness. If you could fix the underlying issue, however, that would be very much appreciated.

[el-hult]

My fix is in the referenced pull request. Lets hope they merge it.

[JuliDi]

Thank you!

[el-hult]

This issue can probably be closed as fixed now after merge.