concave_hull returns nonsense results for simple polygons

[wlinna]

I'm testing concave_hull with a simple polygon, and concave_hull returns very weird results. Here are the screenshots

Original polygon

Concave hull

Here's the test code

       let exterior = LineString(vec![
            Coord { x: 5.1734996, y: 1.4128553 },
            Coord { x: 5.1734996, y: 1.5378553 },
            Coord { x: -4.9266067, y: 1.5378562 },
            Coord { x: -4.9266057, y: -8.45025 },
            Coord { x: -4.8016057, y: -8.45025 },
            Coord { x: -4.8016057, y: 1.4128553 },
            Coord { x: 5.1734996, y: 1.4128553 },
        ]);
    
        let polygon = Polygon::new(exterior.clone(), vec![]);
        let hull = polygon.concave_hull(0.5); // Whether the concavity is 0.5 or 4.0 doesn't seem to matter

I'm using geo 0.27.0 with Rustc 1.72

[wlinna]

I tried this again with both geo 0.27 and geo 0.28 , and it looks like nothing changed with concave hull itself. Both versions result in following coordinates

-4.9266057 -8.45025
-4.8016057 -8.45025
5.1734996 1.4128553
5.1734996 1.5378553
-4.9266067 1.5378562
-4.9266057 -8.45025

However, I'm not sure anymore how I produced the original 3D model of the concave hull. When I generate it now, it looks like this

I checked the printed coordinates visually one by one, and they correspond with the generated triangle mesh.

So at least the algorithm produces a convex hull. But I can't make it produce the original shape.

[kirillolenev-dm]

Any updates about that? I have a similar experience when concave_hull provides something not close to expected result, concavity param doesn't change much.

[michaelkirk]

@kirillolenev-dm - can you provide a minimal reproduction?

e.g. the input you gave and the output you're expecting?

concave hull is a bit tricky because there's no rigorous definition for what the "correct" output should be. I'll say that @wlinna's first screenshot looks very concerning, not a hull at all, but seemingly that output can no longer be reproduced.

The second one at least looks like a hull, but admittedly doesn't look very concave.

I don't use these methods myself, but I'd be willing to look into any issues with it if you can gather more expected input/outputs.

[michaelkirk]

(sorry that this sat here so long!)

[wlinna]

I suppose I could turn my example into an actual unit test, but that is not much.
Maybe I could create some synthetic inputs / outputs.

[wlinna]

Hello @michaelkirk , I made a unit test out of the original case. Please tell me what you think of it. I can make another, synthetic and simplified test based on a real case I would like to use concave hull on.

    #[test]
    fn concave_hull() { // https://github.com/georust/geo/issues/1124
        
        let line_string = LineString(vec![
            Coord { x: 5.1734996, y: 1.4128553 },
            Coord { x: 5.1734996, y: 1.5378553 },
            Coord { x: -4.9266067, y: 1.5378562 },
            Coord { x: -4.9266057, y: -8.45025 },
            Coord { x: -4.8016057, y: -8.45025 },
            Coord { x: -4.8016057, y: 1.4128553 },
            Coord { x: 5.1734996, y: 1.4128553 },
        ]);

        // get_rr().log("2d/exterior_point", 
        // &Points2D::new(line_string.coords().map(|c| [c.x, c.y]))
        // ).ok();

        let indices_not_on_convex_hull = [5];

        let indices_on_convex_hull = (0..line_string.coords_iter().count())
            .filter(|i| !indices_not_on_convex_hull.contains(i))
            .collect::<Vec<_>>();

        let coords_on_convex_hull = indices_on_convex_hull
            .iter()
            .map(|i| line_string.0[*i])
            .collect::<Vec<_>>();
    
        let polygon = Polygon::new(line_string.clone(), vec![]);
        let hull = polygon.concave_hull(2.0); // Whether the concavity is 0.5 or 4.0 doesn't seem to matter

        // Concave hull should include all the coords that a convex hull would
        for coord_on_convex_hull in &coords_on_convex_hull {
            assert!(hull.exterior().contains(coord_on_convex_hull));
        }

        // This line jumps takes a huge leap from one coord on a convex hull to another.
        let bad_line = geo::Line::new(line_string[4], line_string[6]);
        let bad_line_inv = geo::Line::new(line_string[6], line_string[4]);

        for line in hull.lines_iter() {
            assert_ne!(line, bad_line);
            assert_ne!(line, bad_line_inv);
        }

        // get_rr().flush_blocking();
    }