Berechnen Sie den maximalen Abstand zwischen zwei Punkten auf der Koordinatenebene mit der Methode des rotierenden Messschiebers

In C++ haben wir eine vordefinierte Funktion sqrt, die die Quadratwurzel einer beliebigen Zahl zurückgibt. Die Methode des rotierenden Messschiebers ist eine Technik zur Lösung von Algorithmen oder zur Berechnung der Geometrie.

Visuelle Darstellung der Methode mit rotierendem Messschieber

Handrotation zeigt ein reales Beispiel eines Diagramms mit rotierendem Messschieber und zeigt die vertikale Ausrichtung, wann immer die Hand gedreht wird. Wir können dieses Konzept auch durch die Verwendung von Polygonen verstehen.

In diesem Artikel verwenden wir die Methode des rotierenden Messschiebers, um den maximalen Abstand zwischen zwei Koordinatenpunkten zu ermitteln. 跨度>

Grammatik

Die folgende Syntax wird im Programm verwendet -

vector<datatype> name

Parameter

• Vektoren – Wir beginnen mit Schlüsselwortvektoren und initialisieren Vektoren in C++.

• Datentyp – Der Typ des durch den Vektor dargestellten Datenelements.

• Name – Der Name des Vektors.

Algorithmus

• Wir werden die Header-Dateien iostream, vector und cmath verwenden, um das Programm zu starten.

• Wir erstellen Strukturnamenspunkte, die die Koordinaten von x und y speichern.

• Wir definieren eine Funktionsdefinition vom doppelten Datentyp distance(), um den Abstand zwischen zwei Koordinatenpunkten zu berechnen. Hier sind Punkte p1 und Punkt p2 Parameter, die Koordinatenwerte akzeptieren und Entfernungen mithilfe der vordefinierten Funktion sqrt und der Entfernungsformel zurückgeben.

• Wir definieren eine Funktionsdefinition namens CP(), deren doppelter Datentyp die Parameter Punkt p1, Punkt p2 und Punkt p3 b> akzeptiert, um den Kreuzproduktvektor zu berechnen, d. h. p2-p1 und p3-p1 bzgl. x- und y-Koordinaten.

• Jetzt erstellen wir eine Funktionsdefinition vom doppelten Datentyp rotatingCaliper(), die das Argument als Punktvektor verwendet und den Abstand zwischen zwei beliebigen Koordinatenebenen maximiert.

• Wir initialisieren das variable Ergebnis auf 0, das verfolgt wird, um die Berechnung der maximalen Entfernung zu erfüllen. Um die Größe des Punkts zu ermitteln, wird eine vordefinierte Funktion namens size() verwendet und in der Variablen n gespeichert.

• Wir initialisieren die beiden Variablen j und k auf 1 und führen Folgendes aus -

• Wir bewegen j zum nächsten Punkt im Polygon und dem Kreuzprodukt CP i+1] % n' der aktuellen Kante 'points[i], points[ und der nächsten Kante 'points [ j]' ist kleiner als das Kreuzprodukt CP der aktuellen Kante 'points[i]', points[ (i + 1) % n]' und dem nächsten Punkt ' nach Punkt [(j + 1) % n]' Kante. Dadurch wird überprüft, ob die aktuelle Kante senkrecht zur nächsten Kante verläuft.

• Wir bewegen uns k zum nächsten Punkt im Polygon, bis der Abstand zwischen dem aktuellen Punkt 'point[i]' und dem nächsten Punkt ' point[k]' kleiner ist als der aktuelle Punkt 'point [ Der Abstand ' zwischen i]' und dem Punkt nach dem nächsten Punkt 'points[(k+1)%n]. Dadurch wird überprüft, ob der nächste Punkt am weitesten vom aktuellen Punkt entfernt ist.

• Jetzt berechnen wir den Abstand zwischen dem Punkt j, k, und dem aktuellen Punkt 'point[i]', multiplizieren alle diese Punkte und erhalten dann den Maximalwert in der Variablen result.

• Wir starten die Hauptfunktion und wenden den Wert der Koordinatenebene auf die Variable "Vektor Punkt" an.

• Schließlich rufen wir den Funktionsnamen rotatingCaliper() auf und übergeben den Wert 'points' als Parameter, um den maximalen Abstand des rotierenden Bremssatteldiagramms zu erhalten.

Beispiel

In diesem Programm verwenden wir die Methode des rotierenden Messschiebers, um den maximalen Abstand zwischen zwei Punkten in der Koordinatenebene zu ermitteln.

#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;
}

Ausgabe

Maximum distance between two coordinate points: 39.0512

Fazit

Wir verstehen das Konzept der rotierenden Messschiebermethode, indem wir den maximalen Abstand zwischen zwei Koordinatenpunkten berechnen. Zu den praktischen Anwendungen dieser Methode gehören die Optimierung des Öffnungswinkels, die Klassifizierung durch maschinelles Lernen usw.

Das obige ist der detaillierte Inhalt vonBerechnen Sie den maximalen Abstand zwischen zwei Punkten auf der Koordinatenebene mit der Methode des rotierenden Messschiebers. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!