Dados dos polígonos convexos, necesitamos encontrar las tangentes inferior y superior de estos polígonos.
Como se muestra en la figura a continuación, 
y 
muestra la tangente superior e inferior respectivamente.
Ejemplos:
Input : First Polygon : {(2, 2), (3, 3), (5, 2), (4, 0), (3, 1)}
Second Polygon : {(-1, 0), (0, 1), (1, 0), (0, -2)}.
Output : Upper Tangent - line joining (0,1) and (3,3)
Lower Tangent - line joining (0,-2) and (4,0)
Descripción general:
tengamos dos polígonos convexos como se muestra,
Para encontrar la tangente superior, comenzamos tomando dos puntos. El punto más a la derecha de a y el punto más a la izquierda de b. La línea que los une se etiqueta como 1. Como esta línea pasa a través del polígono b (no está sobre el polígono b), entonces tomamos el siguiente punto en b en sentido contrario a las agujas del reloj, la línea se etiqueta como 2. Ahora la línea está sobre el polígono b , ¡multa! Pero la línea cruza el polígono a, así que nos movemos al siguiente punto en el sentido de las agujas del reloj, etiquetado como 3 en la imagen. Esto nuevamente cruza el polígono a, así que pasamos a la línea 4. Esta línea cruza b, así que pasamos a la línea 5. Ahora esta línea no cruza ninguno de los puntos. Entonces esta es la tangente superior para los polígonos dados.
Para encontrar la tangente inferior, necesitamos movernos inversamente a través de los polígonos, es decir, si la línea cruza el polígono b, nos movemos en el sentido de las agujas del reloj y luego en el sentido contrario a las agujas del reloj si la línea cruza el polígono a.
Algoritmo para la tangente superior:
L <- line joining the rightmost point of a
and leftmost point of b.
while (L crosses any of the polygons)
{
while(L crosses b)
L <- L' : the point on b moves up.
while(L crosses a)
L <- L' : the point on a moves up.
}
Algoritmo para la tangente inferior:
L <- line joining the rightmost point of a
and leftmost point of b.
while (L crosses any of the polygons)
{
while (L crosses b)
L <- L' : the point on b moves down.
while (L crosses a)
L <- L' : the point on a moves down.
}
Ejemplo :
CPP
// C++ program to find upper tangent of two polygons.
#include<bits/stdc++.h>
using namespace std;
// stores the center of polygon (It is made
// global because it is used in compare function)
pair<int,int> mid;
// determines the quadrant of a point
// (used in compare())
int quad(pair<int,int> p)
{
if (p.first >= 0 && p.second >= 0)
return 1;
if (p.first <= 0 && p.second >= 0)
return 2;
if (p.first <= 0 && p.second <= 0)
return 3;
return 4;
}
// Checks whether the line is crossing the polygon
int orientation(pair<int,int> a, pair<int,int> b,
pair<int,int> c)
{
int res = (b.second-a.second)*(c.first-b.first) -
(c.second-b.second)*(b.first-a.first);
if (res == 0)
return 0;
if (res > 0)
return 1;
return -1;
}
// compare function for sorting
bool compare(pair<int,int> p1, pair<int,int> q1)
{
pair<int,int> p = make_pair(p1.first - mid.first,
p1.second - mid.second);
pair<int,int> q = make_pair(q1.first - mid.first,
q1.second - mid.second);
int one = quad(p);
int two = quad(q);
if (one != two)
return (one < two);
return (p.second*q.first < q.second*p.first);
}
// Finds upper tangent of two polygons 'a' and 'b'
// represented as two vectors.
void findUpperTangent(vector<pair<int,int> > a,
vector<pair<int,int> > b)
{
// n1 -> number of points in polygon a
// n2 -> number of points in polygon b
int n1 = a.size(), n2 = b.size();
// To find a point inside the convex polygon(centroid),
// we sum up all the coordinates and then divide by
// n(number of points). But this would be a floating-point
// value. So to get rid of this we multiply points
// initially with n1 and then find the centre and
// then divided it by n1 again.
// Similarly we do divide and multiply for n2 (i.e.,
// elements of b)
// maxa and minb are used to check if polygon a
// is left of b.
int maxa = INT_MIN;
for (int i=0; i<n1; i++)
{
maxa = max(maxa, a[i].first);
mid.first += a[i].first;
mid.second += a[i].second;
a[i].first *= n1;
a[i].second *= n1;
}
// sorting the points in counter clockwise order
// for polygon a
sort(a.begin(), a.end(), compare);
for (int i=0; i<n1; i++)
{
a[i].first /= n1;
a[i].second /= n1;
}
mid = {0, 0};
int minb = INT_MAX;
for (int i=0; i<n2; i++)
{
mid.first += b[i].first;
mid.second += b[i].second;
minb = min(minb, b[i].first);
b[i].first *= n2;
b[i].second *= n2;
}
// sorting the points in counter clockwise
// order for polygon b
sort(b.begin(), b.end(), compare);
for (int i=0; i<n2; i++)
{
b[i].first/=n2;
b[i].second/=n2;
}
// If a is to the right of b, swap a and b
// This makes sure a is left of b.
if (minb < maxa)
{
a.swap(b);
n1 = a.size();
n2 = b.size();
}
// ia -> rightmost point of a
int ia = 0, ib = 0;
for (int i=1; i<n1; i++)
if (a[i].first > a[ia].first)
ia = i;
// ib -> leftmost point of b
for (int i=1; i<n2; i++)
if (b[i].first < b[ib].first)
ib=i;
// finding the upper tangent
int inda = ia, indb = ib;
bool done = 0;
while (!done)
{
done = 1;
while (orientation(b[indb], a[inda], a[(inda+1)%n1]) > 0)
inda = (inda + 1) % n1;
while (orientation(a[inda], b[indb], b[(n2+indb-1)%n2]) < 0)
{
indb = (n2+indb-1)%n2;
done = 0;
}
}
cout << "upper tangent (" << a[inda].first << ","
<< a[inda].second << ") (" << b[indb].first
<< "," << b[indb].second << ")\n";
}
// Driver code
int main()
{
vector<pair<int,int> > a;
a.push_back({2, 2});
a.push_back({3, 1});
a.push_back({3, 3});
a.push_back({5, 2});
a.push_back({4, 0});
vector<pair<int,int> > b;
b.push_back({0, 1});
b.push_back({1, 0});
b.push_back({0, -2});
b.push_back({-1, 0});
findUpperTangent(a, b);
return 0;
}
Producción:
Upper tangent (0,1) (3,3)
Complejidad de tiempo: O(n1 log (n1) + n2 log(n2))
Espacio auxiliar: O(1)
Tenga en cuenta que el código anterior solo encuentra la tangente superior. De manera similar podemos encontrar la tangente inferior.
Este artículo es una contribución de Aarti_Rathi y Amritya Vagmi y le gustaría contribuir, también puede escribir un artículo usando write.geeksforgeeks.org o enviar su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA