Opened 5 years ago

Closed 4 years ago

#2648 closed defect (fixed)

v.concave.hull fails with small number of points

Reported by: annakrat Owned by: grass-dev@…
Priority: normal Milestone: 7.0.1
Component: Addons Version: unspecified
Keywords: concave hull Cc:
CPU: Unspecified Platform: All

Description

Tested with 3, 4, 5 points, v.concave.hull fails. Depends on threshold and point configuration, too.

ERROR: Input vector map contains no boundaries.
...
 ['v.centroids', '--q', 'input=concave_hull_tmp_31390_delaunay_borders_select', 'output=concave_hull_tmp_31390_delaunay_areas_select'] ended with error

Change History (7)

comment:1 Changed 4 years ago by mlennert

Could you provide a reproducible test case ?

comment:2 in reply to:  1 ; Changed 4 years ago by annakrat

Replying to mlennert:

Could you provide a reproducible test case ?

echo "638597|220531
638838|220526
638757|220237
638695.0|220410.0" | v.in.ascii in=- out=points
v.concave.hull input=points out=hull

comment:3 in reply to:  description ; Changed 4 years ago by mlennert

Replying to annakrat:

Tested with 3, 4, 5 points, v.concave.hull fails. Depends on threshold and point configuration, too.

ERROR: Input vector map contains no boundaries.
...
 ['v.centroids', '--q', 'input=concave_hull_tmp_31390_delaunay_borders_select', 'output=concave_hull_tmp_31390_delaunay_areas_select'] ended with error

AFAICT, the algorithm cannot calculate the hull because the threshold is too high. For now I've added a fatal error in the script with a hint about the threshold (r65495). I don't know if the algorithm could be improved to allow a less concave hull even with such small number of points.

comment:4 in reply to:  2 Changed 4 years ago by mlennert

Replying to annakrat:

Replying to mlennert:

Could you provide a reproducible test case ?

echo "638597|220531
638838|220526
638757|220237
638695.0|220410.0" | v.in.ascii in=- out=points
v.concave.hull input=points out=hull

This works with thresh=1 or 0.

comment:5 in reply to:  3 ; Changed 4 years ago by mlennert

Replying to mlennert:

Replying to annakrat:

Tested with 3, 4, 5 points, v.concave.hull fails. Depends on threshold and point configuration, too.

ERROR: Input vector map contains no boundaries.
...
 ['v.centroids', '--q', 'input=concave_hull_tmp_31390_delaunay_borders_select', 'output=concave_hull_tmp_31390_delaunay_areas_select'] ended with error

AFAICT, the algorithm cannot calculate the hull because the threshold is too high. For now I've added a fatal error in the script with a hint about the threshold (r65495).

I've changed it again in r65496: the algorithm now automatically reduces the threshold if it is too high and only fatals out if even a threshold of 0 wouldn't work.

comment:6 in reply to:  5 ; Changed 4 years ago by annakrat

Replying to mlennert:

Replying to mlennert:

Replying to annakrat:

Tested with 3, 4, 5 points, v.concave.hull fails. Depends on threshold and point configuration, too.

ERROR: Input vector map contains no boundaries.
...
 ['v.centroids', '--q', 'input=concave_hull_tmp_31390_delaunay_borders_select', 'output=concave_hull_tmp_31390_delaunay_areas_select'] ended with error

AFAICT, the algorithm cannot calculate the hull because the threshold is too high. For now I've added a fatal error in the script with a hint about the threshold (r65495).

I've changed it again in r65496: the algorithm now automatically reduces the threshold if it is too high and only fatals out if even a threshold of 0 wouldn't work.

Thanks, this works for the case. But for some point configurations, the algorithm still doesn't produce what I would expect, for example these points where the concave and convex hull should be the same I think, but are not:

 echo "638597|220531
638838|220526
638757|220237
638606|220331
638651|220576.08
638735|220601.28
638798|220578.18
638856.8|220456.38
638886.2|220292.58
638644.7|220256.88
638579.6|220437.48" | v.in.ascii in=- out=points --o
 v.concave.hull input=points out=hull --o

I don't know what could be done about it. Maybe we could consider this ticket as solved. Thank you

comment:7 in reply to:  6 Changed 4 years ago by mlennert

Resolution: fixed
Status: newclosed

Replying to annakrat:

Replying to mlennert:

Replying to mlennert:

Replying to annakrat:

Tested with 3, 4, 5 points, v.concave.hull fails. Depends on threshold and point configuration, too.

ERROR: Input vector map contains no boundaries.
...
 ['v.centroids', '--q', 'input=concave_hull_tmp_31390_delaunay_borders_select', 'output=concave_hull_tmp_31390_delaunay_areas_select'] ended with error

AFAICT, the algorithm cannot calculate the hull because the threshold is too high. For now I've added a fatal error in the script with a hint about the threshold (r65495).

I've changed it again in r65496: the algorithm now automatically reduces the threshold if it is too high and only fatals out if even a threshold of 0 wouldn't work.

Thanks, this works for the case. But for some point configurations, the algorithm still doesn't produce what I would expect, for example these points where the concave and convex hull should be the same I think, but are not:

 echo "638597|220531
638838|220526
638757|220237
638606|220331
638651|220576.08
638735|220601.28
638798|220578.18
638856.8|220456.38
638886.2|220292.58
638644.7|220256.88
638579.6|220437.48" | v.in.ascii in=- out=points --o
 v.concave.hull input=points out=hull --o

The PostGIS ST_ConcaveHull fonction authors agree with you as whatever the precentage I set, I always get the convex hull as a result.

I don't know what could be done about it.

I don't either. I don't even know if there is one "correct" definition of a concave hull.

Maybe we could consider this ticket as solved. Thank you

Yes, I'm closing it. If you want to discuss the general results of v.concave.hull, thus probably warrants another ticket.

Note: See TracTickets for help on using tickets.