SearchAlgorithms.h

Go to the documentation of this file.

/*
 * Copyright (c) 2020, Alysson Ribeiro da Silva
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 * 
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 * 
 * 3. All advertising materials mentioning features or use of this software must
 *    display the following acknowledgement:
 *    This product includes software developed by Alysson Ribeiro da Silva.
 * 
 * 4. Neither the name of the copyright holder nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 * 
 * 5. The source and the binary form, and any modifications made to them
 *    may not be used for the purpose of training or improving machine learning
 *    algorithms, including but not limited to artificial intelligence, natural
 *    language processing, or data mining. This condition applies to any derivatives,
 *    modifications, or updates based on the Software code. Any usage of the source
 *    or the binary form in an AI-training dataset is considered a breach of
 *    this License.
 * 
 * THIS SOFTWARE IS PROVIDED BY COPYRIGHT HOLDER "AS IS" AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
 * EVENT SHALL COPYRIGHT HOLDER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#ifndef SEARCH_ALGORITHMS_H
#define SEARCH_ALGORITHMS_H
 
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <exception>
#include <list>
#include <vector>
#include <limits>
#include "nav_msgs/OccupancyGrid.h"
#include "Common.h"
 
namespace sa {
    void InitOccFrom(nav_msgs::OccupancyGrid& rInput, nav_msgs::OccupancyGrid& rOutput);
    bool IsInBounds(nav_msgs::OccupancyGrid& rInput, Vec2i& rPos);
    bool CheckAny(nav_msgs::OccupancyGrid& rInput, const Vec2i& rStart, const Vec2i& rEnd, const int& rVal);
    void ComputePath(nav_msgs::OccupancyGrid& rOcc, 
                     const Vec2i& rStart, 
                     const Vec2i& rEnd, 
                     std::list<Vec2i>& rOutPath);
    void ComputePathWavefront(
        nav_msgs::OccupancyGrid& rInput, 
        const Vec2i& rStart, 
        const Vec2i& rEnd, 
        std::list<Vec2i>& rOutPath);
    void ComputeFrontiers(nav_msgs::OccupancyGrid& rInput,  
                          nav_msgs::OccupancyGrid& rOutput, 
                          std::vector<Vec2i>& rFrontiers);
    void ComputeClusters(nav_msgs::OccupancyGrid& rFrontiersMap, 
                         std::vector<Vec2i>& rFrontiers, 
                         std::vector<std::vector<Vec2i>>& rOutClusters);
    Vec2i ClosestFrontierCluster(const Vec2i& rPos, std::vector<Vec2i>& rCluster);
    Vec2i MedianFrontierCluster(const Vec2i& rPos, std::vector<Vec2i>& rCluster);
    void ComputeCentroids(const Vec2i& rPos, 
                          std::vector<std::vector<Vec2i>>& rClusters, 
                          std::vector<Vec2i>& rOutCentroids);
    void ComputeAverageCentroids(const Vec2i& rPos, 
                        std::vector<std::vector<Vec2i>>& rClusters, 
                        std::vector<Vec2i>& rOutCentroids);
};
#endif