Get Bereich der Schnittlinie (CGPoints)

Question

Ich habe ein Array von CGPoints und ich möchte diese Punkte finden, die eine Form bilden. Bitte beachten Sie das beigefügte Bild:

Die roten Kreise markieren nur die Punkte, die ich habe.

Wie kann der Bereich mit dem Fragezeichen gefunden werden?

Danke.

Answer 1

Ich habe die Lösung herausgefunden.

Diese Funktion gibt ein Polygon für jeden Bereich zurück, der durch sich kreuzende Linien geschlossen wird.

func intersectionOfLineFrom(p1: CGPoint, to p2: CGPoint, withLineFrom p3: CGPoint, to p4: CGPoint) -> NSValue? { 
    let d: CGFloat = (p2.x - p1.x) * (p4.y - p3.y) - (p2.y - p1.y) * (p4.x - p3.x) 
    if d == 0 { 
     return nil 
    } 
    // parallel lines 
    let u: CGFloat = ((p3.x - p1.x) * (p4.y - p3.y) - (p3.y - p1.y) * (p4.x - p3.x))/d 
    let v: CGFloat = ((p3.x - p1.x) * (p2.y - p1.y) - (p3.y - p1.y) * (p2.x - p1.x))/d 
    if u < 0.0 || u > 1.0 { 
     return nil 
    } 
    // intersection point not between p1 and p2 
    if v < 0.0 || v > 1.0 { 
     return nil 
    } 
    // intersection point not between p3 and p4 
    var intersection: CGPoint = CGPointZero 
    intersection.x = p1.x + u * (p2.x - p1.x) 
    intersection.y = p1.y + u * (p2.y - p1.y) 

    return NSValue(CGPoint: intersection) 
} 


func intersectedPolygons(points: [CGPoint]) -> [[CGPoint]] { 
    var removeIndexBelow : Int = 0 
    var removeIndexAbove : Int = 0 

    var resultArrays : [[CGPoint]] = [[CGPoint]]() 

    for i in 1..<points.count { 
     let firstLineStart = points[i-1] as CGPoint 
     let firstLineEnd = points[i] as CGPoint 
     for var j = points.count-1; j > i+1; j-- { 
      let lastLineStart = points[j-1] as CGPoint 
      let lastLineEnd = points[j] as CGPoint 
      if let intersect: NSValue = self.intersectionOfLineFrom(firstLineStart, to: firstLineEnd, withLineFrom: lastLineStart, to: lastLineEnd){ 
       var pointsCopy = points 
       let intersection = intersect.CGPointValue() 
       pointsCopy[i-1] = intersection 
       pointsCopy[j] = intersection 
       removeIndexBelow = i 
       removeIndexAbove = j 
       let fullPoly = Array(pointsCopy[removeIndexBelow-1..<removeIndexAbove]) 
       resultArrays.append(fullPoly) 
       break; 
      } 
     } 
    } 

    return resultArrays 
} 

Answer 2

Sie müssen mit Ihrem ersten Liniensegment beginnen und nach Kreuzungen suchen. Offensichtlich, wenn die ersten zwei Liniensegmente sich schneiden, dann sind sie die selbe Linie und Ihre Form ist nur eine Linie, also ignorieren Sie diesen Fall. Wenn Sie mit den Liniensegmenten fortfahren, nachdem Sie ein Segmentpaar gefunden haben, das sich überschneidet, haben Sie Ihre Form.

Überprüfen Sie Liniensegment 2 gegen Liniensegment 1. Dann überprüfen Sie Liniensegment 3 gegen Liniensegment 2, dann gegen Liniensegment 1. Dann überprüfen Sie 4 gegen 3, dann 2, dann 1, etc ... Wenn Sie diese Linie finden Segment 7 schneidet das Liniensegment 3, löscht den ersten Punkt des Liniensegments 3 und schneidet es an den gefundenen Schnittpunkt. Löschen Sie dann den letzten Punkt von Liniensegment 7 und setzen Sie ihn auf den gefundenen Schnittpunkt. Da hast du deine Form.

Hier ist eine Beispielmethode, um den Schnittpunkt von 2 Liniensegmenten zu finden (in C# geschrieben, aber es ist gerade Mathematik, so dass es sehr einfach sein sollte, in jede Sprache zu konvertieren, die Sie möchten). Taken from here:

// Determines if the lines AB and CD intersect. 
static bool LinesIntersect(PointF A, PointF B, PointF C, PointF D) 
{ 
    PointF CmP = new PointF(C.X - A.X, C.Y - A.Y); 
    PointF r = new PointF(B.X - A.X, B.Y - A.Y); 
    PointF s = new PointF(D.X - C.X, D.Y - C.Y); 

    float CmPxr = CmP.X * r.Y - CmP.Y * r.X; 
    float CmPxs = CmP.X * s.Y - CmP.Y * s.X; 
    float rxs = r.X * s.Y - r.Y * s.X; 

    if (CmPxr == 0f) 
    { 
     // Lines are collinear, and so intersect if they have any overlap 

     return ((C.X - A.X < 0f) != (C.X - B.X < 0f)) 
      || ((C.Y - A.Y < 0f) != (C.Y - B.Y < 0f)); 
    } 

    if (rxs == 0f) 
     return false; // Lines are parallel. 

    float rxsr = 1f/rxs; 
    float t = CmPxs * rxsr; 
    float u = CmPxr * rxsr; 

    return (t >= 0f) && (t <= 1f) && (u >= 0f) && (u <= 1f); 
}