Draw a perfect circle from user's touch

Question

I have this practice project that allows the user to draw on the screen as they touch with their fingers. Very simple App I did as an exercise way back. My little cousin took the liberty of drawing things with his finger with my iPad on this App (Kids drawings: circle, lines, etc, whatever came to his mind). Then he started to draw circles and then he asked me to make it a "good circle" (from my understanding: make the drawn circle perfectly round, as we know no matter how stable we try to draw something with our finger on the screen, a circle is never really as rounded as a circle should be).

So my question here is that, is there any way in code where we can first detect a line drawn by the user that forms a circle and generate approximately the same size of the circle by making it perfectly round on the screen. Making a not so straight line straight is something I would know how to do, but as for circle, I don't quite know how to go about doing it with Quartz or other methods.

My reasoning is that, the start and the end point of the line must touch or cross each other after the user lifts his finger to justify the fact that he was trying to actually draw a circle.

Goldenseal

It can be hard to tell the difference between a circle and a polygon in this scenario. How about having a "Circle Tool" where the user clicks to define the center, or one corner of a bounding rectangle, and drags to change the radius or set the opposite corner? – Farl

@user1118321: This defeats the concept of just being able to draw a circle and have a perfect circle. Ideally, the app should recognize from the user's drawing alone whether the user drew a circle (more or less), an ellipse, or a polygon. (Plus, polygons might not be in scope for this app—it might just be circles or lines.) – Augusto

So, to which answer do you think I should give the bounty? I see many good candidates. – Augusto

@Unheilig: I don't have any expertise in the subject, beyond a nascent understanding of trig. That said, the answers that show the most potential to me are https://mcmap.net/q/135343/-draw-a-perfect-circle-from-user-39-s-touch, https://mcmap.net/q/135343/-draw-a-perfect-circle-from-user-39-s-touch, https://mcmap.net/q/135343/-draw-a-perfect-circle-from-user-39-s-touch, maybe https://mcmap.net/q/135343/-draw-a-perfect-circle-from-user-39-s-touch, and my own. Those are the ones I'd try first. I leave the order to you. – Augusto

Please try Googling for "Skechpad" by Ivan Sutherland! This problem was-solved in 1963! – Roomy

@Gene: Perhaps you could summarize the relevant information, and link to more details, in an answer. – Augusto

Answer 1

