交差線の領域を取得する（CGPoints）

Question

CGPointの配列がありますが、シェイプを構成する点を探したいと思います。添付の画像をご覧ください：

赤い丸は、私が持っているポイントをマークしています。

疑問符の付いた領域は、どのようにして見つけることができますか？

ありがとうございました。

Answer 1

私は解決策を考え出しました。

この関数は、交差する線で閉じる領域ごとにポリゴンを返します。

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

最初の線分から始まり、交差点を確認する必要があります。明らかに最初の2つの線分が交差する場合、それらは同じ線であり、あなたの形状は単なる線であるので、その場合は無視してください。ラインセグメントを一度続けていくと、交差するセグメントペアが見つかると、あなたはあなたのシェイプを持っています。

線分1を線分2で確認してから、線分2を線分1、次に線分1を確認します。次に3を4、2を、1をチェックします。セグメント7は線分3と交差し、線分3の最初の点を削除し、見つかった交点に移動します。次に線分7の最後の点を削除し、見つかった交点に設定します。そこにあなたの形があります。

ここでは、2つの線分（C＃で書かれていますが、直線的な数値なので、好きな言語に変換するのは非常に簡単です）を見つける方法の例です。 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); 
}