继续对之前的版本 Range Tree C++实现 进行优化

优化点一：用shared_ptr取代static的点数组

优化点二：参考 https://tildesites.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring16/Lectures/cg-rangetrees.pdf
https://ima.udg.edu/~sellares/ComGeo/RangeTrees4Ms.pdf
只对所有点做一次y方向的排序，然后按照y方向顺序，再给左右子树一个按照y顺序排序好的数组

#ifndef RANGE_TREE_2D_H
#define RANGE_TREE_2D_H 1

#include "Point.h"
#include <vector>
#include <memory>

class RangeTree1D
{
    friend class RangeTree2D;

protected:
    RangeTree1D(std::shared_ptr<std::vector<FloatPoint>> &data);
    ~RangeTree1D();

    bool Build(std::vector<int>& idx);

    void RangeQuery(FloatPoint& query_low, FloatPoint& query_high,
        std::vector<int>& result_idx, float ylow, float yhigh);
    void TraversalInorder(std::vector<int>& result_idx);
    bool IsLeaf();

protected:
    int keypos_;
    RangeTree1D* lchild_;
    RangeTree1D* rchild_;

    std::shared_ptr<std::vector<FloatPoint>> data_;
};


class RangeTree2D
{
public:
    RangeTree2D(const std::vector<FloatPoint>& in_data);
    ~RangeTree2D();

    bool BuildTree();
    void RangeQuery(FloatPoint&query_low, FloatPoint&query_high,
        std::vector<int>& result_idx);

protected:
    RangeTree2D(std::shared_ptr<std::vector<FloatPoint>>& data);

    bool Build(std::vector<int>& x_idx, std::vector<int>& y_idx);
    void RangeQuery(FloatPoint& query_low, FloatPoint& query_high,
        std::vector<int>& result_idx, float xlow, float xhigh);
    bool IsLeaf();

protected:
    int keypos_;
    RangeTree2D* lchild_;
    RangeTree2D* rchild_;
    RangeTree1D* ytree_;
    // 所有子孙树都共用同一份数据
    std::shared_ptr<std::vector<FloatPoint>> data_;
};


#endif

#include "RangeTree2D.h"
#include <numeric>
#include <algorithm>

const float kXMin = -1000.0;
const float kXMax = 1000.0;
const float kYMin = -1000.0;
const float kYMax = 1000.0;

typedef bool (*CompFun)(const FloatPoint&, const FloatPoint&);

static bool xless(const FloatPoint &l, const FloatPoint &r)
{
    return l.x < r.x;
}

static bool yless(const FloatPoint& l, const FloatPoint& r)
{
    return l.y < r.y;
}

template <typename T>
std::vector<int> SortIndex(const std::vector<T>& data, bool (*comp)(const T&, const T&)) 
{
    // initialize original index locations
    std::vector<int> idx(data.size());
    std::iota(idx.begin(), idx.end(), 0);
    //    for(int i=0;i<v.size();i++)  idx[i]=i;
        
    // sort indexes based on comparing values in v
    sort(idx.begin(), idx.end(), [&data, &comp](size_t i1, size_t i2) {return (*comp)(data[i1], data[i2]); });

    return idx;
}

template <typename T>
std::vector<int> SortIndex(const std::vector<T>& data, std::vector<int>& idx, 
    bool(*comp)(const T&, const T&)) 
{
    // sort indexes based on comparing values in v
    sort(idx.begin(), idx.end(), [&data, &comp](int i1, int i2) {return (*comp)(data[i1], data[i2]); });

    return idx;
}

/////////////////////////////////////////////
// class RangeTree1D
/////////////////////////////////////////////

RangeTree1D::RangeTree1D(std::shared_ptr<std::vector<FloatPoint>>& data) :
    keypos_(-1), lchild_(NULL), rchild_(NULL),
    data_(data)
{
}

RangeTree1D::~RangeTree1D()
{
    if (lchild_)
        delete lchild_;
    if (rchild_)
        delete rchild_;
}

bool RangeTree1D::Build(std::vector<int>& idx)
{
    size_t n = idx.size();
    if (n == 0)
        return false;

    size_t pos = !(n % 2) ? n / 2 - 1 : (n - 1) / 2;
    keypos_ = idx[pos];

    if (n == 1)
    {
        this->lchild_ = NULL;
        this->rchild_ = NULL;
    }
    else
    {
        std::vector<int> left, right;
        
        left.assign(idx.begin(), idx.begin() + pos + 1);
        right.assign(idx.begin() + pos + 1, idx.end());

        this->lchild_ = new RangeTree1D(data_);
        lchild_->Build(left);
        this->rchild_ = new RangeTree1D(data_);
        rchild_->Build(right);
    }

    return true;
}