Sometimes it is really useful to spend some time reinventing the wheel. As you might have already noticed there are a lot of frameworks, but it is not that hard to implement a simple, but yet useful solution without introducing all that complexity. (Please don't get me wrong, for any serious purpose it is better to use some mature and proven to be stable framework).

I will present my results first and then explain the simple and straightforward idea behind them.

You'll see in my implementation there is no need to analyze every single point and do complex computations. The idea is to spot some valuable meta information. I will use tangent as an example:

Let's identify a simple and straightforward pattern, typical for the selected shape:

So it is not that hard to implement a circle detection mechanism based on that idea. See working demo below (Sorry, I'm using Java as the fastest way to provide this fast and a bit dirty example):

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.HeadlessException;
import java.awt.Point;
import java.awt.RenderingHints;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JFrame;
import javax.swing.SwingUtilities;

public class CircleGestureDemo extends JFrame implements MouseListener, MouseMotionListener {

    enum Type {
        RIGHT_DOWN,
        LEFT_DOWN,
        LEFT_UP,
        RIGHT_UP,
        UNDEFINED
    }

    private static final Type[] circleShape = {
        Type.RIGHT_DOWN,
        Type.LEFT_DOWN,
        Type.LEFT_UP,
        Type.RIGHT_UP};

    private boolean editing = false;
    private Point[] bounds;
    private Point last = new Point(0, 0);
    private List<Point> points = new ArrayList<>();

    public CircleGestureDemo() throws HeadlessException {
        super("Detect Circle");

        addMouseListener(this);
        addMouseMotionListener(this);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        setPreferredSize(new Dimension(800, 600));
        pack();
    }

    @Override
    public void paint(Graphics graphics) {
        Dimension d = getSize();
        Graphics2D g = (Graphics2D) graphics;

        super.paint(g);

        RenderingHints qualityHints = new RenderingHints(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        qualityHints.put(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
        g.setRenderingHints(qualityHints);

        g.setColor(Color.RED);
        if (cD == 0) {
            Point b = null;
            for (Point e : points) {
                if (null != b) {
                    g.drawLine(b.x, b.y, e.x, e.y);
                }
                b = e;
            }
        }else if (cD > 0){
            g.setColor(Color.BLUE);
            g.setStroke(new BasicStroke(3));
            g.drawOval(cX, cY, cD, cD);
        }else{
            g.drawString("Uknown",30,50);
        }
    }


    private Type getType(int dx, int dy) {
        Type result = Type.UNDEFINED;

        if (dx > 0 && dy < 0) {
            result = Type.RIGHT_DOWN;
        } else if (dx < 0 && dy < 0) {
            result = Type.LEFT_DOWN;
        } else if (dx < 0 && dy > 0) {
            result = Type.LEFT_UP;
        } else if (dx > 0 && dy > 0) {
            result = Type.RIGHT_UP;
        }

        return result;
    }

    private boolean isCircle(List<Point> points) {
        boolean result = false;
        Type[] shape = circleShape;
        Type[] detected = new Type[shape.length];
        bounds = new Point[shape.length];

        final int STEP = 5;

        int index = 0;        
        Point current = points.get(0);
        Type type = null;

        for (int i = STEP; i < points.size(); i += STEP) {
            Point next = points.get(i);
            int dx = next.x - current.x;
            int dy = -(next.y - current.y);

            if(dx == 0 || dy == 0) {
                continue;
            }

            Type newType = getType(dx, dy);
            if(type == null || type != newType) {
                if(newType != shape[index]) {
                    break;
                }
                bounds[index] = current;
                detected[index++] = newType;
            }
            type = newType;            
            current = next;

            if (index >= shape.length) {
                result = true;
                break;
            }
        }

        return result;
    }

    @Override
    public void mousePressed(MouseEvent e) {
        cD = 0;
        points.clear();
        editing = true;
    }

    private int cX;
    private int cY;
    private int cD;

    @Override
    public void mouseReleased(MouseEvent e) {
        editing = false;
        if(points.size() > 0) {
            if(isCircle(points)) {
                cX = bounds[0].x + Math.abs((bounds[2].x - bounds[0].x)/2);
                cY = bounds[0].y;
                cD = bounds[2].y - bounds[0].y;
                cX = cX - cD/2;

                System.out.println("circle");
            }else{
                cD = -1;
                System.out.println("unknown");
            }
            repaint();
        }
    }

    @Override
    public void mouseDragged(MouseEvent e) {
        Point newPoint = e.getPoint();
        if (editing && !last.equals(newPoint)) {
            points.add(newPoint);
            last = newPoint;
            repaint();
        }
    }

    @Override
    public void mouseMoved(MouseEvent e) {
    }

    @Override
    public void mouseEntered(MouseEvent e) {
    }

    @Override
    public void mouseExited(MouseEvent e) {
    }

    @Override
    public void mouseClicked(MouseEvent e) {
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {

            @Override
            public void run() {
                CircleGestureDemo t = new CircleGestureDemo();
                t.setVisible(true);
            }
        });
    }
}

It should not be a problem to implement similar behavior on iOS, since you just need several events and coordinates. Something like the following (see example):

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
    UITouch* touch = [[event allTouches] anyObject];
}

- (void)handleTouch:(UIEvent *)event {
    UITouch* touch = [[event allTouches] anyObject];
    CGPoint location = [touch locationInView:self];

}

- (void)touchesMoved:(NSSet *)touches withEvent:(UIEvent *)event {
    [self handleTouch: event];
}

- (void)touchesEnded:(NSSet *)touches withEvent:(UIEvent *)event {
    [self handleTouch: event];    
}

There are several enhancements possible.

Start at any point

Current requirement is to start drawing a circle from the top middle point due to the following simplification:

        if(type == null || type != newType) {
            if(newType != shape[index]) {
                break;
            }
            bounds[index] = current;
            detected[index++] = newType;
        }

Please notice the default value of index is used. A simple search through the available "parts" of the shape will remove that limitation. Please note you'll need to use a circular buffer in order to detect a full shape:

Clockwise and counterclockwise

In order to support both modes you will need to use the circular buffer from the previous enhancement and search in both directions:

Draw an ellipse

You have everything you need already in the bounds array.

Simply use that data:

cWidth = bounds[2].y - bounds[0].y;
cHeight = bounds[3].y - bounds[1].y;

Other gestures (optional)

Finally, you just need to properly handle a situation when dx (or dy) is equal to zero in order to support other gestures:

Update

This small PoC got quite a high attention, so I did update the code a bit in order to make it work smoothly and provide some drawing hints, highlight supporting points, etc:

Here is the code:

import java.awt.BasicStroke;
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.HeadlessException;
import java.awt.Point;
import java.awt.RenderingHints;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class CircleGestureDemo extends JFrame {

    enum Type {

        RIGHT_DOWN,
        LEFT_DOWN,
        LEFT_UP,
        RIGHT_UP,
        UNDEFINED
    }

    private static final Type[] circleShape = {
        Type.RIGHT_DOWN,
        Type.LEFT_DOWN,
        Type.LEFT_UP,
        Type.RIGHT_UP};

    public CircleGestureDemo() throws HeadlessException {
        super("Circle gesture");
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setLayout(new BorderLayout());
        add(BorderLayout.CENTER, new GesturePanel());
        setPreferredSize(new Dimension(800, 600));
        pack();
    }

    public static class GesturePanel extends JPanel implements MouseListener, MouseMotionListener {

        private boolean editing = false;
        private Point[] bounds;
        private Point last = new Point(0, 0);
        private final List<Point> points = new ArrayList<>();

        public GesturePanel() {
            super(true);
            addMouseListener(this);
            addMouseMotionListener(this);
        }

        @Override
        public void paint(Graphics graphics) {
            super.paint(graphics);

            Dimension d = getSize();
            Graphics2D g = (Graphics2D) graphics;

            RenderingHints qualityHints = new RenderingHints(RenderingHints.KEY_ANTIALIASING,
                    RenderingHints.VALUE_ANTIALIAS_ON);
            qualityHints.put(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);

            g.setRenderingHints(qualityHints);

            if (!points.isEmpty() && cD == 0) {
                isCircle(points, g);
                g.setColor(HINT_COLOR);
                if (bounds[2] != null) {
                    int r = (bounds[2].y - bounds[0].y) / 2;
                    g.setStroke(new BasicStroke(r / 3 + 1));
                    g.drawOval(bounds[0].x - r, bounds[0].y, 2 * r, 2 * r);
                } else if (bounds[1] != null) {
                    int r = bounds[1].x - bounds[0].x;
                    g.setStroke(new BasicStroke(r / 3 + 1));
                    g.drawOval(bounds[0].x - r, bounds[0].y, 2 * r, 2 * r);
                }
            }

            g.setStroke(new BasicStroke(2));
            g.setColor(Color.RED);

            if (cD == 0) {
                Point b = null;
                for (Point e : points) {
                    if (null != b) {
                        g.drawLine(b.x, b.y, e.x, e.y);
                    }
                    b = e;
                }

            } else if (cD > 0) {
                g.setColor(Color.BLUE);
                g.setStroke(new BasicStroke(3));
                g.drawOval(cX, cY, cD, cD);
            } else {
                g.drawString("Uknown", 30, 50);
            }
        }

        private Type getType(int dx, int dy) {
            Type result = Type.UNDEFINED;

            if (dx > 0 && dy < 0) {
                result = Type.RIGHT_DOWN;
            } else if (dx < 0 && dy < 0) {
                result = Type.LEFT_DOWN;
            } else if (dx < 0 && dy > 0) {
                result = Type.LEFT_UP;
            } else if (dx > 0 && dy > 0) {
                result = Type.RIGHT_UP;
            }

            return result;
        }

        private boolean isCircle(List<Point> points, Graphics2D g) {
            boolean result = false;
            Type[] shape = circleShape;
            bounds = new Point[shape.length];

            final int STEP = 5;
            int index = 0;
            int initial = 0;
            Point current = points.get(0);
            Type type = null;

            for (int i = STEP; i < points.size(); i += STEP) {
                final Point next = points.get(i);
                final int dx = next.x - current.x;
                final int dy = -(next.y - current.y);

                if (dx == 0 || dy == 0) {
                    continue;
                }

                final int marker = 8;
                if (null != g) {
                    g.setColor(Color.BLACK);
                    g.setStroke(new BasicStroke(2));
                    g.drawOval(current.x - marker/2, 
                               current.y - marker/2, 
                               marker, marker);
                }

                Type newType = getType(dx, dy);
                if (type == null || type != newType) {
                    if (newType != shape[index]) {
                        break;
                    }
                    bounds[index++] = current;
                }

                type = newType;
                current = next;
                initial = i;

                if (index >= shape.length) {
                    result = true;
                    break;
                }
            }
            return result;
        }

        @Override
        public void mousePressed(MouseEvent e) {
            cD = 0;
            points.clear();
            editing = true;
        }

        private int cX;
        private int cY;
        private int cD;

        @Override
        public void mouseReleased(MouseEvent e) {
            editing = false;
            if (points.size() > 0) {
                if (isCircle(points, null)) {
                    int r = Math.abs((bounds[2].y - bounds[0].y) / 2);
                    cX = bounds[0].x - r;
                    cY = bounds[0].y;
                    cD = 2 * r;
                } else {
                    cD = -1;
                }
                repaint();
            }
        }

        @Override
        public void mouseDragged(MouseEvent e) {
            Point newPoint = e.getPoint();
            if (editing && !last.equals(newPoint)) {
                points.add(newPoint);
                last = newPoint;
                repaint();
            }
        }

        @Override
        public void mouseMoved(MouseEvent e) {
        }

        @Override
        public void mouseEntered(MouseEvent e) {
        }

        @Override
        public void mouseExited(MouseEvent e) {
        }

        @Override
        public void mouseClicked(MouseEvent e) {
        }
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {

            @Override
            public void run() {
                CircleGestureDemo t = new CircleGestureDemo();
                t.setVisible(true);
            }
        });
    }

    final static Color HINT_COLOR = new Color(0x55888888, true);
}

Subastral

Spectacular answer Renat. Clear description of the approach, images that document the process, animations too. Also seems the most generalized, robust solution. Tangents sound like a really clever idea - much like initial (current?) handwriting recognition techniques. Question bookmarked for the sake of this answer. :) – Interdependent

One thing I'd add is that, in Cocoa Touch, the state-machine nature of UIGestureRecognizers makes that a perfect place to implement this. You'd have a recognizer for every shape, even (I imagine) separate recognizers for clockwise and counterclockwise. The nature of gesture recognizers is to rule themselves out as the gesture progresses, so, by the end of it, you should be left with zero or one recognizers standing—and if it's one, that's the shape the user just drew, and the controller then just needs to ask it where and how big. (Caveat: I have never implemented a custom gesture recognizer.) – Augusto

More generally: A concise, understandable explanation AND diagrams AND an animated demo AND code AND variations? This is an ideal Stack Overflow answer. – Augusto

This is such a good answer, I can almost forgive he is doing computer graphics in Java! ;) – Pietje

Will there be anymore surprising updates (i.e., more shapes, etc) for this Christmas, Santa Renat? :-) – Goldenseal

Wow. Tour de force. – Bolivia

Answer 2

A classic Computer Vision technique for detecting a shape is the Hough Transform. One of the nice things about the Hough Transform is that it is very tolerant of partial data, imperfect data and noise. Using Hough for a circle: http://en.wikipedia.org/wiki/Hough_transform#Circle_detection_process

Given that your circle is hand drawn I think the Hough transform may be a good match for you.

Here's a "simplified" explanation, I apologize for it not really being that simple. Much of it is from a school project that I did many years ago.

The Hough Transform is a voting scheme. A two dimensional array of integers is allocated and all elements are set to zero. Each element corresponds to a single pixel in the image being analyzed. This array is referred to as the accumulator array since each element will accumulate information, votes, indicating the possibility that a pixel may be at the origin of a circle or arc.

A gradient operator edge detector is applied to the image and edge pixels, or edgels, are recorded. An edgel is a pixel that has a different intensity or color with respect to it’s neighbors. The degree of difference is called the gradient magnitude. For each edgel of sufficient magnitude a voting scheme is applied that will increment elements of the accumulator array. The elements being incremented (voted for) correspond to the possible origins of circles that pass through the edgel under consideration. The desired outcome is that if an arc exists then the true origin will receive more votes than the false origins.

Note that elements of the accumulator array being visited for voting form a circle around the edgel under consideration. Calculating the x,y coordinates to vote for is the same as calculating the x,y coordinates of a circle that you are drawing.

In your hand drawn image you may be able to use the set (colored) pixels directly rather than calculate edgels.

Now with imperfectly located pixels you won't necessarily get a single accumulator array element with the greatest number of votes. You may get a collection of neighboring array elements with a bunch of votes, a cluster. The center of gravity of this cluster may offer a good approximation for the origin.

Note that you may have to run the Hough Transform for different values of radius R. The one that produces the denser cluster of votes is the "better" fit.

