gabriel_graph()

MAYAFLUX_API 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 408 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
                    ? sum_below(row_i, table.data() + j * n, n, pq_sq)
                    : sum_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,
        "gabriel_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: