获取相交线的区域（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); 
}