Detect if drawing a path is a circle/rectangle in xcode

Question

I want to implement a auto complete feature for a drawing app. Once a free hand object is drawn, I want to detect the type of object (circle/rectangle/triangle) and based on the result would want to plot a corresponding object.

I have read up a bit about OpenCV but then I would need to convert the user drawing into an image at real time. I am recording the number of points plotted/traced by the touch and also generate a UIBeizerPath of the corresponding path. How do I go about to detecting the shape type?

Ron Regev · Answer 1 · 2021-08-20T23:10:13.863

Perhaps a simpler solution, at least for perfect shapes: assuming you know the shape you are looking for, you can create the path of that shape within the bounds of your user's UIBezierPath, and then perform a hit test against a stroked version of that path.

For instance, here's a Swift 5 method that detects if a path resembles an oval. I also threw in a method I adapted from another post here to extract all the elements of a UIBezierPath, except a subpath's closure:

extension UIBezierPath {
    /// Indicates whether a manually drawn UIBézierPath resembles an oval.
    func resemblesOval() -> Bool {
        // Get all the path points
        let pathPoints = self.getPathElements().map({$0.point})
        // Create the path of the perfect oval of the same bounds to perform a hit test against
        let perfectOvalPath = UIBezierPath(ovalIn: self.bounds)
        // Choose a hit test ribbon that is a quarter of the average of the bounds' width and height
        let hitWidth = (self.bounds.width + self.bounds.height)/2 * 0.25
        // Stroke the path of the desired perfect oval to create hit test criteria
        let hitPath = perfectOvalPath.cgPath.copy(strokingWithWidth: hitWidth,
                                                     lineCap: .round,
                                                     lineJoin: .miter,
                                                     miterLimit: 0)
        // Create an array to collect points that succeed in the hit test
        var validPathPoints = [CGPoint]()
        // Hit test for each point of our tested path
        for point in pathPoints {
            guard point != nil else { continue }
            if hitPath.contains(point!) {
                validPathPoints.append(point!)
            }
        }
        // If 90% or more were successful, then it is an oval
        if 10 * validPathPoints.count >= 9 * pathPoints.count {
            return true
        }
        return false
    }

    /// An enum containing possible UIBezierPath element types. Use in conjunction with the `getPathElements` method.
    enum PathElementType {
        case move
        case addLine
        case addQuadCurve
        case addCurve
    }
    
    /// Extracts all of the path elements, their points and their control points. Expected returned types belong to the enum `PathElementType`.
    func getPathElements() -> [(type: PathElementType?, point: CGPoint?, controlPoint: CGPoint?, controlPoint1: CGPoint?, controlPoint2: CGPoint?)] {
    
        let initialPath = UIBezierPath(cgPath: self.cgPath)
        var bezierPoints = NSMutableArray()
        initialPath.cgPath.apply(info: &bezierPoints, function: { info, element in

            guard let resultingPoints = info?.assumingMemoryBound(to: NSMutableArray.self) else {
                return
            }

            let points = element.pointee.points
            let type = element.pointee.type

            switch type {
            case .moveToPoint:
                resultingPoints.pointee.add([NSNumber(value: Float(points[0].x)), NSNumber(value: Float(points[0].y))])
                resultingPoints.pointee.add(NSString("move"))

            case .addLineToPoint:
                resultingPoints.pointee.add([NSNumber(value: Float(points[0].x)), NSNumber(value: Float(points[0].y))])
                resultingPoints.pointee.add(NSString("addLine"))

            case .addQuadCurveToPoint:
                resultingPoints.pointee.add([NSNumber(value: Float(points[0].x)), NSNumber(value: Float(points[0].y))])
                resultingPoints.pointee.add([NSNumber(value: Float(points[1].x)), NSNumber(value: Float(points[1].y))])
                resultingPoints.pointee.add(NSString("addQuadCurve"))

            case .addCurveToPoint:
                resultingPoints.pointee.add([NSNumber(value: Float(points[0].x)), NSNumber(value: Float(points[0].y))])
                resultingPoints.pointee.add([NSNumber(value: Float(points[1].x)), NSNumber(value: Float(points[1].y))])
                resultingPoints.pointee.add([NSNumber(value: Float(points[2].x)), NSNumber(value: Float(points[2].y))])
                resultingPoints.pointee.add(NSString("addCurve"))

            case .closeSubpath:
                break
            @unknown default:
                break
            }
        })
        let elementsTypes : [String] = bezierPoints.compactMap { $0 as? String }
        let elementsCGFloats : [[CGFloat]] = bezierPoints.compactMap { $0 as? [CGFloat] }
        var elementsCGPoints : [CGPoint] = elementsCGFloats.map { CGPoint(x: $0[0], y: $0[1]) }
    
        var returnValue : [(type: PathElementType?, point: CGPoint?, controlPoint: CGPoint?, controlPoint1: CGPoint?, controlPoint2: CGPoint?)] = []
        for i in 0..<elementsTypes.count {
            switch elementsTypes[i] {
            case "move":
                returnValue.append((type: .move, point: elementsCGPoints.removeFirst(), controlPoint: nil, controlPoint1: nil, controlPoint2: nil))
            case "addLine":
                returnValue.append((type: .addLine, point: elementsCGPoints.removeFirst(), controlPoint: nil, controlPoint1: nil, controlPoint2: nil))
            case "addQuadCurve":
                let controlPoint = elementsCGPoints.removeFirst()
                returnValue.append((type: .addQuadCurve, point: elementsCGPoints.removeFirst(), controlPoint: controlPoint, controlPoint1: nil, controlPoint2: nil))
            case "addCurve":
                let controlPoint1 = elementsCGPoints.removeFirst()
                let controlPoint2 = elementsCGPoints.removeFirst()
                returnValue.append((type: .addCurve, point: elementsCGPoints.removeFirst(), controlPoint: nil, controlPoint1: controlPoint1, controlPoint2: controlPoint2))
            default:
                returnValue.append((type: nil, point: nil, controlPoint: nil, controlPoint1: nil, controlPoint2: nil))
            }
        }
        return returnValue
    }
}

fang · Accepted Answer · 2014-12-24T00:54:53.533

1

You need to segment the data points first. Google on "stroke segmentation" to find related articles. One simple and fast algorithm is to compute the forward slope and backward slope for each data point, then compute the turning angle between forward slope and backward slope. If the turning angle is greater than a certain angle threshold, then you can assume that your path takes a sharp turn there. From the number of sharp turns computed, you can infer whether the points represent a triangle (with 2 sharp turns), a quadrilateral (with 3 sharp turns) or something else. To infer that the data points represent a circle or a rectangle, you will need to do additional computation. For example, if there is no sharp turns at all, do a circle fitting to the data points to see if the maximum error to the fitted circle is smaller than a certain tolerance. To output a rectangle, you will have to fit straight lines to each segment of data points and check if the fitted lines are more or less orthogonal to each other.

edited Dec 24 '14 at 00:54

answered Dec 24 '14 at 00:49

fang

3,473
1
13
19

Interesting! I followed your approach but unfortunately the sequence of points that I get have minor offsets (ie- they are not in straight line) and hence applying the formula gives me many sharp turns. For a triangle I got 70 sharp turns, I then reduced the sample size but still was getting around 18 sharp turns. – B K Dec 26 '14 at 05:00
When computing backward/forward slopes, use several points before and after the current point. For example, when computing the backward/forward slope for point P(i), use point P(i-m) and P(i+m). Choose the value of m depending on the point density. This way, you should be able to avoid sharp turns caused by minor data noises. – fang Dec 26 '14 at 07:58
Yes, after posting the comment I figured I should reduce my sampling size and did that. Now I seem to get correct values though for triangle I keep getting 3 turns instead of 2 and rects I sometimes get 2 turns. The turning angle threshold needs more work I guess. – B K Dec 27 '14 at 04:47
Typically I used 60 degree as the angle threshold. Please note that the turnning angle is 180 - angle(P(i-m),P(i),P(i+m)). So, for a stroke that looks like an equilateral triangle, you should get two sharp turns and each sharp turn is about 120 degree, not 60 degree. – fang Dec 27 '14 at 08:25
I have optimised your approach to have a somewhat working algorithm though it nowhere close to being perfect. So I will accept this answer as the right one. – B K Jan 26 '15 at 22:36

score 0 · Answer 3 · edited May 23 '17 at 12:34

0

You can iterate through UIBezierPath points with CGPathApply(..) method. Look here for example.

But you should determine shape type somehow - it's mathematical task and approach depends on your input data.

edited May 23 '17 at 12:34

Community

1
1

answered Dec 23 '14 at 15:22

brigadir

6,874
6
46
81

1

I think its hidden somewhere in my question but I already have the points for the path. I am looking at the math on how to detect shapes. – B K Dec 26 '14 at 04:58

Detect if drawing a path is a circle/rectangle in xcode

3 Answers3

Linked

Related