Performant way to determine if paths are intersecting

Question

I have an app where the user can draw numbers, I'm currently trying to differentiate between digits. My idea was to group overlapping lines by checking if they intersect. Currently it takes all the points and draws a SwiftUI Path.

The problem is that the paths contain a lot of points. The arm of the 4 contains 49 points, the stalk of the 4 has 30, and the 2 has 82 points. This makes comparing all the line segments for an intersection very expensive.

I have two questions:

• Are there any swift functions to reduce the number of points while retaining the overall shape?
• Are there any good methods for quickly determining whether complex paths intersect?

Answer 1

For curve simplification, start with Ramer–Douglas–Peucker. For this problem, that might get you most of the way there all by itself.

Next, consider the bounding boxes of the curves. For a Path, this is the boundingRect property. If two bounding boxes do not overlap, then the paths cannot intersect. If all your curves are composed of straight lines, this boundingRect should work well. If you also use quad or cubic curves, you may want to investigate path.cgPath.boundingBoxOfPath, which will be a tighter box (it doesn't include the control points).

I expect those approaches will be the best way, but another approach is to draw the paths and then look for the intersections. For example, you can create a small context and draw one curve in red and another in blue with a .screen blend mode. Then scan for any purple. (You can easily make this work for three curves simultaneously. With some linear algebra, it may be possible to scale to more simultaneous curves.)

This approach is an approximation, and its accuracy can be tuned by changing the size of the context. I expect an approximation is going to be fine (and even preferable) for your problem.

Here is a slapped together implementation just to show how it can work. I haven't given any thought to making this clean; the point is just the technique:

let width = 64
let height = 64
let context = CGContext(data: nil,
                        width: width,
                        height: height,
                        bitsPerComponent: 8,
                        bytesPerRow: width * 4,
                        space: CGColorSpaceCreateDeviceRGB(),
                        bitmapInfo: CGImageAlphaInfo.noneSkipFirst.rawValue)!
context.setShouldAntialias(false)
context.setBlendMode(.screen)

let path1 = UIBezierPath(rect: CGRect(x: 10, y: 20, width: 50, height: 8))
context.addPath(path1.cgPath)
context.setFillColor(UIColor.blue.cgColor)
context.drawPath(using: .fill)

let path2 = UIBezierPath(rect: CGRect(x: 40, y: 0, width: 8, height: 50))
context.addPath(path2.cgPath)
context.setFillColor(UIColor.red.cgColor)
context.drawPath(using: .fill)

let data = context.data!.bindMemory(to: UInt8.self, capacity: width * height * 4)
for i in stride(from: 0, to: width * height * 4, by: 4) {
    if data[i + 1] == 255 && data[i + 3] == 255 {
        print("Found overlap!")
        break
    }
}

I've turned off anti-aliasing here for consistency (and speed). With anti-aliasing, you may get partial colors. On the other hand, turning on anti-aliasing and adjusting what range of colors you treat as "overlap" may lead to more accurate results.