relative_neighborhood_graph()

MAYAFLUX_API EdgeList MayaFlux::Kinesis::relative_neighborhood_graph

(

const Eigen::MatrixXd &

points

)

Compute relative neighborhood graph.

Parameters

points

DxN matrix where each column is a point

Returns

Edge list of RNG edges

RNG property: Edge (p,q) exists iff lune(p,q) contains no points. Lune is intersection of two circles centered at p and q, each with radius |p-q|.

Equivalently: max(|p-r|, |q-r|) ≥ |p-q| for all r ∈ P \ {p,q}

The RNG is a subset of Gabriel graph and Delaunay triangulation.

Complexity: O(n³) with geometric tests

Definition at line 504 of file ProximityGraphs.cpp.

{
    const auto n = static_cast<size_t>(points.cols());
    if (n < 2) {
        return {};
    }
 
    const auto dim = static_cast<size_t>(points.rows());
    const double* base = points.data();
 
    const std::vector<double> table = build_distance_table(points);
    const bool resident = !table.empty();
 
    std::vector<EdgeList> bins(n);
 
    std::for_each(std::execution::par_unseq,
        std::views::iota(size_t { 0 }, n).begin(),
        std::views::iota(size_t { 0 }, n).end(),
        [&](size_t i) {
            const double* row_i = resident ? table.data() + i * n : nullptr;
            const double* pi = base + i * dim;
            EdgeList& out = bins[i];
 
            for (size_t j = i + 1; j < n; ++j) {
                const double pq_sq = resident
                    ? row_i[j]
                    : dist_sq(pi, base + j * dim, dim);
 
                const bool rejected = resident
                    ? max_below(row_i, table.data() + j * n, n, pq_sq)
                    : max_below_direct(base, dim, n, i, j, pq_sq);
 
                if (!rejected) {
                    out.emplace_back(i, j);
                }
            }
        });
 
    EdgeList edges = flatten_bins(bins);
 
    MF_DEBUG(Journal::Component::Kinesis, Journal::Context::Runtime,
        "relative_neighborhood_graph: {} points, generated {} edges",
        n, edges.size());
 
    return edges;
}

References MayaFlux::Journal::Kinesis, MF_DEBUG, out, points, and MayaFlux::Journal::Runtime.

Referenced by generate_proximity_graph().

Here is the caller graph for this function: