Bezier-Pfad überprüfen, ob er sich schneidet

Question

Ich habe einen Code, der es dem Benutzer ermöglicht, eine Form zu zeichnen. Dafür verwende ich UIBezierPath. Aber ich muss überprüfen, ob die Form sich selbst schneidet, zum Beispiel wie hier: http://upload.wikimedia.org/wikipedia/commons/0/0f/Complex_polygon.svg Dann handelt es sich nicht um eine gültige Form. Wie kann ich das herausfinden?

Bearbeiten: Ich habe das immer noch nicht gelöst. Ich speichere alle Punkte zwischen den Linien im Pfad in einem Array. Dann durchlaufe ich das Array und versuche festzustellen, ob sich Linien kreuzen. Aber das funktioniert nicht, manchmal wird angezeigt, dass es einen Schnittpunkt gibt, obwohl keiner vorhanden ist.

Ich denke, dass das Problem irgendwo in dieser Methode liegt.

-(BOOL)pathIntersects:(double *)x:(double *)y {
int count = pathPoints.count;
CGPoint p1, p2, p3, p4;
for (int a=0; a

`Dies ist der Code, den ich gefunden habe, um festzustellen, ob sich zwei Linien schneiden. Er ist in C, aber er sollte funktionieren.

int LineIntersect(
              double x1, double y1,
              double x2, double y2,
              double x3, double y3,
              double x4, double y4,
              double *x, double *y)
{
double mua,mub;
double denom,numera,numerb;

denom  = (y4-y3) * (x2-x1) - (x4-x3) * (y2-y1);
numera = (x4-x3) * (y1-y3) - (y4-y3) * (x1-x3);
numerb = (x2-x1) * (y1-y3) - (y2-y1) * (x1-x3);

/* Sind die Linien koinzident? */
if (ABS(numera) < 0.00001 && ABS(numerb) < 0.00001 && ABS(denom) < 0.00001) {
    *x = (x1 + x2) / 2;
    *y = (y1 + y2) / 2;
    return(TRUE);
}

/* Sind die Linien parallel */
if (ABS(denom) < 0.00001) {
    *x = 0;
    *y = 0;
    return(FALSE);
}

/* Liegt der Schnittpunkt entlang der Segmente */
mua = numera / denom;
mub = numerb / denom;
if (mua < 0 || mua > 1 || mub < 0 || mub > 1) {
    *x = 0;
    *y = 0;
    return(FALSE);
}
*x = x1 + mua * (x2 - x1);
*y = y1 + mua * (y2 - y1);
return(TRUE);
}`

Answer 1

Es kommt darauf an, wie komplex das Polygon ist, das vom Benutzer gezeichnet wird, und wie viele Punkte es hat. Idealerweise sollte es einen Punkt für alle Eckpunkte der Form geben und nicht mehr. Holen Sie sich einen CGPath aus dem UIBezierPath und verwenden Sie GCPathApply, um die Elemente an eine Funktion zu übergeben, die jeden Punkt zu einem Array hinzufügt. Durchlaufen Sie das Array mit zwei for-Schleifen, eine ineinander verschachtelt, die jede Linienstrecke gegen jede Linienstrecke danach überprüft, indem sie einen Standard-Linien-Linien-Schnitttest verwendet. Sobald ein Schnittpunkt gefunden wurde, brechen Sie die Schleife ab. Oder, wenn dies eine Bequemlichkeitsmethode wäre, geben Sie BOOL zurück. Das ist der einfachste Weg.

BEARBEITEN: Hier ist ein Beispiel für eine Funktion zur Überprüfung von Linienkreuzungen, die BOOL zurückgibt und Ihnen mitteilt, ob zwei Segmente sich kreuzen. Geben Sie die beiden Punkte ein, die das erste Segment erstellen, gefolgt von den beiden Punkten, die das zweite Segment bilden. Sie wurde schnell aus einem Stück Quellcode, den ich im Internet gefunden habe, bearbeitet, aber sie funktioniert.

CGPoint lineSegmentsIntersect(CGPoint L1P1, CGPoint L1P2, CGPoint L2P1, CGPoint L2P2) 
{ 
    float x1 = L1P1.x, x2 = L1P2.x, x3 = L2P1.x, x4 = L2P2.x;
    float y1 = L1P1.y, y2 = L1P2.y, y3 = L2P1.y, y4 = L2P2.y;

    float bx = x2 - x1; 
    float by = y2 - y1; 
    float dx = x4 - x3; 
    float dy = y4 - y3;

    float b_dot_d_perp = bx * dy - by * dx;

    if(b_dot_d_perp == 0) {
        return NO;
    }

    float cx = x3 - x1;
    float cy = y3 - y1;
    float t = (cx * dy - cy * dx) / b_dot_d_perp;

    if(t < 0 || t > 1) {
        return NO;
    }

    float u = (cx * by - cy * bx) / b_dot_d_perp;

    if(u < 0 || u > 1) { 
        return NO;
    }

    return YES;
}

Sie können es so verwenden.

if (lineSegmentsIntersect(lineOnePointOne,lineOnePointTwo,lineTwoPointOne,lineTwoPointTwo)){
     //Segment überschneidet
} else {
     //Segment überschneiden sich nicht
}

Es liegt an Ihnen, die doppelte Schleife zu erstellen, um die richtigen Segmente gegeneinander zu prüfen.