radius_threshold_graph()

MAYAFLUX_API EdgeList MayaFlux::Kinesis::radius_threshold_graph	(	const Eigen::MatrixXd &	points,
		double	radius
	)

Compute radius threshold graph.

Parameters

points	Dx N matrix where each column is a point
radius	Maximum connection distance

Returns

Edge list (point index pairs)

Connects all point pairs within radius distance. Undirected graph: if (i,j) exists, edge appears once.

Complexity: O(n²) brute force

Definition at line 307 of file ProximityGraphs.cpp.

{
    const auto n = static_cast<size_t>(points.cols());
    if (n < 2) {
        return {};
    }
 
    const double radius_sq = radius * radius;
    const auto dim = static_cast<size_t>(points.rows());
    const double* base = points.data();
 
    std::vector<size_t> offsets(n + 1, 0);
 
    P::for_each(P::par_unseq,
        std::views::iota(size_t { 0 }, n).begin(),
        std::views::iota(size_t { 0 }, n).end(),
        [&](size_t i) {
            const double* pi = base + i * dim;
            size_t count = 0;
            for (size_t j = i + 1; j < n; ++j) {
                if (dist_sq(pi, base + j * dim, dim) <= radius_sq) {
                    ++count;
                }
            }
            offsets[i + 1] = count;
        });
 
    for (size_t i = 0; i < n; ++i) {
        offsets[i + 1] += offsets[i];
    }
 
    EdgeList edges(offsets[n]);
 
    P::for_each(P::par_unseq,
        std::views::iota(size_t { 0 }, n).begin(),
        std::views::iota(size_t { 0 }, n).end(),
        [&](size_t i) {
            const double* pi = base + i * dim;
            size_t at = offsets[i];
            for (size_t j = i + 1; j < n; ++j) {
                if (dist_sq(pi, base + j * dim, dim) <= radius_sq) {
                    edges[at++] = { i, j };
                }
            }
        });
 
    MF_DEBUG(Journal::Component::Kinesis, Journal::Context::Runtime,
        "radius_threshold_graph: {} points, radius={:.3f}, generated {} edges",
        n, radius, edges.size());
 
    return edges;
}

References count, MayaFlux::Journal::Kinesis, MF_DEBUG, points, radius, and MayaFlux::Journal::Runtime.

Referenced by generate_proximity_graph().

Here is the caller graph for this function: