CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS

Adriano Moreira, Maribel Yasmina Santos

2007

Abstract

This paper describes an algorithm to compute the envelope of a set of points in a plane, which generates convex or non-convex hulls that represent the area occupied by the given points. The proposed algorithm is based on a k-nearest neighbours approach, where the value of k, the only algorithm parameter, is used to control the “smoothness” of the final solution. The obtained results show that this algorithm is able to deal with arbitrary sets of points, and that the time to compute the polygons increases approximately linearly with the number of points.

Paper Citation

in Harvard Style

Moreira A. and Yasmina Santos M. (2007). CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS . In Proceedings of the Second International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, ISBN 978-972-8865-71-9, pages 61-68. DOI: 10.5220/0002080800610068

in Bibtex Style

@conference{grapp07,
author={Adriano Moreira and Maribel Yasmina Santos},
title={CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS},
booktitle={Proceedings of the Second International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP,},
year={2007},
pages={61-68},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002080800610068},
isbn={978-972-8865-71-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Second International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP,
TI - CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS
SN - 978-972-8865-71-9
AU - Moreira A.
AU - Yasmina Santos M.
PY - 2007
SP - 61
EP - 68
DO - 10.5220/0002080800610068