Creating Bipartite Graph for incremental Convex Hull

Question

I'm trying to create some classes to build a 3D Convex Hull of a cloud of points in O(N*logN).

I have already solved the naive problem that has a complexity of O(N²) where N is the number of points. It works like this:

I've a std::list of points. These points are istance of a class that I've created. I randomize the list and extract one by one all the points from the list. For every point I check which facets are visible from that point. So, the complexity is too high, because facets are O(N) (more than 6*N)

Then I do some operations to delete visible facets, find horizon and link the point with horizon. Informations about these operation will not help to solve my problem.

What I need is an example for creating and handling a bipartite graph that will be quick in add and remove nodes.

I tried to build my own classes, but I failed because my graph was too slow. But some days ago I found that the boost library has the solution: this.

But I'm stuck with how to create my simple graph with all these options, I don't understand how to create it. I've read so many times this documentation...

Now, the question is: how can I build a bipartite graph using boost?

it must be:

• bidirectional;
• bipartite: one type of node will be Pointd the other type will be Dcel::Face;
• the Pointd Nodes must link all the facets that the point can see;
• the Dcel::Face method must link all the point that can see it.
• quick remove and add operations.

I don't care about memory usage. I just need it to be quick.

This is my first question, so I don't know if it's clear or not. If someone will be so kind to give me an example of how I can build a graph with these characteristic I gave you, it will be great. If you know some other way to create it easily, it will be good either.

Answer 1

When you say bidirectional, I assume you mean undirected. If it means you want your graph to be directed but to have access to both in and out edges of a vertex, then just replace boost::undirectedS with boost::bidirectionalS Regarding its creation, here is what you could do:

#include <cstdint>
#include <boost/graph/adjacency_list.hpp>

enum class vertex_kind : std::uint8_t {
    POINTD,
    DCEL_FACE,
    UNKNOWN
};

struct pointd_property { /* Whatever is needed */ };
struct dcel_face_property { /* Whatever is needed */};

struct vertex_property {
    vertex_kind kind;
    union {
        pointd_property pointd;
        dcel_face_property dcel_face;
    };
    vertex_property() : kind(vertex_kind::UNKNOWN) {}
    vertex_property(pointd_property const& pprop) : kind(vertex_kind::POINTD) { new (&pointd) pointd_property(pprop); }
    vertex_property(dcel_face_property const& fprop) : kind(vertex_kind::DCEL_FACE) { new (&dcel_face) dcel_face_property(fprop); }
};

typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, vertex_property> graph_type;

Now populating the graph is quite easy:

auto graph = []() {
    graph_type g;
    auto a = boost::add_vertex({pointd_property()}, g);
    auto b = boost::add_vertex({dcel_face_property()}, g);
    boost::add_edge(a, b, g);
    return g;
} ();
// Do whatever you please with g.

Of course the content of the vertex property should be in line with the requirement of the algorithm from the BGL you intend to use. If there are any requirements, let me know so I can edit my answer.