Skip to content

[Small Feature] Point Set Clustering#4568

Merged
lrineau merged 27 commits intoCGAL:masterfrom
sgiraudot:PSP-Cluster_points-GF
May 18, 2020
Merged

[Small Feature] Point Set Clustering#4568
lrineau merged 27 commits intoCGAL:masterfrom
sgiraudot:PSP-Cluster_points-GF

Conversation

@sgiraudot
Copy link
Copy Markdown
Contributor

@sgiraudot sgiraudot commented Mar 10, 2020 •
edited by MaelRL
Loading

Rationale

Identifying clusters of locally connected points in a point set is a pretty standard procedure. Although the algorithm is pretty simple and straightforward, CGAL does not provide any API to such an algorithm, which seems like a missing feature.

(In my personal experience, I used several times this algorithm and kept copy-pasting the code, so I figured it belonged in the Point Set Processing package.)

This small features adds a clustering algorithm to Point Set Processing.

Summary of API changes

A new function CGAL::cluster_point_set() is provided, along with a new named parameter adjacencies.

License and copyright ownership

GPL, GeometryFactory

CHANGES.md

(todo)

Submission

Version 1 (outdated)

Version 2

Status

@mglisse
Copy link
Copy Markdown
Member

mglisse commented Mar 10, 2020

Precisely because clustering is such a well-known and wide topic, it should be clear what algorithm you are using. Are you just returning the connected components of a union of balls? The generic name "clustering" may give users a lot of expectations.

@sgiraudot
Copy link
Copy Markdown
Contributor Author

sgiraudot commented Mar 11, 2020

The documentation says:

Identifies simply connected clusters on a nearest neighbors graph.

How can I make it clearer?

@mglisse
Copy link
Copy Markdown
Member

mglisse commented Mar 11, 2020

simply connected clusters -> connected components

nearest neighbor graph: that has a precise definition. Neighborhood graph is more vague. I've seen the graph with all pairs at distance less than r called the r-Rips graph, proximity graph, maybe also some name with "ball" in it, not sure about it, it probably doesn't have a canonical name. Anyway, a sentence explaining what it does cannot hurt.

@afabri
Copy link
Copy Markdown
Member

afabri commented Mar 11, 2020

I suggest to add an image for a 2D point set (then it is planar which is better for html).
I think your "neighbor" function must be symmetric as you strive for equivalence classes. It does not seem to be well defined for functions like "a link to the closest point" which are not symmetric.

@maxGimeno
Copy link
Copy Markdown
Contributor

maxGimeno commented Mar 12, 2020

Errors on travis here and here

@sgiraudot
Copy link
Copy Markdown
Contributor Author

sgiraudot commented Mar 17, 2020

I uploaded a new version of the doc following the different reviews I got. Following a discussion with @afabri, I removed the parameter K, as using a number of nearest neighbors to create the nearest neighbor graph creates a directed graph that is not well suited for this algorithm. Now only a neighbor radius can be used, which makes the graph undirected and the algorithm better defined. I also added a figure.

@sgiraudot sgiraudot force-pushed the PSP-Cluster_points-GF branch from 1645786 to 0e67264 Compare March 17, 2020 11:05
@MaelRL
Copy link
Copy Markdown
Member

MaelRL commented Apr 7, 2020

@afabri @sgiraudot bump

@MaelRL MaelRL added this to the 5.1-beta milestone Apr 7, 2020
@MaelRL MaelRL added the pre-approved For pre-approved small features. After 15 days the feature will be accepted. label Apr 16, 2020
@sgiraudot sgiraudot changed the base branch from master to releases/CGAL-5.0-branch April 16, 2020 15:02
@maxGimeno
Copy link
Copy Markdown
Contributor

maxGimeno commented May 4, 2020

Successfully tested in https://cgal.geometryfactory.com/CGAL/testsuite/results-5.1-Ic-139.shtml.

@maxGimeno maxGimeno added Tested and removed Tested labels May 4, 2020
@sloriot
Copy link
Copy Markdown
Member

sloriot commented May 5, 2020

@sgiraudot could you please update changes.md?

@sgiraudot sgiraudot changed the base branch from master to releases/CGAL-5.0-branch May 6, 2020 07:01
@sgiraudot sgiraudot changed the base branch from releases/CGAL-5.0-branch to master May 6, 2020 07:01
@MaelRL MaelRL mentioned this pull request May 9, 2020
Merged
6 tasks
sloriot
sloriot reviewed May 12, 2020
View reviewed changes
Property_map/include/CGAL/property_map.h
template <typename Range, typename Pmap>
CGAL::Iterator_range<typename boost::transform_iterator<CGAL::Property_map_to_unary_function<Pmap>,
typename Range::iterator> >
make_transform_range_from_property_map (Range& range, Pmap pmap)
Copy link
Copy Markdown
Member

@sloriot sloriot May 12, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I would rename that to transform_range_[with/using]_property_map()

@maxGimeno
Copy link
Copy Markdown
Contributor

maxGimeno commented May 18, 2020

Successfully tested in https://cgal.geometryfactory.com/CGAL/testsuite/results-5.1-Ic-152.shtml

@lrineau lrineau self-assigned this May 18, 2020
@lrineau lrineau added the rm only: ready for master For the release team only: that indicates that a PR is about to be merged in 'master' label May 18, 2020
@lrineau lrineau merged commit bb012da into CGAL:master May 18, 2020
@lrineau lrineau deleted the PSP-Cluster_points-GF branch May 18, 2020 10:39
@lrineau lrineau removed the rm only: ready for master For the release team only: that indicates that a PR is about to be merged in 'master' label May 18, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@sloriot sloriot sloriot left review comments

+1 more reviewer

@maxGimeno maxGimeno maxGimeno left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

@lrineau lrineau

Labels

Accepted small feature Merged_in_5.1 Pkg::Point_set_processing_3 Small feature tested manually on Linux Tested

Projects

None yet

Milestone

5.1-beta1

Development

Successfully merging this pull request may close these issues.

7 participants

@sgiraudot @mglisse @afabri @maxGimeno @MaelRL @sloriot @lrineau