Calculez la distance maximale entre deux points sur le plan de coordonnées à l'aide de la méthode du pied à coulisse rotatif

En C++, nous avons une fonction prédéfinie sqrt qui renvoie la racine carrée de n'importe quel nombre. La méthode du pied à coulisse rotatif est une technique utilisée dans la résolution d'algorithmes ou de géométrie computationnelle.

Représentation visuelle de la méthode du pied à coulisse rotatif

La rotation de la main montre un exemple réel de tracé d'un pied à coulisse rotatif, montrant l'orientation verticale chaque fois que la main est tournée. Nous pouvons également comprendre ce concept en utilisant des polygones.

Dans cet article, nous utiliserons la méthode du pied à coulisse rotatif pour trouver la distance maximale entre deux points de coordonnées. 跨度>

Grammaire

La syntaxe suivante est utilisée dans le programme -

vector<datatype> name

Paramètres

• Vecteurs - Nous commençons par des vecteurs de mots-clés et initialisons les vecteurs en C++.

• datatype - Le type d'élément de données représenté par le vecteur.

• name - Le nom du vecteur.

Algorithme

• Nous utiliserons les fichiers d'en-tête iostream, vector et cmath pour démarrer le programme.

• Nous créons des points de nom de structure qui stockeront les coordonnées de x et y.

• Nous définissons une définition de fonction de type de données double distance() pour calculer la distance entre deux points de coordonnées. Ici, Points p1 et Point p2 sont des paramètres qui acceptent les valeurs de coordonnées et renvoient la distance à l'aide de la fonction prédéfinie sqrt et de la formule de distance.

• Nous définissons une définition de fonction appelée CP() dont le type de données double accepte les paramètres Point p1, Point p2 et Point p3 pour calculer le vecteur de produit vectoriel, c'est-à-dire p2-p1 et p3-p1 par rapport aux coordonnées x et y.

• Nous créons maintenant une définition de fonction de type de données double rotatingCaliper() qui prend l'argument comme vecteur ponctuel et maximise la distance entre deux plans de coordonnées.

• Nous initialisons le résultat variable à 0, qui suivra pour satisfaire le calcul de la distance maximale. Pour trouver la taille du point, il utilisera une fonction prédéfinie appelée size() et la stockera dans la variable n.

• On initialise les deux variables j et k à 1 et on fait ce qui suit -

• Nous nous déplaçons j vers le point suivant du polygone et le produit vectoriel CP i+1] % n' de l'arête actuelle 'points[i], points[ et l'arête suivante 'points [ j]' est inférieur au produit vectoriel CP de l'arête actuelle 'points[i]', points[ (i + 1) % n]' et le point suivant ' après le point [(j + 1) %n]' bord. Cela vérifiera que le bord actuel est perpendiculaire au bord suivant.

• Nous déplaçons k vers le point suivant du polygone jusqu'à ce que la distance entre le point actuel 'point[i]' et le point suivant 'point[k]' soit plus petite que le point actuel 'point [ La distance ' entre i]' et le point après le point suivant 'points[(k+1)%n]. Cela vérifiera que le point suivant est le plus éloigné du point actuel.

• Maintenant, nous calculons la distance entre le point j, k, et le point actuel 'point[i]', en multipliant tous ces points et nous obtiendrons ensuite la valeur maximale dans la variable result.

• Nous démarrons la fonction principale et appliquons la valeur du plan de coordonnées à la variable "vecteur point".

• Enfin, nous appelons le nom de la fonction rotatingCaliper() et passons la valeur 'points' comme paramètre pour obtenir la distance maximale du tracé du pied à coulisse rotatif.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct Point {
    double x, y;
};
// In this function we are calculating the distance between two coordinate point.
double distance(Point p1, Point p2) {
   return sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
}
// In this function we are calculating the cross-product of two vector
double CP(Point p1, Point p2, Point p3) // CP: cross-product {
   return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
// In this function we are calculating the Rotating Caliper
double rotatingCalipers(vector<Point> points) {
   double result = 0;
  int n = points.size();
    int j = 1, k = 1;
   for (int i = 0; i < n; i++) {
       while (CP(points[i], points[(i + 1) % n], points[j]) < CP(points[i], points[(i + 1) % n], points[(j + 1) % n])) 
       {
           j = (j + 1) % n;
       }
       while (distance(points[i], points[k]) < distance(points[i], points[(k + 1) % n])) {
          k = (k + 1) % n;
       }
     // calculate the max distance
        result = max(result, distance(points[i], points[j]) * distance(points[i], points[k]));
   }
   return result;
}
int main() {
    vector<Point> points = {{0, 0}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4, 4}, {4, 5}, {5, 5},{5,6}};
    cout << "Maximum distance between two coordinate points: "<<rotatingCalipers(points) << endl;
    return 0;
}

Maximum distance between two coordinate points: 39.0512