concave_hull appears to be returning convex_hull in at least one case

[caewok]

trafficstars

Related: #607

I was testing concave_hull and ran across a potential bug. The following set of points are basically two polygons combined: a square, and a four-sided polygon that overlaps the square, forming something near to a diamond. The concave hull should close in on the intersection points, but instead geo's concave_hull is not doing that and instead returning a convex hull. This differs from the result in concaveman.

let mp: MultiPoint<f64> = vec![
	(450., 100.),
	(611.1111111111111, 100.),
	(100., 450.),
	(100., 611.1111111111111),
	(275., 1000.),
	(1000., 1000.),
	(1000., 275.),
	(1000., 1000.),
	(100., 100.),
	(1000., 100.),
	(1000., 1000.),
	(100., 1000.),
	(100., 100.),
	(50., 500.),
	(500., 50.),
	(1500., 500.),
	(500., 1500.),
	(50., 500.),
].into();

let expected: Polygon<f64> = Polygon::new(
	LineString::from(vec![
		(100., 100.),
		(100., 450.),
		(50., 500.),
		(100., 611.1111111111111),
		(100., 1000.),
		(275., 1000.),
		(500., 1500.),
		(1000., 1000.),
                 (1500., 500.),
		(1000., 275.),
		(1000., 100.),
		(611.1111111111111, 100.),
		(500., 50.),
		(450., 100.),
		(100., 100.),
	]),
	vec![]);

assert_eq!(mp.concave_hull(1.), expected); // will fail

[callpraths]

Thanks for filing this issue. I am working on #607 this month and this counter-example will be very useful.

[wlinna]

My project also suffers from this. My MultiPolygon consists of two orthogonal rectangles (split into triangles).

MultiPolygon(
    [
        Polygon {
            exterior: LineString(
                [
                    Coord {  x: -4.802,  y: 1.413, },
                    Coord {  x: 5.173, y: 1.413, },
                    Coord { x: 5.173, y: 1.538, },
                    Coord {  x: -4.802,   y: 1.413,
                    },
                ],
            ),
            interiors: [],
        },
        Polygon {
            exterior: LineString(
                [
                    Coord {  x: -4.927, y: 1.538, },
                    Coord { x: -4.802,  y: 1.413, },
                    Coord { x: 5.173,  y: 1.538, },
                    Coord { x: -4.927, y: 1.538, },
                ],
            ),
            interiors: [],
        },
        Polygon {
            exterior: LineString(
                [
                    Coord { x: -4.927,  y: -8.45, },
                    Coord { x: -4.802, y: -8.45, },
                    Coord { x: -4.802, y: 1.413, },
                    Coord { x: -4.927, y: -8.45, },
                ],
            ),
            interiors: [],
        },
        Polygon {
            exterior: LineString(
                [
                    Coord { x: -4.927,  y: -8.45, },
                    Coord { x: -4.802,   y: 1.413,  },
                    Coord {  x: -4.927, y: 1.538, },
                    Coord { x: -4.927, y: -8.45,  },
                ],
            ),
            interiors: [],
        },
    ],
)

and the resulting concave hull (concavity parameter being 0.1) looks like this (the L-shape is turned into something that looks more like a triangle when viewed from a distance)

Polygon {
    exterior: LineString(
        [
            Coord {  x: -4.802, y: -8.45, },
            Coord {  x: 5.173,  y: 1.413, },
            Coord { x: 5.173, y: 1.538, },
            Coord {  x: -4.802, y: 1.413, },
            Coord { x: -4.802, y: 1.413, },
            Coord { x: -4.927,  y: 1.538, },
            Coord {  x: -4.927, y: -8.45, },
            Coord {  x: -4.802, y: -8.45,  },
        ],
    ),
    interiors: [],
}