georust / geo

Geospatial primitives and algorithms for Rust
https://crates.io/crates/geo
Other
1.48k stars 191 forks source link

concave_hull returns nonsense results for simple polygons #1124

Open wlinna opened 7 months ago

wlinna commented 7 months ago

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

Original polygon OriginalPolygon

Concave hull FailedConcaveHull

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 commented 2 months ago

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

imagen

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.