There are various techniques to use to reduce votes for false origins. For example one advantage of using edgels is that they not only have a magnitude but they have a direction as well. When voting we need only vote for possible origins in the appropriate direction. The locations receiving votes would form an arc rather than a complete circle.

Here's an example. We start with a circle of radius one and an initialized accumulator array. As each pixel is considered potential origins are voted for. The true origin receives the most votes which in this case is four.

.  empty pixel
X  drawn pixel
*  drawn pixel currently being considered

. . . . .   0 0 0 0 0
. . X . .   0 0 0 0 0
. X . X .   0 0 0 0 0
. . X . .   0 0 0 0 0
. . . . .   0 0 0 0 0

. . . . .   0 0 0 0 0
. . X . .   0 1 0 0 0
. * . X .   1 0 1 0 0
. . X . .   0 1 0 0 0
. . . . .   0 0 0 0 0

. . . . .   0 0 0 0 0
. . X . .   0 1 0 0 0
. X . X .   1 0 2 0 0
. . * . .   0 2 0 1 0
. . . . .   0 0 1 0 0

. . . . .   0 0 0 0 0
. . X . .   0 1 0 1 0
. X . * .   1 0 3 0 1
. . X . .   0 2 0 2 0
. . . . .   0 0 1 0 0

. . . . .   0 0 1 0 0
. . * . .   0 2 0 2 0
. X . X .   1 0 4 0 1
. . X . .   0 2 0 2 0
. . . . .   0 0 1 0 0

Scarabaeid

Answer 3

Here is another way. Using UIView touchesBegan, touchesMoved, touchesEnded and adding points to an array. You divide the array into halves, and test whether every point in one array is roughly the same diameter from its counterpart in the other array as all of the other pairs.

    NSMutableArray * pointStack;

    - (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
    {
        // Detect touch anywhere
    UITouch *touch = [touches anyObject];


    pointStack = [[NSMutableArray alloc]init];

    CGPoint touchDownPoint = [touch locationInView:touch.view];


    [pointStack addObject:touchDownPoint];

    }


    /**
     * 
     */
    - (void)touchesMoved:(NSSet *)touches withEvent:(UIEvent *)event
    {

            UITouch* touch = [touches anyObject];
            CGPoint touchDownPoint = [touch locationInView:touch.view];

            [pointStack addObject:touchDownPoint];  

    }

    /**
     * So now you have an array of lots of points
     * All you have to do is find what should be the diameter
     * Then compare opposite points to see if the reach a similar diameter
     */
    - (void)touchesEnded:(NSSet *)touches withEvent:(UIEvent *)event
    {
            uint pointCount = [pointStack count];

    //assume the circle was drawn a constant rate and the half way point will serve to calculate or diameter
    CGPoint startPoint = [pointStack objectAtIndex:0];
    CGPoint halfWayPoint = [pointStack objectAtIndex:floor(pointCount/2)];

    float dx = startPoint.x - halfWayPoint.x;
    float dy = startPoint.y - halfWayPoint.y;


    float diameter = sqrt((dx*dx) + (dy*dy));

    bool isCircle = YES;// try to prove false!

    uint indexStep=10; // jump every 10 points, reduce to be more granular

    // okay now compare matches
    // e.g. compare indexes against their opposites and see if they have the same diameter
    //
      for (uint i=indexStep;i<floor(pointCount/2);i+=indexStep)
      {

      CGPoint testPointA = [pointStack objectAtIndex:i];
      CGPoint testPointB = [pointStack objectAtIndex:floor(pointCount/2)+i];

      dx = testPointA.x - testPointB.x;
      dy = testPointA.y - testPointB.y;


      float testDiameter = sqrt((dx*dx) + (dy*dy));

      if(testDiameter>=(diameter-10) && testDiameter<=(diameter+10)) // +/- 10 ( or whatever degree of variance you want )
      {
      //all good
      }
      else
      {
      isCircle=NO;
      }

    }//end for loop

    NSLog(@"iCircle=%i",isCircle);

}

That sound okay? :)

Consociate

Answer 4

I'm no shape recognition expert, but here's how I might approach the problem.

First, while displaying the user's path as freehand, secretly accumulate a list of point (x, y) samples along with times. You can get both facts from your drag events, wrap them into a simple model object, and pile those up in a mutable array.

You probably want to take the samples fairly frequently—say, every 0.1 seconds. Another possibility would be to start out really frequent, maybe every 0.05 seconds, and watch how long the user drags; if they drag longer than some amount of time, then lower the sample frequency (and drop any samples that would've been missed) to something like 0.2 seconds.

(And don't take my numbers for gospel, because I just pulled them out of my hat. Experiment and find better values.)

Second, analyze the samples.

You'll want to derive two facts. First, the center of the shape, which (IIRC) should just be the average of all of the points. Second, the average radius of each sample from that center.

If, as @user1118321 guessed, you want to support polygons, then the rest of the analysis consists of making that decision: whether the user wants to draw a circle or a polygon. You can look at the samples as a polygon to start with to make that determination.

There are several criteria you can use:

• Time: If the user hovers for longer at some points than others (which, if samples are at a constant interval, will appear as a cluster of consecutive samples near each other in space), those may be corners. You should make your corner threshold small so that the user can do this unconsciously, rather than having to deliberately pause at each corner.
• Angle: A circle will have roughly the same angle from one sample to the next all the way around. A polygon will have several angles joined by straight line segments; the angles are the corners. For a regular polygon (the circle to an irregular polygon's ellipse), the corner angles should all be roughly the same; an irregular polygon will have different corner angles.
• Interval: A regular polygon's corners will be equal space apart within the angular dimension, and the radius will be constant. An irregular polygon will have irregular angular intervals and/or a non-constant radius.

The third and final step is to create the shape, centered upon the previously-determined center point, with the previously-determined radius.

No guarantees that anything I've said above will work or be efficient, but I hope it at least gets you on the right track—and please, if anyone who knows more about shape recognition than me (which is a very low bar) sees this, feel free to post a comment or your own answer.

Augusto

+1 Hi, thanks for the input. Very informative. Likewise, I wish that the iOS/"shape recognition" superman will somehow see this post and enlighten us further. – Goldenseal

Your algorithm sounds good. I would add a check on how far the user's path diverged from a perfect circle/polygon. (For example, percent mean square deviation.) If it's too large, the user might not want the ideal shape. For a skilled doodler, the cutoff would be smaller than for a sloppy doodler. Having this would allow the program to give artistic freedom to artists but lots of help to beginners. – Potation

@user2654818: How would you measure that? – Augusto

@PeterHosey: Explanation for circles: Once you have the ideal circle, you've got the center and the radius. So you take every drawn point, and calculate its square distance from the center, which is ( (x-x0)^2 + (y-y0)^2 ). Subtract that from the radius squared. (I am avoiding lots of square roots to save computation.) Call that the squared error for a drawn point. Average the squared error for all drawn points, then square root it, then divide it by the radius. That's your average percent divergence. (The math/statistics is probably cringe-worthy, but it would work in practice.) – Potation

Answer 5

Once you determine the user finished drawing their shape where they started, you can take a sample of the coordinates that they drew through and try fitting them to a circle.

There is a MATLAB solution to this problem here: http://www.mathworks.com.au/matlabcentral/fileexchange/15060-fitcircle-m

Which is based on the paper Least-Squares Fitting of Circles and Ellipses by Walter Gander, Gene H. Golub and Rolf Strebel: http://www.emis.de/journals/BBMS/Bulletin/sup962/gander.pdf

Dr Ian Coope from the University of Canterbury, NZ published a paper with the abstract:

The problem of determining the circle of best fit to a set of points in the plane (or the obvious generalization to n-dimensions) is easily formulated as a nonlinear total least-squares problem which may be solved using a Gauss-Newton minimization algorithm. This straight-forward approach is shown to be inefficient and extremely sensitive to the presence of outliers. An alternative formulation allows the problem to be reduced to a linear least squares problem which is trivially solved. The recommended approach is shown to have the added advantage of being much less sensitive to outliers than the nonlinear least squares approach.

http://link.springer.com/article/10.1007%2FBF00939613

The MATLAB file can compute both the nonlinear TLS and linear LLS problem.

Fikes

Answer 6

I've had pretty good luck with a properly trained $1 recognizer (http://depts.washington.edu/aimgroup/proj/dollar/). I used it for circles, lines, triangles and squares.

It was a long ago, before UIGestureRecognizer, but I think it should be easy-ish to create proper UIGestureRecognizer subclasses.

Forrestforrester

Answer 7

Here's a fairly simple way using:

- (UIView *)hitTest:(CGPoint)point withEvent:(UIEvent *)event

assuming this matrix grid:

 A B C D E F G H
1      X X
2    X     X 
3  X         X
4  X         X
5    X     X
6      X X
7
8

Place some UIViews on the"X" locations and test them for becoming hit ( in sequence ) . If they all get hit in sequence I think it might be fair to let the user say "Well done you drew a circle"

Sounds okay? ( and simple )

Consociate

Hi, Lemon. Good reasoning, but in the scenario above, it means that we would need to have 64 UIViews to detect the touches, right? And how would you define the size for one single UIView if the canvas is the size of an iPad for example? It seems that if the circle is small and if the size of a single UIView is larger, in this case we could not check the sequence because all drawn points would lie within one single UIView. – Goldenseal

Yep - this one probably only works if you fix the canvas to something like 300x300 and then have an "example" canvas next to it with the size of circle you are looking for the user to draw. If so I would go with 50x50 squares * 6 , you also only need to render the Views you are interested in hitting in the correct locations, not all 6*6 ( 36 ) or 8*8 (64) – Consociate

@Unheilig: That's what this solution does. Anything circular enough to pass through a correct sequence of views (and you could potentially allow some maximum number of detours for extra slop) will match as a circle. You then snap it to a perfect circle centered at the center of all of those views, whose radius reaches all (or at least most) of them. – Augusto

@PeterHosey Ok, let me try to get my head around this. I would appreciate if any of you could provide some code to get this rolling. Meanwhile, I will also try to get my head round this and afterward I will do the same with the coding part. Thanks. – Goldenseal

Just submitted another way for you which I think might be better – Consociate

Answer 8

The pixels the user touches are a collection of x-y coordinates. Ian Coope proposed a linear least squares algorithm for fitting a circle non-iteratively here: https://ir.canterbury.ac.nz/handle/10092/11104. The idea is to linearize the fit using a simple change of variable.

I made a simple python implementation, described here: https://scikit-guess.readthedocs.io/en/latest/generated/skg.nsphere_fit.html.

You can find the source on GitHub: https://github.com/madphysicist/scikit-guess/blob/master/src/skg/nsphere.py. Since the function is only about 20 lines long, you should have no trouble translating it into your language of choice, as long as you have access to a library that allows you to invert matrices. In fact, the problem described here only requires inverting a 3x3 matrix, which you can do manually with arithmetic operations.

Here is a simple Java implementation specific to the 2D case. I did not include the scaling, which might be a good idea for a production application, or if you have a large number of pixels, but that's a very easy pre- and post-processing step that's left as an exercise for the reader:

// This is just a container for the result for the example.
// Make it proper with getters and setters if you like.
public class Circle
{
    public final double radius;
    public final double x;
    public final double y;

    public Circle(double radius, double x, double y)
    {
        this.radius = radius;
        this.x = x;
        this.y = y;
    }

    public static fit(int[] x, int[] y)
    {
        // exercise for the reader: check that x.length == y.length

        // To solve b * x = d in terms of least-squares projection
        //   1. bT * b * x = bT * y
        //   2. x = inv(bT * b) * bT * d
        // Matrix b[i] = [x[i], y[i], 1]
        // Vector d[i] = [x[i]*x[i] + y[i]*y[i]]
        long[][] bTb = new long[3][3] = {{0L, 0L, 0L},
                                         {0L, 0L, 0L},
                                         {0L, 0L, 0L}};
        long[] bTd = new long[3] {0L, 0L, 0L};

        for(int i = 0; i < x.length; i++) {
            long x2 = x[i] * x[i];
            long y2 = y[i] * y[i];
            long xy = x[i] * y[i];
            bTb[0][0] += x2;
            bTb[0][1] += xy;
            bTb[1][0] += xy;
            bTb[1][1] += y2;
            bTb[0][2] += x[i];
            bTb[2][0] += x[i];
            bTb[1][2] += y[i];
            bTb[2][1] += y[i];
            bTb[2][2] += 1L;
            long d = x2 + y2;
            bTd[0] += x[i] * d;
            bTd[1] += y[i] * d;
            bTd[2] += d;
        }

        // invert the matrix, e.g.: https://www.wikihow.com/Find-the-Inverse-of-a-3x3-Matrix
        double det_bTb =
            bTb[0][0] * (bTb[1][1] * bTb[2][2] - bTb[2][1] * bTb[1][2]) -
            bTb[0][1] * (bTb[1][0] * bTb[2][2] - bTb[2][0] * bTb[1][2]) +
            bTb[0][2] * (bTb[1][0] * bTb[2][1] - bTb[2][0] * bTb[1][1]);
        // exercise for reader: check if determinant is zero
        double[][] inv_bTb = new double[3][3];
        inv_bTb[0][0] = (double)(bTb[1][1] * bTb[2][2] - bTb[1][2] * bTb[2][1]) / det_bTb;
        inv_bTb[0][1] = (double)(bTb[0][2] * bTb[2][1] - bTb[0][1] * bTb[2][2]) / det_bTb;
        inv_bTb[0][2] = (double)(bTb[0][1] * bTb[1][2] - bTb[0][2] * bTb[1][1]) / det_bTb;
        inv_bTb[1][0] = (double)(bTb[2][0] * bTb[1][2] - bTb[1][0] * bTb[2][2]) / det_bTb;
        inv_bTb[1][1] = (double)(bTb[0][0] * bTb[2][2] - bTb[2][0] * bTb[0][2]) / det_bTb;
        inv_bTb[1][2] = (double)(bTb[1][0] * bTb[0][2] - bTb[0][0] * bTb[1][2]) / det_bTb;
        inv_bTb[2][0] = (double)(bTb[1][0] * bTb[2][1] - bTb[2][0] * bTb[1][1]) / det_bTb;
        inv_bTb[2][1] = (double)(bTb[2][0] * bTb[0][1] - bTb[0][0] * bTb[2][1]) / det_bTb;
        inv_bTb[2][2] = (double)(bTb[0][0] * bTb[1][1] - bTb[0][1] * bTb[1][0]) / det_bTb;

        double[] result = new double[3] {
            bTd[0] * inv_bTb[0][0] + bTd[1] * inv_bTb[0][1] + bTd[2] * inv_bTb[0][2],
            bTd[0] * inv_bTb[1][0] + bTd[1] * inv_bTb[1][1] + bTd[2] * inv_bTb[1][2],
            bTd[0] * inv_bTb[2][0] + bTd[1] * inv_bTb[2][1] + bTd[2] * inv_bTb[2][2]
        };


        return new Circle(Math.sqrt(result[2] +
                               0.25 * result[0] * result[0] +
                               0.25 * result[1] * result[1]),
                          0.5 * result[0], 0.5 * result[1]);
    }
}

Here is a sample of a hand-drawn circle I made, and the fit from this solution when the coordinates of all the black pixels are passed in:

Bilection