k_nearest()

template<typename PointT >

std::vector< QueryResult > MayaFlux::Kinesis::SpatialIndex< PointT >::k_nearest	(	const PointT &	center,
		uint32_t	k
	)		const

Find the k nearest entities to a point.

Parameters

center	Query origin.
k	Maximum number of results.

Returns

Results sorted by ascending squared distance. May return fewer than k.

Definition at line 270 of file SpatialIndex.cpp.

{
#ifdef MAYAFLUX_PLATFORM_MACOS
    auto [snap, slot] = acquire_snapshot();
    if (!snap || snap->positions.empty()) {
        if (snap)
            release_snapshot(slot);
        return {};
    }
#else
    auto snap_ptr = m_snapshot.load(std::memory_order_acquire);
    if (!snap_ptr || snap_ptr->positions.empty()) {
        return {};
    }
    const auto* snap = snap_ptr.get();
#endif
 
    k = std::min(k, static_cast<uint32_t>(snap->positions.size()));
 
    auto cmp = [](const QueryResult& a, const QueryResult& b) {
        return a.distance_sq < b.distance_sq;
    };
    std::priority_queue<QueryResult, std::vector<QueryResult>, decltype(cmp)> heap(cmp);
 
    for (uint32_t i = 0; i < static_cast<uint32_t>(snap->positions.size()); ++i) {
        float d_sq = m_distance_fn(center, snap->positions[i]);
        if (heap.size() < k) {
            heap.push({ snap->slot_to_id[i], d_sq });
        } else if (d_sq < heap.top().distance_sq) {
            heap.pop();
            heap.push({ snap->slot_to_id[i], d_sq });
        }
    }
 
    std::vector<QueryResult> results;
    results.reserve(heap.size());
    while (!heap.empty()) {
        results.push_back(heap.top());
        heap.pop();
    }
    std::ranges::reverse(results);
 
#ifdef MAYAFLUX_PLATFORM_MACOS
    release_snapshot(slot);
#endif
 
    return results;
}

References a, and b.