gasparuff gasparuff - 3 months ago 15
iOS Question

Get area of intersecting line (CGPoints)

I have an Array of CGPoints and I would like to find those points, which build a shape. Please see the attached image:
enter image description here

The red circles just mark the points I have.

How can the area with the question mark be found?

Thanks.

Answer

I've figured out the solution.

This function returns a polygon for each area that gets closed by intersecting lines.

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
}