Método del Calibre Giratorio

En Geometría computacional, el Método del Calibre Giratorio (en inglés, Rotating Caliper) es un método usado para construir algoritmos eficientes para varios problemas, como el diámetro de un conjunto de puntos o Mayor distancia entre dos polígonos convexos.

Secuencia de medidas tomadas entre pares antipodales del cierre convexo de un polígono generadas con el Método del Calibre Giratorio.

Historia

El método fue usado por primera vez por Michael Shamos en 1978 para determinar todos los pares de puntos antipodales de un polígono convexo.^[1] El término rotating caliper fue acuñado en 1983 por el matemático Godfried Toussaint^[2] quien aplicó este enfoque a otros problemas dentro de la geometría computacional. El nombre viene de la analogía entre esta técnica e ir rotando una herramienta de medición cuyo nombre es Calibre de Vernier (conocido como pie de rey dentro de algunos países de habla hispana) alrededor de la parte exterior de un polígono convexo.

Esta técnica la explicaremos a través del problema de determinar todos los todos los pares de puntos antipodales de un polígono convexo.

Definiciones y conceptos

Un par de vértices antipodales y su correspondiente par de rectas paralelas soporte.

Definición 1: Recta soporte de un conjunto de puntos S es aquella que pasa por un punto del conjunto y deja a todo S en uno de los 2 semiplanos que delimita.

Definición 2: Paralelas soporte son 2 rectas de soporte paralelas.

Definición 3: Dos puntos de S se dicen antipodales si por ellos pasan paralelas soporte, es decir, si podemos trazar un par de rectas que pasen cada una por uno de los puntos, sean paralelas entre sí y contengan a todos los puntos de S en el espacio entre ambas rectas.

Algoritmo de cálculo de pares de puntos antipodales

El algoritmo para encontrar los pares de puntos antipodales de un polígono se apoya en tres lemas, cuya demostración puede encontrarse en [^[3]].

Lema 1: Sea ${\displaystyle u_{k-1}u_{k}}$ una arista de un polígono convexo P. Se recorren los vértices de P en el orden contrario al recorrido de las manecillas de un reloj comenzando por el vértice ${\displaystyle u_{k}}$. Sea ${\displaystyle u_{i}}$ el primer vértice más lejano de ${\displaystyle u_{k-1}u_{k}}$ en el recorrido (es decir, la distancia del segmento ${\displaystyle u_{k-1}u_{k}}$ al vértice ${\displaystyle u_{i}}$ es mayor que a los vértices ${\displaystyle u_{i-1}}$ y ${\displaystyle u_{i+1}}$), entonces ningún vértice entre ${\displaystyle u_{k}}$ y ${\displaystyle u_{i}}$ forma un par antipodal con ${\displaystyle u_{k}}$.

Lema 2: Sea ${\displaystyle u_{k-1}u_{k}}$ una arista de un polígono convexo P. Se recorren los vértices de P en el orden contrario al recorrido de las manecillas de un reloj comenzando por el vértice ${\displaystyle u_{k}}$. Sea ${\displaystyle u_{r}}$ el último vértice más lejano de ${\displaystyle u_{k-1}u_{k}}$ en el recorrido, entonces ningún vértice entre ${\displaystyle u_{r}}$ y ${\displaystyle u_{k-1}}$ (en orden contrario al que siguen las manecillas del reloj) forma un par antipodal con ${\displaystyle u_{k-1}}$.

Lema 3: Dado un par de puntos antipodales de un conjunto de puntos S, se cumple que dichos puntos pertenecen a la envolvente convexa del conjunto S.

Es conocido que un punto p está en la envolvente convexa de S si y solo si existe una línea que pasa por p tal que todos los puntos del conjunto S están enteramente contenidos en uno de los dos semiplanos determinados por dicha línea [2]. Usando este resultado se puede inducir que si por un punto pasa una recta soporte de S entonces ese punto pertenece a la envolvente convexa de S, por lo que si dos puntos son antipodales esto significa que a través de ellos pasan rectas soportes de donde se concluye que estos puntos se encuentran en la envolvente convexa de S.

Lo que muestra el lema 3 es que encontrar los pares de puntos antipodales de un conjunto arbitrario de puntos se puede reducir a encontrar los pares de puntos antipodales de la envolvente convexa de S y estaríamos en presencia del problema discutido anteriormente debido a que la envolvente convexa de un conjunto de puntos en el plano es un polígono convexo. Existen varios algoritmos que encuentran la envolvente convexa de un conjunto de puntos eficientemente, quizás el más famoso de ellos sea el algoritmo de Graham scan.

Basándonos en los dos primeros lemas, para hallar todos los pares de puntos antipodales de un polígono convexo seleccionamos una arista ${\displaystyle u_{k-1}}$ ${\displaystyle u_{k}}$ del polígono y comenzamos a recorrer los puntos del mismo en el sentido contrario de las manecillas del reloj comenzando por ${\displaystyle u_{k-1}}$ hasta que alcancemos al primer vértice más lejano de ${\displaystyle u_{k-1}u_{k}}$,al cual llamaremos ${\displaystyle u_{i}}$. Por el lema 2 ${\displaystyle u_{i}}$ es el primer vértice que forma un par antipodal con ${\displaystyle u_{k}}$, luego continuamos moviéndonos hasta alcanzar el último vértice más lejano con respecto a la arista ${\displaystyle u_{k}u_{k+1}}$ el cual está después ${\displaystyle u_{i}}$ en el recorrido que estamos realizando y denotaremos a dicho vértice como ${\displaystyle u_{r}}$.Por el lema 3 ${\displaystyle u_{r}}$ es el último vértice que constituye un par forma un par antipodal con ${\displaystyle u_{k}}$ y todos los vértices visitados entre ${\displaystyle u_{i}}$ y ${\displaystyle u_{r}}$ también forman pares antipodales con ${\displaystyle u_{k}}$. Este proceso lo continuamos repitiendo hasta encontrar todos los pares antipodales y lo interesante es que se puede realizar el recorrido completo con costo temporal de ${\displaystyle O(n)}$ usando dos contadores.

Algoritmo Puntos Antipodales:

Entrada: Un polígono convexo P= {u(1), u(2), u(3),...., u(m)} con los vértices ordenados siguiendo un orden contrario al de las manecillas del reloj. Consideraremos que el vértice u(0) y el vértice u(m) son el mismo vértice.

Salida: Todos los pares de puntos antipodales.

BEGIN:

1- Comenzamos con el lado {u(0)u(1)}. Sea k=1;i=2;

2- WHILE u(i) no es el vértices más lejano del lado {u(k-1)u(k)}:i= i+1 (mod m)

3- WHILE u(i) no es el vértices más lejano del lado {u(k)u(k+1)}:
        OUTPUT[u(k),u(i)] como un par antipodal; i=i+1(mod m+1)

4- IF u(i+1) es también un vértice mas lejano con respecto a la arista u(k+1)u(k):
            OUTPUT[u(k),u(i)];
            OUTPUT[u(k+1),u(i)];
            i=i+1(mod m+1);

5- OUTPUT[u(k),u(i)];

6- IF k<m:k=k+1 mod(m+1);GOTO 3;

END

Note que el punto ${\displaystyle u_{i}}$ tal que área del triángulo ${\displaystyle u_{i}u_{k-1}u_{k}}$ es máxima es precisamente el punto (uno de los puntos) más lejanos con respecto al lado ${\displaystyle u_{k-1}u_{k}}$ debido a que el área de un triángulo que contenga a la arista ${\displaystyle u_{k-1}u_{k}}$ y a otro punto p es igual a ${\displaystyle |u_{k-1}u_{k}|*d(p,u_{k-1}u_{k})}$ donde ${\displaystyle d(p,u_{k-1}u_{k})}$ es igual a la distancia entre el punto ${\displaystyle p}$ y la recta ${\displaystyle u_{k-1}u_{k}}$.

Aplicaciones

El algoritmo puede adaptarse para resolver múltiples problemas geométricos, como por ejemplo

Diámetro de un conjunto de puntos

El diámetro de un conjunto S, de puntos en el plano, es la mayor distancia entre dos puntos de S. Sean u y v dos puntos extremos de un diámetro de S. Notemos que u y v son puntos antipodales ya que si trazamos una recta perpendicular al segmento que une a u con v a través de v todos los puntos de S están de esa recta ya que si hubiese un punto z que estuviese en un semiplano distinto al semiplano donde esta u, la distancia entre z y u fuese mayor que la distancia entre u y v. Lo mismo sucede con la perpendicular a |uv| que pasa por el punto v, por lo que se concluye que los puntos u y v son antipodales ya que a través de ellos pasan dos rectas soportes paralelas(las perpendiculares antes mencionadas). Usando el resultado anterior, si queremos encontrar el diámetro de un conjunto de puntos S iteramos por todos los pares antipodales de la envolvente convexa de S y devolvemos la pareja de puntos con mayor distancia entre los dos puntos del par (o la distancia entre ellos). La envolvente convexa la podemos encontrar con costo temporal de ${\displaystyle O(nlog(n))}$ mientras todos los pares antipodales los podemos encontrar en ${\displaystyle O(n)}$, de esta forma encontraríamos el diámetro de un conjunto de puntos de ${\displaystyle O(nlog(n))}$ lo cual es considerablemente mejor que el algoritmo fuerza bruta que itera por todos los pares de puntos y devuelve los dos puntos más distantes (o la distancia entre los mismos) con costo temporal de ${\displaystyle O(n^{2})}$.

#include <algorithm>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;

typedef pair<double, double> point;

//Check if 3 points are in positive (counter clockwise) orientation
bool ccw(const point &a, const point &b, const point &c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first) > 0;
}

//Build the CCW convex hull of a set of points
vector<point> convexHull(vector<point> p) {
    int n = p.size();
    if (n <= 1)
        return p;
    int k = 0;
    sort(p.begin(), p.end());
    vector<point> q(n * 2);
    for (int i = 0; i < n; q[k++] = p[i++])
        for (; k >= 2 && !ccw(q[k - 2], q[k - 1], p[i]); --k)
            ;
    for (int i = n - 2, t = k; i >= 0; q[k++] = p[i--])
        for (; k > t && !ccw(q[k - 2], q[k - 1], p[i]); --k)
            ;
    q.resize(k - 1 - (q[0] == q[1]));
    return q;
}

