Draw a perfect circle from user's touch

问题:

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 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 "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 like 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.

回答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);
}

回答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

回答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? :)

回答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.

回答5:

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.

回答6:

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.

回答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 )