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?

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
    }

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
    }

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?

Thanks a lot for just reading this far! All help Appreciated!

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?

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
    }