nearest_neighbor_graph()

EdgeList MayaFlux::Kinesis::nearest_neighbor_graph

(

const Eigen::MatrixXd &

points

)

Compute nearest neighbor graph.

Parameters

points

DxN matrix where each column is a point

Returns

Edge list of nearest neighbor edges

Connects each point to its single nearest neighbor. Directed graph: point i connects to nearest neighbor j, but j may connect to a different point k.

Complexity: O(n²) brute force

Definition at line 206 of file ProximityGraphs.cpp.

{
    Eigen::Index n = points.cols();
    if (n < 2) {
        return {};
    }
 
    EdgeList edges;
    edges.reserve(n);
 
    for (Eigen::Index i = 0; i < n; ++i) {
        double min_dist_sq = std::numeric_limits<double>::max();
        size_t nearest = i;
 
        for (Eigen::Index j = 0; j < n; ++j) {
            if (i == j)
                continue;
 
            double dist_sq = distance_squared(points.col(i), points.col(j));
            if (dist_sq < min_dist_sq) {
                min_dist_sq = dist_sq;
                nearest = static_cast<size_t>(j);
            }
        }
 
        if (nearest != static_cast<size_t>(i)) {
            edges.emplace_back(static_cast<size_t>(i), nearest);
        }
    }
 
    MF_DEBUG(Journal::Component::Kinesis, Journal::Context::Runtime,
        "nearest_neighbor_graph: {} points, generated {} edges", n, edges.size());
 
    return edges;
}

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

Referenced by generate_proximity_graph().

Here is the caller graph for this function: