So ermitteln Sie den Typ des Polygons

Question

Der Benutzer gibt n-te Punkte ein. Ich muss prüfen, ob ein Polygon existiert und dann den Typ bestimmen - konkaves oder konvexes Polygon. Ich weiß, dass ein Polygon konvex ist, wenn jeder Winkel unter 180 Grad ist. Das Problem besteht also darin, jede innere Ecke des Polygons zu finden. Ich habe nach der Formel oder dem Algorithmus gesucht, aber ohne Erfolg.

Beispiel:

Input: n = 4;

Punkt1: (5; 6)

Point2: (4; -5)

Point3: (-5, 4)

Point4: (-5, 5)

Erwartete Ausgabe: Polygon konvex

Dies ist der Code so weit: Ri Jetzt findet es nur den maximalen und minimalen Abstand zwischen den Punkten in der Ebene.

#include "stdafx.h" 
#include <iostream> 
using namespace std; 

int main() 
{ 
    double a[15][2]; 
    int n; 
    cin >> n; 
    if (n <= 0 && n > 15) 
     return 1; 

    for (int i = 0; i < n; i++) 
    { 
     cout << "x" << i << " = , y" << i << " = "; 
     cin >> a[i][0] >> a[i][1]; 
    } 

    double maxDistance = 0.0; 
    double minDistance = 0.0; 
    double maxpoint1[2]; 
    double maxpoint2[2]; 
    double minpoint1[2]; 
    double minpoint2[2]; 

    for (int i = 0; i < n; i++) 
    { 
     for (int j = 0; j < n; j++) 
     { 
      if (j != i) 
      { 
       double x1 = a[i][0]; 
       double x2 = a[j][0]; 
       double y1 = a[i][1]; 
       double y2 = a[j][1]; 
       double currentDistance = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)); 

       if (currentDistance > maxDistance) 
       { 
        maxDistance = currentDistance; 
        maxpoint1[0] = x1; 
        maxpoint1[1] = y1; 
        maxpoint2[0] = x2; 
        maxpoint2[1] = y2; 

       } 

       if (minDistance > currentDistance) 
       { 
        currentDistance = minDistance; 
        minpoint1[0] = x1; 
        minpoint1[1] = y1; 
        minpoint2[0] = x2; 
        minpoint2[1] = y2; 
       } 

       cout << "x1 = " << x1 << " y1 = " << y1 << " x2 = " << x2 << " y2 = " << y2; 
       cout << endl << "Distance is " << currentDistance; 
       cout << endl; 
      } 
     } 
    } 

    cout << "The max distance is: " << maxDistance << " between x1 = " << maxpoint1[0] << " y1 = " << maxpoint1[1] << " and x2 = " << maxpoint2[0] << " y2 = " << maxpoint2[1]; 
    cout << "The min distance is: " << minDistance << " between x1 = " << minpoint1[0] << " y1 = " << minpoint1[1] << " and x2 = " << minpoint2[0] << " y2 = " << minpoint2[1]; 


    return 0; 
} 

Answer 1

zu finden, wenn Polygon konvex oder konkav ist, nur Zeichen der Kreuzprodukte CrossProduct(P[0], P[1], P[2]) etc für alle sequentiellen Punkttripel überprüfen. Als Beispiel

CrossProductSign(A, B, C) = 
       SignOf((B.X - A.X) * (C.Y - B.Y) - (B.Y - A.Y) * (C.X - B.X)) 

Für konvexe müssen alle Kreuzprodukte das gleiche Vorzeichen (+ oder -) haben.

Wie es funktioniert: für konvexe Polygon macht jedes Triplet auf der gleichen Seite (oder CW, oder CCW je nach Laufrichtung) drehen. Für konkav sind einige Zeichen unterschiedlich (wo der innere Winkel 180 Grad überschreitet). Beachten Sie, dass Sie keine Winkelwerte berechnen müssen.

Answer 2

Wenn Sie Winkel zwischen zwei Seiten zu finden, verwenden Sie Kreuz oder Skalarprodukt von Vektoren.

ein Punkt b = | a || b | cos (angle_between_vectors) = a [0] * B [0] + a [1] * B [1] + a [2] * B [2]

würden innere Winkel (pi - angle_between_vectors)

Oh, übrigens, Polygon kann sich selbst schneiden, das ist auch in vielen Anwendungsfällen schädlich. Ihre Definition würde dies nicht erkennen. Komplexes Viereck hätte alle Winkel von weniger als 90 Grad.

Das ist nicht die einzige Möglichkeit zu bestimmen, ob das Polygon konvex und wahrscheinlich eines der kalkreichsten ist. Das Problem mit dem Skalarprodukt ist, dass sein Vorzeichen anzeigen würde, wenn der Winkel kleiner oder größer als Pi/2 ist. Die richtige Methode zum Bestimmen, ob Ihr Polygon nicht komplex oder nicht-konvex ist, besteht darin, zu überprüfen, ob sich die Richtung der Drehung ändert. Dafür würden Sie Kreuzprodukt benötigen. Für 2D-Vektoren hat das Ergebnis ihres Kreuzprodukts nur eine Z-Komponente (senkrecht zur Ebene), sein Vorzeichen bestimmt, in welcher Richtung die Rotation stattfand.

Die Frage war hier schon.

How do determine if a polygon is complex/convex/nonconvex?