獲取相交線的區域（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.然後檢查線段3對線段2，然後檢查線段1.然後檢查4對3，然後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); 
}