Collaboration diagram for Slic3r::NearestPoints< K >:

Public Member Functions
	NearestPoints (const std::vector< Vec2d > &points)
template<typename Filter>
std::array< size_t, K >	query (const Vec2d &q, Filter filter) const

Static Public Attributes
static constexpr size_t	npos = size_t(-1)

Private Member Functions
size_t	cell (const Vec2d &p) const

Private Attributes
const std::vector< Vec2d > &	m_points
Vec2d	m_origin
double	m_cell
int	m_cols
int	m_rows
std::vector< size_t >	m_first
std::vector< size_t >	m_index

Detailed Description

template<size_t K>
class Slic3r::NearestPoints< K >

Constructor & Destructor Documentation

◆ NearestPoints()

template<size_t K>

Slic3r::NearestPoints< K >::NearestPoints ( const std::vector< Vec2d > & points )

inlineexplicit

                                                         : m_points(points)
  {
    BoundingBoxf bbox;
    for (const Vec2d &p : points)
      bbox.merge(p);
    const Vec2d  size  = bbox.size();
    const double count = double(std::max<size_t>(points.size(), 1));
    m_cell   = std::max(std::sqrt(2. * size.x() * size.y() / count), std::max(size.x(), size.y()) / count);
    if (m_cell <= 0.)
      m_cell = 1.;
    m_origin = bbox.min;
    m_cols   = int(size.x() / m_cell) + 1;
    m_rows   = int(size.y() / m_cell) + 1;
    m_first.assign(size_t(m_cols) * m_rows + 1, 0);
    for (const Vec2d &p : points)
      ++ m_first[cell(p) + 1];
    for (size_t c = 1; c < m_first.size(); ++ c)
      m_first[c] += m_first[c - 1];
    m_index.resize(points.size());
    std::vector<size_t> next(m_first.begin(), m_first.end() - 1);
    for (size_t i = 0; i < points.size(); ++ i)
      m_index[next[cell(points[i])] ++] = i;
  }

References cell(), count, m_cell, m_cols, m_first, m_index, m_origin, m_points, m_rows, Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), Slic3r::BoundingBoxBase< PointType, APointsType >::min, and Slic3r::BoundingBoxBase< PointType, APointsType >::size().

Here is the call graph for this function:

Member Function Documentation

◆ cell()

template<size_t K>

size_t Slic3r::NearestPoints< K >::cell ( const Vec2d & p ) const

inlineprivate

  {
    const int x = std::clamp(int((p.x() - m_origin.x()) / m_cell), 0, m_cols - 1);
    const int y = std::clamp(int((p.y() - m_origin.y()) / m_cell), 0, m_rows - 1);
    return size_t(y) * m_cols + x;
  }

References m_cell, m_cols, m_origin, and m_rows.

Referenced by NearestPoints().

Here is the caller graph for this function:

◆ query()

template<size_t K>

template<typename Filter>

std::array< size_t, K > Slic3r::NearestPoints< K >::query	(	const Vec2d &	q,
		Filter	filter ) const

inline

  {
    std::array<std::pair<double, size_t>, K> best;
    size_t found = 0;
    const int cx = int(std::clamp(std::floor((q.x() - m_origin.x()) / m_cell), 0., double(m_cols - 1)));
    const int cy = int(std::clamp(std::floor((q.y() - m_origin.y()) / m_cell), 0., double(m_rows - 1)));
    auto visit = [&](int x, int y) {
      if (x < 0 || y < 0 || x >= m_cols || y >= m_rows)
        return;
      const size_t c = size_t(y) * m_cols + x;
      for (size_t k = m_first[c]; k < m_first[c + 1]; ++ k) {
        const size_t i = m_index[k];
        if (! filter(i))
          continue;
        const std::pair<double, size_t> candidate((m_points[i] - q).squaredNorm(), i);
        if (found == K && ! (candidate < best[K - 1]))
          continue;
        auto it = std::upper_bound(best.begin(), best.begin() + found, candidate);
        std::move_backward(it, best.begin() + std::min(found, K - 1), best.begin() + std::min(found + 1, K));
        *it = candidate;
        found = std::min(found + 1, K);
      }
    };
    // Points beyond ring r are at least r cells away.
    for (int r = 0; r <= std::max(m_cols, m_rows); ++ r) {
      if (r == 0)
        visit(cx, cy);
      for (int d = -r; d <= r && r > 0; ++ d) {
        visit(cx + d, cy - r);
        visit(cx + d, cy + r);
        if (d != -r && d != r) {
          visit(cx - r, cy + d);
          visit(cx + r, cy + d);
        }
      }
      if (found == K && best[K - 1].first <= sqr(r * m_cell))
        break;
    }
    std::array<size_t, K> out;
    out.fill(npos);
    for (size_t k = 0; k < found; ++ k)
      out[k] = best[k].second;
    return out;
  }