Suma de Minkowski de polígonos convexos

Definición

Consideremos dos conjuntos $A$ y $B$ de puntos en un plano. La suma de Minkowski $A + B$ se define como ${a + b| a \in A, b \in B}$ . Aquí consideraremos el caso en que $A$ y $B$ consisten de polígonos convexos $P$ y $Q$ con sus interiores. A lo largo de este artículo identificaremos polígonos con secuencias ordenadas de sus vértices, de modo que notaciones como $|P|$ o $P_i$ tienen sentido. Resulta que la suma de polígonos convexos $P$ y $Q$ es un polígono convexo con a lo sumo $|P| + |Q|$ vértices.

Algoritmo

Aquí consideramos que los polígonos están enumerados de forma cíclica, es decir, $P_{|P|} = P_0,\ Q_{|Q|} = Q_0$ y así sucesivamente.

Como el tamaño de la suma es lineal en términos de los tamaños de los polígonos iniciales, deberíamos apuntar a encontrar un algoritmo de tiempo lineal. Supongamos que ambos polígonos están ordenados en sentido antihorario. Consideremos las secuencias de aristas ${\overrightarrow{P_iP_{i+1}}}$ y ${\overrightarrow{Q_jQ_{j+1}}}$ ordenadas por ángulo polar. Afirmamos que la secuencia de aristas de $P + Q$ se puede obtener fusionando estas dos secuencias preservando el orden de ángulo polar y reemplazando vectores consecutivos codirigidos por su suma. El uso directo de esta idea resulta en un algoritmo de tiempo lineal; sin embargo, restaurar los vértices de $P + Q$ a partir de la secuencia de lados requiere suma repetida de vectores, lo que puede introducir problemas no deseados de precisión si trabajamos con coordenadas de punto flotante, así que describiremos una ligera modificación de esta idea.

Primero deberíamos reordenar los vértices de tal forma que el primer vértice de cada polígono tenga la menor coordenada y (en caso de varios de tales vértices elegir el de menor coordenada x). Después de eso los lados de ambos polígonos quedarán ordenados por ángulo polar, así que no hay necesidad de ordenarlos manualmente. Ahora creamos dos punteros $i$ (que apunta a un vértice de $P$ ) y $j$ (que apunta a un vértice de $Q$ ), ambos inicialmente puestos en 0. Repetimos los siguientes pasos mientras $i < |P|$ o $j < |Q|$ .

Agregar $P_i + Q_j$ a $P + Q$ .
Comparar los ángulos polares de $\overrightarrow{P_iP_{i + 1}}$ y $\overrightarrow{Q_jQ_{j+1}}$ .
Incrementar el puntero que corresponde al ángulo más pequeño (si los ángulos son iguales, incrementar ambos).

Visualización

Aquí hay una visualización agradable, que puede ayudar a entender qué está pasando.

Distancia entre dos polígonos

Una de las aplicaciones más comunes de la suma de Minkowski es computar la distancia entre dos polígonos convexos (o simplemente comprobar si se intersectan). La distancia entre dos polígonos convexos $P$ y $Q$ se define como $\min\limits_{a \in P, b \in Q} ||a - b||$ . Se puede notar que la distancia siempre se alcanza entre dos vértices o un vértice y una arista, así que podemos encontrar fácilmente la distancia en $O(|P||Q|)$ . Sin embargo, con un uso inteligente de la suma de Minkowski podemos reducir la complejidad a $O(|P| + |Q|)$ .

Si reflejamos $Q$ a través del punto $(0, 0)$ obteniendo el polígono $-Q$ , el problema se reduce a encontrar la menor distancia entre un punto en $P + (-Q)$ y $(0, 0)$ . Podemos encontrar esa distancia en tiempo lineal usando la siguiente idea. Si $(0, 0)$ está dentro o en el borde del polígono, la distancia es $0$ ; en caso contrario la distancia se alcanza entre $(0, 0)$ y algún vértice o arista del polígono. Como la suma de Minkowski se puede computar en tiempo lineal, obtenemos un algoritmo de tiempo lineal para encontrar la distancia entre dos polígonos convexos.

Implementación

Abajo está la implementación de la suma de Minkowski para polígonos con puntos enteros. Nótese que en este caso todos los cómputos se pueden hacer en enteros ya que en lugar de computar ángulos polares y compararlos de forma directa podemos mirar el signo del producto cruz de dos vectores.


struct pt{
    long long x, y;
    pt operator + (const pt & p) const {
        return pt{x + p.x, y + p.y};
    }
    pt operator - (const pt & p) const {
        return pt{x - p.x, y - p.y};
    }
    long long cross(const pt & p) const {
        return x * p.y - y * p.x;
    }
};

void reorder_polygon(vector<pt> & P){
    size_t pos = 0;
    for(size_t i = 1; i < P.size(); i++){
        if(P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
            pos = i;
    }
    rotate(P.begin(), P.begin() + pos, P.end());
}

vector<pt> minkowski(vector<pt> P, vector<pt> Q){
    // el primer vértice debe ser el más bajo
    reorder_polygon(P);
    reorder_polygon(Q);
    // debemos asegurar la indexación cíclica
    P.push_back(P[0]);
    P.push_back(P[1]);
    Q.push_back(Q[0]);
    Q.push_back(Q[1]);
    // parte principal
    vector<pt> result;
    size_t i = 0, j = 0;
    while(i < P.size() - 2 || j < Q.size() - 2){
        result.push_back(P[i] + Q[j]);
        auto cross = (P[i + 1] - P[i]).cross(Q[j + 1] - Q[j]);
        if(cross >= 0 && i < P.size() - 2)
            ++i;
        if(cross <= 0 && j < Q.size() - 2)
            ++j;
    }
    return result;
}