relative_neighborhood_graph()

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 242 of file ProximityGraphs.cpp.

{
    Eigen::Index n = points.cols();
    if (n < 2) {
        return {};
    }
 
    EdgeList edges;
 
    for (Eigen::Index i = 0; i < n; ++i) {
        for (Eigen::Index j = i + 1; j < n; ++j) {
            Eigen::VectorXd p = points.col(i);
            Eigen::VectorXd q = points.col(j);
 
            double pq_dist = distance(p, q);
            bool is_rng_edge = true;
 
            for (Eigen::Index k = 0; k < n; ++k) {
                if (k == i || k == j)
                    continue;
 
                Eigen::VectorXd r = points.col(k);
 
                double pr_dist = distance(p, r);
                double qr_dist = distance(q, r);
 
                double max_dist = std::max(pr_dist, qr_dist);
 
                if (max_dist < pq_dist) {
                    is_rng_edge = false;
                    break;
                }
            }
 
            if (is_rng_edge) {
                edges.emplace_back(static_cast<size_t>(i), static_cast<size_t>(j));
            }
        }
    }
 
    MF_DEBUG(Journal::Component::Kinesis, Journal::Context::Runtime,
        "relative_neighborhood_graph: {} points, generated {} edges",
        n, edges.size());
 
    return edges;
}

References distance(), MayaFlux::Journal::Kinesis, MF_DEBUG, q, and MayaFlux::Journal::Runtime.

Referenced by generate_proximity_graph().

Here is the call graph for this function:

Here is the caller graph for this function: