Testen, ob ein Polygon schwach einfach ist

Question

Ich bin nicht in der Lage, einen Algorithmus zu finden, um schwach einfache Polygone zu erkennen (d. H. Polygone, bei denen die Seiten sich berühren dürfen, aber nicht überkreuzen). Derzeit suche ich nur nach Kreuzungen zwischen jeder Seite - hier ist die Funktion, die ich für alle nicht angrenzenden Seiten anrufe. Auf diese Weise sind nur einfache Polygone erlaubt (keine Berührung). Polygone sind Vektoren von Punkten.

bool linesIntersect(const point &a1, const point &a2, const point &b1, const point &b2) { 
    // Solve intersection of parametric lines using inverse matrix 
    // The equation of the parametric lines are line1 = (a2 - a1)*s + a1 
    // and line2 = (b2 - b1)*t + b1, where a1, a2, etc. are vectors. 
    // Two equations can be produced from the two components, and these 
    // this system of two equations can be solved for s and t 
    // If the parameters s and t are between 0 and 1, it means that the lines intersect 
    float x21 = a2.x - a1.x, x43 = b2.x - b1.x, x31 = b1.x - a1.x, 
     y21 = a2.y - a1.y, y43 = b2.y - b1.y, y31 = b1.y - a1.y; 
    float determinant = x43*y21 - x21*y43; 
    if(determinant == 0.) return false; 

    float s = float(x43*y31 - x31*y43)/determinant; 
    float t = float(x21*y31 - x31*y21)/determinant; 

    if(s <= 1. && s >= 0. && t <= 1. && t >= 0.) return true; // lines intersect 
    return false; 
} 

s < 1. && s > 0. && t < 1. && t > 0. Mit funktioniert nicht, weil es einige komplexe Polygone so einfach akzeptiert.

Die erste Zahl in this question zeigt ein paar Beispiele. Unten ist ein typisches schwach einfaches Polygon, mit dem sich das Programm befassen würde.

würde ich Pseudo-Code, da die Mathematik Jargon in der oben genannten Frage (1) schreckt mich lieber, und ich glaube nicht, dass ich das Wissen jeden komplexen Algorithmus zu implementieren. Ich verwende Boost.Polygon für etwas anderes, wenn da etwas ist, aber ich habe nichts gefunden.

EDIT:

Hier ist, wie ich die Funktion verwenden. checkPts ist ein vector<point> mit einer angenommenen Seite vom letzten Punkt zum ersten.

// Check for self-intersecting polygons 
for(int i = 0; i < checkPts.size() - 2; ++i) { 
    for(int j = i + 2; j < checkPts.size() - 2; ++j) { 
     if(linesIntersect(checkPts[i], checkPts[i+1], checkPts[j], checkPts[j+1])) error("self-intersecting polygon"); 
    } 
} 

Answer 1

Ich bin mir nicht sicher, ob ich es verstehe, denn Sie scheinen bereits eine Lösung zu haben. Rufen Sie einfach lineIntersects auf jedem Paar nicht benachbarter Kanten. Wenn zwei Kanten keine gemeinsamen Punkte haben, gibt lineIntersects den Wert false zurück, was erwartet wird.

Wenn sich zwei Kanten kreuzen, gibt lineIntersects den Wert true zurück, und Sie wissen, dass das Polygon nicht schwach einfach ist.

Wenn zwei Kanten berühren, wie im Bild, dann ist die Determinante, die Sie in linesIntersects berechnen, 0 (d. H. Die Linien sind parallel). lineIntersects gibt false zurück. Was Sie wollen (Sie können Kanten berühren)

Natürlich gibt es immer den kniffligen Teil, wo Operationen auf Float Rundungsfehler führt, aber für mich ist die Mathematik in Ihrer Funktion richtig. (und sollte definitiv auf dem Beispiel auf dem Bild arbeiten)

Edit: Eine mehr "mathematische" Ansatz. Zwei Kanten haben entweder 0 Punkte gemeinsam, 1 Punkt gemeinsam oder unendlich viele Punkte gemeinsam (sie "berühren"). Einfach schwach zu sein bedeutet, dass Sie für zwei beliebige Kanten nicht den gemeinsamen "1 Punkt" -Fall haben dürfen. Sie benötigen also eine Funktion, die herausfindet, wenn Sie genau 1 Punkt gemeinsam haben. Mein Anspruch ist, dass lineIntersects bereits tut es

Edit 2: Ich habe vergessen zu erklären, dass mit 1 Punkt gemeinsam ist nicht immer ein Problem. Aber nur, wenn der gemeinsame Punkt zwischen den beiden Kanten an einem Endpunkt einer der beiden Kanten liegt. Dann sollten wir es zulassen (false zurückgeben). Aber das ändert meine Antwort nicht, denn in lineIntersects berechnen wir s < 1. && s > 0. && t < 1. && t > 0. und nicht s <= 1. && s >= 0. && t <= 1. && t >= 0.. Wir "erlauben" also schon diesen Fall.