Encontrar las caras de un grafo planar
Consideremos un grafo con vértices y aristas, que se puede dibujar en un plano de tal forma que dos aristas se intersectan solo en un vértice común (si existe). Tales grafos se llaman planares. Ahora supongamos que nos dan un grafo planar junto con su embebido rectilíneo (straight-line embedding), lo que significa que para cada vértice tenemos un punto correspondiente y todas las aristas se dibujan como segmentos de recta entre estos puntos sin intersección (tal embebido siempre existe). Estos segmentos de recta parten el plano en varias regiones, que se llaman caras. Exactamente una de las caras es no acotada. Esta cara se llama exterior, mientras que las demás caras se llaman interiores.
En este artículo trataremos de encontrar tanto las caras interiores como la exterior de un grafo planar. Asumiremos que el grafo es conexo.
Algunos hechos sobre grafos planares
En esta sección presentamos varios hechos sobre grafos planares sin demostración. Los lectores interesados en las demostraciones deberían consultar Graph Theory by R. Diestel (véase también clases en video sobre planaridad basadas en este libro) u otro libro.
Teorema de Euler
El teorema de Euler afirma que cualquier embebido correcto de un grafo planar conexo con vértices, aristas y caras satisface:
Y de forma más general, todo grafo planar con componentes conexas satisface:
Número de aristas de un grafo planar.
Si entonces el número máximo de aristas de un grafo planar con vértices es . Este número se alcanza por cualquier grafo planar conexo donde cada cara está acotada por un triángulo. En términos de complejidad este hecho significa que para cualquier grafo planar.
Número de caras de un grafo planar.
Como consecuencia directa del hecho de arriba, si entonces el número máximo de caras de un grafo planar con vértices es .
Grado mínimo de vértice en un grafo planar.
Todo grafo planar tiene un vértice de grado 5 o menos.
El algoritmo
Primero, ordenar las aristas adyacentes de cada vértice por ángulo polar. Ahora recorramos el grafo de la siguiente forma. Supongamos que entramos al vértice a través de la arista y es la siguiente arista después de en la lista de adyacencia ordenada de . Entonces el siguiente vértice será . Resulta que si empezamos este recorrido en alguna arista , recorreremos exactamente una de las caras adyacentes a , la cara exacta dependiendo de si nuestro primer paso es de a o de a .
Ahora el algoritmo es bastante obvio. Debemos iterar sobre todas las aristas del grafo y empezar el recorrido para cada arista que no fue visitada por uno de los recorridos anteriores. De esta forma encontraremos cada cara exactamente una vez, y cada arista se recorrerá dos veces (una en cada dirección).
Encontrar la siguiente arista
Durante el recorrido tenemos que encontrar la siguiente arista en orden antihorario. La forma más obvia de encontrar la siguiente arista es búsqueda binaria por ángulo. Sin embargo, dado el orden antihorario de las aristas adyacentes de cada vértice, podemos precomputar las siguientes aristas y guardarlas en una tabla hash. Si las aristas ya están ordenadas por ángulo, la complejidad de encontrar todas las caras en este caso se vuelve lineal.
Encontrar la cara exterior
No es difícil ver que el algoritmo recorre cada cara interior en orden horario y la cara exterior en orden antihorario, así que la cara exterior se puede encontrar comprobando el orden de cada cara.
Complejidad
Es bastante claro que la complejidad del algoritmo es por el ordenamiento, y como , es de hecho . Como se mencionó antes, sin ordenamiento la complejidad se vuelve .
¿Qué pasa si el grafo no es conexo?
A primera vista puede parecer que encontrar las caras de un grafo no conexo no es mucho más difícil porque podemos ejecutar el mismo algoritmo para cada componente conexa. Sin embargo, las componentes pueden dibujarse de forma anidada, formando agujeros (véase la imagen de abajo). En este caso la cara interior de alguna componente se convierte en la cara exterior de algunas otras componentes y tiene un borde desconectado complejo. Lidiar con tales casos es bastante difícil; un enfoque posible es identificar componentes anidadas con algoritmos de localización de puntos.
Implementación
La siguiente implementación devuelve un vector de vértices para cada cara; la cara exterior va primero. Las caras interiores se devuelven en orden antihorario y la cara exterior se devuelve en orden horario.
Por simplicidad encontramos la siguiente arista haciendo búsqueda binaria por ángulo.
struct Point {
int64_t x, y;
Point(int64_t x_, int64_t y_): x(x_), y(y_) {}
Point operator - (const Point & p) const {
return Point(x - p.x, y - p.y);
}
int64_t cross (const Point & p) const {
return x * p.y - y * p.x;
}
int64_t cross (const Point & p, const Point & q) const {
return (p - *this).cross(q - *this);
}
int half () const {
return int(y < 0 || (y == 0 && x < 0));
}
};
std::vector<std::vector<size_t>> find_faces(std::vector<Point> vertices, std::vector<std::vector<size_t>> adj) {
size_t n = vertices.size();
std::vector<std::vector<char>> used(n);
for (size_t i = 0; i < n; i++) {
used[i].resize(adj[i].size());
used[i].assign(adj[i].size(), 0);
auto compare = [&](size_t l, size_t r) {
Point pl = vertices[l] - vertices[i];
Point pr = vertices[r] - vertices[i];
if (pl.half() != pr.half())
return pl.half() < pr.half();
return pl.cross(pr) > 0;
};
std::sort(adj[i].begin(), adj[i].end(), compare);
}
std::vector<std::vector<size_t>> faces;
for (size_t i = 0; i < n; i++) {
for (size_t edge_id = 0; edge_id < adj[i].size(); edge_id++) {
if (used[i][edge_id]) {
continue;
}
std::vector<size_t> face;
size_t v = i;
size_t e = edge_id;
while (!used[v][e]) {
used[v][e] = true;
face.push_back(v);
size_t u = adj[v][e];
size_t e1 = std::lower_bound(adj[u].begin(), adj[u].end(), v, [&](size_t l, size_t r) {
Point pl = vertices[l] - vertices[u];
Point pr = vertices[r] - vertices[u];
if (pl.half() != pr.half())
return pl.half() < pr.half();
return pl.cross(pr) > 0;
}) - adj[u].begin() + 1;
if (e1 == adj[u].size()) {
e1 = 0;
}
v = u;
e = e1;
}
std::reverse(face.begin(), face.end());
Point p1 = vertices[face[0]];
__int128 sum = 0;
for (int j = 0; j < face.size(); ++j) {
Point p2 = vertices[face[j]];
Point p3 = vertices[face[(j + 1) % face.size()]];
sum += (p2 - p1).cross(p3 - p2);
}
if (sum <= 0) {
faces.insert(faces.begin(), face);
} else {
faces.emplace_back(face);
}
}
}
return faces;
}Construir un grafo planar a partir de segmentos de recta
A veces no nos dan un grafo de forma explícita, sino como un conjunto de segmentos de recta en un plano, y el grafo real se forma intersectando esos segmentos, como se muestra en la imagen de abajo. En este caso hay que construir el grafo manualmente. La forma más fácil de hacerlo es la siguiente. Fijar un segmento e intersectarlo con todos los demás segmentos. Luego ordenar todos los puntos de intersección junto con los dos extremos del segmento lexicográficamente y agregarlos al grafo como vértices. También enlazar cada dos vértices adyacentes en orden lexicográfico por una arista. Después de hacer este procedimiento para todas las aristas obtendremos el grafo. Por supuesto, debemos asegurar que dos puntos de intersección iguales siempre corresponderán al mismo vértice. La forma más fácil de hacer esto es guardar los puntos en un mapa por sus coordenadas, considerando como iguales los puntos cuyas coordenadas difieren en un número pequeño (digamos, menos de ). Este algoritmo funciona en .
Implementación
using dbl = long double;
const dbl eps = 1e-9;
struct Point {
dbl x, y;
Point(){}
Point(dbl x_, dbl y_): x(x_), y(y_) {}
Point operator * (dbl d) const {
return Point(x * d, y * d);
}
Point operator + (const Point & p) const {
return Point(x + p.x, y + p.y);
}
Point operator - (const Point & p) const {
return Point(x - p.x, y - p.y);
}
dbl cross (const Point & p) const {
return x * p.y - y * p.x;
}
dbl cross (const Point & p, const Point & q) const {
return (p - *this).cross(q - *this);
}
dbl dot (const Point & p) const {
return x * p.x + y * p.y;
}
dbl dot (const Point & p, const Point & q) const {
return (p - *this).dot(q - *this);
}
bool operator < (const Point & p) const {
if (fabs(x - p.x) < eps) {
if (fabs(y - p.y) < eps) {
return false;
} else {
return y < p.y;
}
} else {
return x < p.x;
}
}
bool operator == (const Point & p) const {
return fabs(x - p.x) < eps && fabs(y - p.y) < eps;
}
bool operator >= (const Point & p) const {
return !(*this < p);
}
};
struct Line{
Point p[2];
Line(Point l, Point r){p[0] = l; p[1] = r;}
Point& operator [](const int & i){return p[i];}
const Point& operator[](const int & i)const{return p[i];}
Line(const Line & l){
p[0] = l.p[0]; p[1] = l.p[1];
}
Point getOrth()const{
return Point(p[1].y - p[0].y, p[0].x - p[1].x);
}
bool hasPointLine(const Point & t)const{
return std::fabs(p[0].cross(p[1], t)) < eps;
}
bool hasPointSeg(const Point & t)const{
return hasPointLine(t) && t.dot(p[0], p[1]) < eps;
}
};
std::vector<Point> interLineLine(Line l1, Line l2){
if(std::fabs(l1.getOrth().cross(l2.getOrth())) < eps){
if(l1.hasPointLine(l2[0]))return {l1[0], l1[1]};
else return {};
}
Point u = l2[1] - l2[0];
Point v = l1[1] - l1[0];
dbl s = u.cross(l2[0] - l1[0])/u.cross(v);
return {Point(l1[0] + v * s)};
}
std::vector<Point> interSegSeg(Line l1, Line l2){
if (l1[0] == l1[1]) {
if (l2[0] == l2[1]) {
if (l1[0] == l2[0])
return {l1[0]};
else
return {};
} else {
if (l2.hasPointSeg(l1[0]))
return {l1[0]};
else
return {};
}
}
if (l2[0] == l2[1]) {
if (l1.hasPointSeg(l2[0]))
return {l2[0]};
else
return {};
}
auto li = interLineLine(l1, l2);
if (li.empty())
return li;
if (li.size() == 2) {
if (l1[0] >= l1[1])
std::swap(l1[0], l1[1]);
if (l2[0] >= l2[1])
std::swap(l2[0], l2[1]);
std::vector<Point> res(2);
if (l1[0] < l2[0])
res[0] = l2[0];
else
res[0] = l1[0];
if (l1[1] < l2[1])
res[1] = l1[1];
else
res[1] = l1[1];
if (res[0] == res[1])
res.pop_back();
if (res.size() == 2u && res[1] < res[0])
return {};
else
return res;
}
Point cand = li[0];
if (l1.hasPointSeg(cand) && l2.hasPointSeg(cand))
return {cand};
else
return {};
}
std::pair<std::vector<Point>, std::vector<std::vector<size_t>>> build_graph(std::vector<Line> segments) {
std::vector<Point> p;
std::vector<std::vector<size_t>> adj;
std::map<std::pair<int64_t, int64_t>, size_t> point_id;
auto get_point_id = [&](Point pt) {
auto repr = std::make_pair(
int64_t(std::round(pt.x * 1000000000) + 1e-6),
int64_t(std::round(pt.y * 1000000000) + 1e-6)
);
if (!point_id.count(repr)) {
adj.emplace_back();
size_t id = point_id.size();
point_id[repr] = id;
p.push_back(pt);
return id;
} else {
return point_id[repr];
}
};
for (size_t i = 0; i < segments.size(); i++) {
std::vector<size_t> curr = {
get_point_id(segments[i][0]),
get_point_id(segments[i][1])
};
for (size_t j = 0; j < segments.size(); j++) {
if (i == j)
continue;
auto inter = interSegSeg(segments[i], segments[j]);
for (auto pt: inter) {
curr.push_back(get_point_id(pt));
}
}
std::sort(curr.begin(), curr.end(), [&](size_t l, size_t r) { return p[l] < p[r]; });
curr.erase(std::unique(curr.begin(), curr.end()), curr.end());
for (size_t j = 0; j + 1 < curr.size(); j++) {
adj[curr[j]].push_back(curr[j + 1]);
adj[curr[j + 1]].push_back(curr[j]);
}
}
for (size_t i = 0; i < adj.size(); i++) {
std::sort(adj[i].begin(), adj[i].end());
// quitar aristas que se agregaron varias veces
adj[i].erase(std::unique(adj[i].begin(), adj[i].end()), adj[i].end());
}
return {p, adj};
}