Some Algorithms

namespace: algorithm

OnePiece also implements some other algorithms. This part of the content is a summary of algorithms used in author's projects. As you will see in example, using this part can also do some interesting work.

Clutering.h

Three clustering algorithms are implemented in Clutering.h: KMeans(based on OpenCV), MeansShift, KMediods.

//KMeans based on opencv
template <int T >
void KMeansClustering(const std::vector<Eigen::Matrix<geometry::scalar,T,1>, 
    Eigen::aligned_allocator<Eigen::Matrix<geometry::scalar,T,1>> > & wait_to_cluster, std::vector<Cluster<T>> &clustering_result, int K);
//MeansShift
template <int T >
void MeansShiftClustering(const std::vector<Eigen::Matrix<geometry::scalar,T,1>, 
    Eigen::aligned_allocator<Eigen::Matrix<geometry::scalar,T,1>> > & wait_to_cluster, std::vector<Cluster<T>> &clustering_result, float radius);
//KMedoids
template <int T >
void KMedoidsClustering(const std::vector<Eigen::Matrix<geometry::scalar,T,1>, 
    Eigen::aligned_allocator<Eigen::Matrix<geometry::scalar,T,1>> > & wait_to_cluster, std::vector<Cluster<T>> &clustering_result, int target_number, bool initialized = false, const std::vector<int> & initialized_index = std::vector<int>());
//For the above three kinds of clustering, you need to determine the vector dimension of the clustered object when writing the code
//KMedoidsClusteringDynamic can handle the dynamic vector dimension
void KMedoidsClusteringDynamic(const geometry::PointXList & wait_to_cluster, 
    std::vector<ClusterDynamic> &clustering_result, int target_number, bool initialized = false, 
    const std::vector<int> & initialized_index = std::vector<int>());

PatchDetection.h

Line detection for 2D points and plane detection for 3D points are implemented in PatchDetection.h.

void LineDetection(const geometry::Point2List &points, 
    std::vector<LinePatch> &results);
void PlaneDetection(const geometry::Point3List &points, 
    std::vector<PlanePatch> &Patches);

DCEL.h

DCEL.h implemented a 'Doubly Connected Edge List', a famous data structure in computational geometry, which can be used to depict the 'Line Arrangements'('Cell Complex'). After many lines(planes) intersect in a space, some grids are formed. These grids are like cells, which are so called cell complex.If you use DCEL to describe it, you can add lines to it at will (or remove a certain line, which is rarely used). It is also easy to find the grids through which a certain line passes, and to locate the grid that contains a given point, with little computation. Anyway, DCEL is a very powerful tool.

Line Arrangements

DCEL has two main member function:

//Insert a line into DCEL
void IncrementLine(const geometry::Line &line);
//Remove a certain line(Needs more tests)
void ReductLine(int line_id);

Although it looks quiet easy, the implementation is actually a little complex.

Arrangements.h

Arrangements.h are used to help build a 'DCEL'. It can be used to find all the intersection points of multiple lines to determine the volume of the bounding box.

You can see a demostration of Line Arrangements here: Line Arrangements

Using Algorithm, we can implement a 2D map detection of rooms.