//Compute the unsigned double-area of a triangle
double area(const point &a, const point &b, const point &c) {
    return abs((b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first));
}

//Compute the distance between two points
double dist(const point &a, const point &b) {
    return hypot(a.first - b.first, a.second - b.second);
}

//Compute the diameter of a polygon using rotating-caliper method to generate
//all antipodal pairs. Return the max distance between an antipodal pair extremes.
double diameter(const vector<point> &p) {
    //Compute the convex hull of p
    vector<point> h = convexHull(p);
    int m = h.size();

    //Return trivial results for polygons with less than 3 points.
    if (m <= 1)
        return 0;
    if (m == 2)
        return dist(h[0], h[1]);

    //Search the point k which is antipodal of point 0
    int k = 1;
    while (area(h[m - 1], h[0], h[(k + 1) % m]) > area(h[m - 1], h[0], h[k]))
        ++k;

    double res = 0;
    //Generate all antipodal pairs in i,j
    for (int i = 0, j = k; i <= k && j < m; ++i) {
        res = max(res, dist(h[i], h[j]));
        //Advance point j while j is antipodal pair of i
        while (j < m && area(h[i], h[(i + 1) % m], h[(j + 1) % m]) > area(h[i], h[(i + 1) % m], h[j])) {
            res = max(res, dist(h[i], h[(j + 1) % m]));
            ++j;
        }
    }
    return res;
}

int main()
{
    vector<point>p;
    //This is the 11-sides poligon used in:
    //https://commons.wikimedia.org/wiki/File:Rotating_Caliper_Antipodal_Pair.svg
    p.push_back(point(10,210));
    p.push_back(point(110,30));
    p.push_back(point(210,110));
    p.push_back(point(210,10));
    p.push_back(point(390,110));
    p.push_back(point(430,290));
    p.push_back(point(290,250));    
    p.push_back(point(230,430));    
    p.push_back(point(150,310));
    p.push_back(point(190,250));
    p.push_back(point(130,150));

    cout << "Diameter: " << diameter(p) << endl;
        
    return 0;
}

Anchura de un conjunto de puntos

La anchura de un conjunto de puntos en el plano S es la menor distancia entre dos rectas paralelas s1 y s2 tal que el conjunto S este contenido en el espacio comprendido entre las rectas s1 y s2. ^[4] Este problema puede verse como la búsqueda del par de puntos antipodales de la envolvente convexa de S cuya distancia entre sí sea mínima, por lo que se resuelve de manera análoga al problema anterior.

El valor de la anchura de un conjunto de puntos nos permite determinar si el cierre convexo de un polígono es capaz de atravesar un pasillo o una ventana de ancho conocido (siendo una versión simplificada del conocido Problema del sofá), y tiene muchas otras aplicaciones industriales.^[5]

Otras aplicaciones

• Mayor distancia entre dos polígonos convexos^[6][7]
• Menor distancia entre dos polígonos convexos^[8]
• Rectángulo envolvente de menor área (oriented bounding box)
• Rectángulo envolvente de menor perímetro (en:oriented bounding box)
• Onion triangulations
• Spiral triangulations
• Quadrangulations
• Unión de dos polígonos convexos
• Tangentes comunes de dos polígonos convexos
• Intersección de dos polígonos convexos^[9]
• Recta soporte crítica de dos polígonos convexos.

Referencias

1. Shamos, Michael (1978). «Computational Geometry» (PDF). Yale University.
2. "Rotating Calipers" at Toussaint's home page
3. Jianer Chen, Computational Geometry, Methods and Applications, Computer Science Department, Texas A&M University.
4. Michael E. Houle and Godfried T. Toussaint, "Computing the width of a set," IEEE Transactions Pattern Analysis & Machine Intelligence, Vol. 10, no. 5, September 1988, pp. 761–765.
5. Grima, Clara (11 de junio de 2012). «No todo es lo que parece». Mati, una profesora muy particular. Consultado el 2 de noviembre de 2017.
6. Godfried T. Toussaint and Jim A. McAlear, "A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets," Pattern Recognition Letters, Vol. 1, 1982, pp. 21–24.
7. Binay K. Bhattacharya and Godfried T. Toussaint, "Efficient algorithms for computing the maximum distance between two finite planar sets," Journal of Algorithms, vol. 14, 1983, pp. 121– 136.
8. Godfried T. Toussaint and Binay K. Bhattacharya, "Optimal algorithms for computing the minimum distance between two finite planar sets," Pattern Recognition Letters, vol. 2, December, 1983, pp. 79–82.
9. Godfried T. Toussaint, "A simple linear algorithm for intersecting convex polygons, The Visual Computer, Vol. 1, 1985, pp. 118–123.

Véase también

• en:Convex polygon
• en:Convex hull
• en:Smallest enclosing box

• Datos: Q6112703
• Multimedia: Rotating Caliper / Q6112703