I'm trying to detect if a line drawn by the user intersects itself. I'm using a line intersection detection algorithm that goes through each waypoint of the line and checks if intersects with any other point in the line.
This is a costly method and has started to produce performance problems. What would be the recommended algorithm for this problem? Is there a code example of it?
The line is represented with wayPoints which are coordinates that have been gathered by users movement on screen.
Thanks a lot for just reading this far! All help Appreciated!
for i in 1 ..<(wayPoints.count-1) {
for j in 0 ..< i-1 {
if let intersection = intersectionBetweenSegments(wayPoints[i], wayPoints[i+1], wayPoints[j], wayPoints[j+1]){
...}
}
}
func intersectionBetweenSegments(p0: CGPoint, _ p1: CGPoint, _ p2: CGPoint, _ p3: CGPoint) -> CGPoint? {
var denominator = (p3.y - p2.y) * (p1.x - p0.x) - (p3.x - p2.x) * (p1.y - p0.y)
var ua = (p3.x - p2.x) * (p0.y - p2.y) - (p3.y - p2.y) * (p0.x - p2.x)
var ub = (p1.x - p0.x) * (p0.y - p2.y) - (p1.y - p0.y) * (p0.x - p2.x)
if (denominator < 0) {
ua = -ua; ub = -ub; denominator = -denominator
}
if ua >= 0.0 && ua <= denominator && ub >= 0.0 && ub <= denominator && denominator != 0 {
return CGPoint(x: p0.x + ua / denominator * (p1.x - p0.x), y: p0.y + ua / denominator * (p1.y - p0.y))
}
return nil
}