void RangeTree1D::RangeQuery(FloatPoint& query_low, FloatPoint& query_high,
    std::vector<int>& result_idx, float ylow, float yhigh)
{
    if (this->IsLeaf()) // hit the leaf level?
    {
        float leaf_x = (*data_)[keypos_].x;
        float leaf_y = (*data_)[keypos_].y;

        // count if point in range
        if (leaf_y >= query_low.y && leaf_y <= query_high.y)
        {
            result_idx.push_back(keypos_);
        }
        return;
    }
    else if (query_low.y <= ylow && query_high.y >= yhigh) // Query contains entire cell?
    {
        TraversalInorder(result_idx);
        return; // return entire subtree size
    }
    else if (query_high.y < ylow || query_low.y > yhigh) // no overlap
    {
        return;
    }
    else
    {
        float leaf_y = (*data_)[keypos_].y;

        // count left side      
        lchild_->RangeQuery(query_low, query_high, result_idx, ylow, leaf_y);
        // count right side         
        rchild_->RangeQuery(query_low, query_high, result_idx, leaf_y, yhigh);
    }
}

void RangeTree1D::TraversalInorder(std::vector<int>& result_idx)
{
    if (this->IsLeaf())
        result_idx.push_back(keypos_);
    else
    {
        lchild_->TraversalInorder(result_idx);
        rchild_->TraversalInorder(result_idx);
    }
}

bool RangeTree1D::IsLeaf()
{
    return (lchild_ == NULL && rchild_ == NULL);
}

/////////////////////////////////////////////
// class RangeTree2D
/////////////////////////////////////////////

RangeTree2D::RangeTree2D(const std::vector<FloatPoint>& in_data)
    : lchild_(NULL), rchild_(NULL), ytree_(NULL)
{
    data_.reset(new std::vector<FloatPoint>(in_data));
}

RangeTree2D::RangeTree2D(std::shared_ptr<std::vector<FloatPoint>>& data)
    : lchild_(NULL), rchild_(NULL), ytree_(NULL),
    data_(data)
{
}

RangeTree2D::~RangeTree2D()
{
    if (lchild_)
        delete lchild_;
    if (rchild_)
        delete rchild_;
    if (ytree_)
        delete ytree_;
}

bool RangeTree2D::BuildTree()
{
    std::vector<int> x_idx = SortIndex(*data_, xless);
    std::vector<int> y_idx = SortIndex(*data_, yless);

    return Build(x_idx, y_idx);
}

bool RangeTree2D::Build(std::vector<int>& x_idx, std::vector<int>& y_idx)
{
    size_t n = x_idx.size();
    if (n == 0)
        return false;

    size_t pos = !(n % 2) ? n / 2 - 1 : (n - 1) / 2;
    keypos_ = x_idx[pos];

    if (n == 1)
    {
        this->lchild_ = NULL;
        this->rchild_ = NULL;
    }
    else
    {
        std::vector<int> x_left, x_right;
        std::vector<int> y_left, y_right;
        std::vector<bool> in_left;

        x_left.assign(x_idx.begin(), x_idx.begin() + pos + 1);
        x_right.assign(x_idx.begin() + pos + 1, x_idx.end());

        // Mark down which index is in left child
        in_left.resize((*data_).size(), false);
        for (auto p : x_left)
        {
            in_left[p] = true;
        }

        // Build children's y order
        for (auto p : y_idx)
        {
            if (in_left[p])
                y_left.push_back(p);
            else
                y_right.push_back(p);
        }

        this->lchild_ = new RangeTree2D(data_);
        lchild_->Build(x_left, y_left);
        this->rchild_ = new RangeTree2D(data_);
        rchild_->Build(x_right, y_right);
    }

    // build y-tree.
    this->ytree_ = new RangeTree1D(data_);
    ytree_->Build(y_idx);

    return true;
}

void RangeTree2D::RangeQuery(FloatPoint &query_low, FloatPoint &query_high,
    std::vector<int>& result_idx)
{
    result_idx.clear();

    RangeQuery(query_low, query_high, result_idx, kXMin, kXMax);
}

void RangeTree2D::RangeQuery(FloatPoint &query_low, FloatPoint &query_high,
    std::vector<int>& result_idx, float xlow, float xhigh)
{
    if (this->IsLeaf()) // hit the leaf level?
    {
        float leaf_x = (*data_)[keypos_].x;
        float leaf_y = (*data_)[keypos_].y;

        // count if point in range
        if (leaf_x >= query_low.x && leaf_x <= query_high.x
            && leaf_y >= query_low.y && leaf_y <= query_high.y)
        {
            result_idx.push_back(keypos_);
        }
        return;
    }
    else if (query_low.x <= xlow && query_high.x >= xhigh)
    {   // Query’s x-range contains C
        // search auxiliary tree
        ytree_->RangeQuery(query_low, query_high, result_idx, kYMin, kYMax);
        return;
    }
    else if (query_high.x < xlow || query_low.x > xhigh) // no overlap
    {
        return;
    }
    else
    {
        float leaf_x = (*data_)[keypos_].x;

        // count left side
        lchild_->RangeQuery(query_low, query_high, result_idx, xlow, leaf_x);
        // count right side
        rchild_->RangeQuery(query_low, query_high, result_idx, leaf_x, xhigh);
    }
}

bool RangeTree2D::IsLeaf()
{
    return (lchild_ == NULL && rchild_ == NULL);
}