gabriel_graph()

EdgeList MayaFlux::Kinesis::gabriel_graph

(

const Eigen::MatrixXd &

points

)

Compute Gabriel graph.

Parameters

points

DxN matrix where each column is a point

Returns

Edge list of Gabriel edges

Gabriel property: Edge (p,q) exists iff disk with diameter pq contains no other points. Subset of Delaunay triangulation.

The Gabriel graph is a proximity graph defined by the following rule: Two points p and q are connected if and only if the closed disk having the line segment pq as diameter contains no other points.

Equivalently: |p-r|² + |q-r|² ≥ |p-q|² for all r ∈ P \ {p,q}

Complexity: O(n³) with naive geometric tests

Definition at line 161 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_sq = distance_squared(p, q);
            bool is_gabriel_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_sq = distance_squared(p, r);
                double qr_dist_sq = distance_squared(q, r);
 
                if (pr_dist_sq + qr_dist_sq < pq_dist_sq) {
                    is_gabriel_edge = false;
                    break;
                }
            }
 
            if (is_gabriel_edge) {
                edges.emplace_back(static_cast<size_t>(i), static_cast<size_t>(j));
            }
        }
    }
 
    MF_DEBUG(Journal::Component::Kinesis, Journal::Context::Runtime,
        "gabriel_graph: {} points, generated {} edges",
        n, edges.size());
 
    return edges;
}

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

Referenced by generate_proximity_graph().

Here is the caller graph for this function: