VM2D::NeighborTree Class Reference

#include <cpuNeighborTree.h>

Collaboration diagram for VM2D::NeighborTree:

Public Member Functions
int	LeafBegin (int leaf) const
int	LeafEnd (int leaf) const
const NbBox &	LeafBox (int leaf) const
template<typename F>
void	Build (int n_, F getPos)
	Построение дерева; getPos(i) возвращает координаты i-й точки
void	CollectLeaves (const NbBox &q, double R, std::vector< int > &leaves) const
	Список листьев, прямоугольники которых находятся на расстоянии меньше R от прямоугольника q.

Public Attributes
int	n = 0
int	nLeaves = 0
int	firstLeaf = 1
	номер первого листа в неявном бинарном дереве (степень двойки)
std::vector< int >	idx
	исходные номера точек в порядке сортировки
std::vector< Point2D >	pos
	координаты точек в порядке сортировки
std::vector< NbBox >	box
	прямоугольники узлов: корень 1, потомки узла k — 2k и 2k+1

Static Public Attributes
static const int	leafSize = 32

Static Private Member Functions
static uint32_t	Spread (uint32_t v)

Detailed Description

Definition at line 100 of file cpuNeighborTree.h.

Member Function Documentation

Build()

template<typename F>

void VM2D::NeighborTree::Build ( int n_, F getPos )

inline

Построение дерева; getPos(i) возвращает координаты i-й точки

Definition at line 119 of file cpuNeighborTree.h.

        {
            n = n_;
            idx.resize(n);
            pos.resize(n);
 
            NbBox all;
            all.SetEmpty();
            for (int i = 0; i < n; ++i)
                all.Add(getPos(i));
 
            std::vector<uint64_t> keys(n), tmp(n);
            const double scale = std::max(all.maxx - all.minx, all.maxy - all.miny);
            const double iscale = (scale > 0.0) ? (65535.0 / scale) : 0.0;
 
#pragma omp parallel for
            for (int i = 0; i < n; ++i)
            {
                const Point2D& p = getPos(i);
                const uint32_t ix = (uint32_t)((p[0] - all.minx) * iscale);
                const uint32_t iy = (uint32_t)((p[1] - all.miny) * iscale);
                keys[i] = ((uint64_t)((Spread(ix) << 1) | Spread(iy)) << 32) | (uint32_t)i;
            }
 
            //поразрядная сортировка по старшим 32 битам (мортоновский код)
            for (int shift = 32; shift < 64; shift += 8)
            {
                size_t cnt[257] = { 0 };
                for (int i = 0; i < n; ++i)
                    ++cnt[((keys[i] >> shift) & 0xFF) + 1];
                for (int b = 0; b < 256; ++b)
                    cnt[b + 1] += cnt[b];
                for (int i = 0; i < n; ++i)
                    tmp[cnt[(keys[i] >> shift) & 0xFF]++] = keys[i];
                keys.swap(tmp);
            }
 
            for (int i = 0; i < n; ++i)
            {
                idx[i] = (int)(keys[i] & 0xFFFFFFFFu);
                pos[i] = getPos(idx[i]);
            }
 
            nLeaves = (n + leafSize - 1) / leafSize;
            firstLeaf = 1;
            while (firstLeaf < std::max(nLeaves, 1))
                firstLeaf <<= 1;
 
            box.resize(2 * firstLeaf);
#pragma omp parallel for
            for (int l = 0; l < firstLeaf; ++l)
            {
                NbBox& b = box[firstLeaf + l];
                b.SetEmpty();
                if (l < nLeaves)
                    for (int k = LeafBegin(l); k < LeafEnd(l); ++k)
                        b.Add(pos[k]);
            }
            for (int k = firstLeaf - 1; k >= 1; --k)
            {
                box[k] = box[2 * k];
                box[k].Add(box[2 * k + 1]);
            }
        }

Here is the call graph for this function:

Here is the caller graph for this function:

CollectLeaves()

void VM2D::NeighborTree::CollectLeaves ( const NbBox & q, double R, std::vector< int > & leaves ) const

inline

Список листьев, прямоугольники которых находятся на расстоянии меньше R от прямоугольника q.

Definition at line 185 of file cpuNeighborTree.h.

        {
            leaves.clear();
            if (nLeaves == 0)
                return;
            const double R2 = R * R;
            int stack[64];
            int top = 0;
            stack[top++] = 1;
            while (top > 0)
            {
                const int k = stack[--top];
                if (box[k].Dist2(q) >= R2)
                    continue;
                if (k >= firstLeaf)
                    leaves.push_back(k - firstLeaf);
                else
                {
                    stack[top++] = 2 * k + 1;
                    stack[top++] = 2 * k;
                }
            }
        }

Here is the caller graph for this function:

LeafBegin()

int VM2D::NeighborTree::LeafBegin ( int leaf ) const

inline

Definition at line 113 of file cpuNeighborTree.h.

{ return leaf * leafSize; }

Here is the caller graph for this function:

LeafBox()

const NbBox & VM2D::NeighborTree::LeafBox ( int leaf ) const

inline

Definition at line 115 of file cpuNeighborTree.h.

{ return box[firstLeaf + leaf]; }

Here is the caller graph for this function:

LeafEnd()

int VM2D::NeighborTree::LeafEnd ( int leaf ) const

inline

Definition at line 114 of file cpuNeighborTree.h.

{ return std::min(n, (leaf + 1) * leafSize); }

Here is the caller graph for this function:

Spread()

uint32_t VM2D::NeighborTree::Spread ( uint32_t v )

inlinestaticprivate

Definition at line 210 of file cpuNeighborTree.h.

        {
            v &= 0x0000FFFF;
            v = (v | (v << 8)) & 0x00FF00FF;
            v = (v | (v << 4)) & 0x0F0F0F0F;
            v = (v | (v << 2)) & 0x33333333;
            v = (v | (v << 1)) & 0x55555555;
            return v;
        }

Here is the caller graph for this function:

Member Data Documentation

box

std::vector<NbBox> VM2D::NeighborTree::box

прямоугольники узлов: корень 1, потомки узла k — 2k и 2k+1

Definition at line 111 of file cpuNeighborTree.h.

firstLeaf

int VM2D::NeighborTree::firstLeaf = 1

номер первого листа в неявном бинарном дереве (степень двойки)

Definition at line 107 of file cpuNeighborTree.h.

idx

std::vector<int> VM2D::NeighborTree::idx

исходные номера точек в порядке сортировки

Definition at line 109 of file cpuNeighborTree.h.

leafSize

const int VM2D::NeighborTree::leafSize = 32

static

Definition at line 103 of file cpuNeighborTree.h.

n

int VM2D::NeighborTree::n = 0

Definition at line 105 of file cpuNeighborTree.h.

nLeaves

int VM2D::NeighborTree::nLeaves = 0

Definition at line 106 of file cpuNeighborTree.h.

pos

std::vector<Point2D> VM2D::NeighborTree::pos

координаты точек в порядке сортировки

Definition at line 110 of file cpuNeighborTree.h.

---

The documentation for this class was generated from the following file:

• VM2D/TreeCPU2D/cpuNeighborTree.h