gasparuff - 1 year ago 81

iOS Question

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

The red circles just mark the points I have.

How can the area with the question mark be found?

Thanks.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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
}
```