OPTICS is an algorithm for finding density-based clusters in spatial data. It was presented by Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel and Jörg Sander in 1999.

The goal of this repository is to provide a C++ implementation of the algorithm compatible with the cloud and points of the Point Cloud Library (PCL) project, without any further dependencies than those required by the PCL. The metric used by the algorithm to estimate density is the euclidean distance in a 3D space. This work is derived from the implementation made by Ingo Proff.

#include "Optics.hpp"

pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);

// 
// Adding data to the cloud of points ...
//

std::vector<pcl::PointIndicesPtr> clusters;
Optics::optics<pcl::PointXYZ>(cloud, neighborhoodMinPts, reachabilityThreshold, clusters);

for (const auto& cluster : clusters) {
    if (cluster->indices.size() < minPtsPerCluster) continue;
    
    // Do something with the cluster
}

You can compile and execute the example program provided:

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make
./Pcl_Optics ../table_scene_lms400.pcd

You should get the following output into the pcl visualizer:

Each color represents a different density cluster.

The only dependencies required is the Point Cloud Libary. Tests have been performed with pcl-1.8.1, pcl-1.9.0 and pcl-1.9.1 and using C++11, C++14 and C++17.

The implementation resides in a single header file making it easy to integrate into a c++ project. Just clone the repository

git clone https://github.com/Nandite/Pcl-Optics

Then copy the Optics header file located into the include directory in your project.

You will find into the resources directory a publication from Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel and Jörg Sander succinctly explaining the OPTICS algorithm.

There is also an excellent paper from Izabela Anna Wowczko of the Institute of Technology Blanchardstown explaining the principle of the algorithm.

Don't hesitate if you have any suggestions for improving this project, or if you find any error. I will be glad to hear from you. Contributions are welcomed :)

Distributed under the MIT Software License (X11 license). See accompanying file LICENSE.