Desenhe um círculo perfeito com o toque do usuário

Eu tenho esse projeto de prática que permite ao usuário desenhar na tela enquanto toca com os dedos. App muito simples que fiz como exercício há muito tempo. Meu primo teve a liberdade de desenhar coisas com o dedo com o meu iPad neste aplicativo (desenhos para crianças: círculo, linhas, etc., o que lhe veio à cabeça). Então ele começou a desenhar círculos e então me pediu para torná-lo "bom círculo" (pelo meu entendimento: faça o círculo desenhado perfeitamente redondo, pois sabemos, por mais estável que seja, tentemos desenhar algo com o dedo na tela, um círculo nunca é realmente tão arredondado como deveria ser).

Portanto, minha pergunta aqui é que, existe alguma maneira no código em que possamos primeiro detectar uma linha desenhada pelo usuário que forma um círculo e gerar aproximadamente o mesmo tamanho do círculo, fazendo-o perfeitamente redondo na tela. Fazer uma linha não tão reta é algo que eu saberia fazer, mas, quanto ao círculo, não sei como fazê-lo com quartzo ou outros métodos.

Meu raciocínio é que, o ponto inicial e final da linha devem se tocar ou cruzar após o usuário levantar o dedo para justificar o fato de que ele estava tentando desenhar um círculo.

Às vezes, é realmente útil gastar algum tempo reinventando a roda. Como você já deve ter notado, existem muitas estruturas, mas não é tão difícil implementar uma solução simples, mas útil, sem introduzir toda essa complexidade. (Por favor, não me entenda mal, para qualquer propósito sério, é melhor usar alguma estrutura madura e comprovadamente estável).

Apresentarei meus resultados primeiro e depois explicarei a idéia simples e direta por trás deles.

Você verá na minha implementação que não há necessidade de analisar todos os pontos e fazer cálculos complexos. A ideia é identificar algumas informações meta valiosas. Vou usar a tangente como exemplo:

Vamos identificar um padrão simples e direto, típico da forma selecionada:

Portanto, não é tão difícil implementar um mecanismo de detecção de círculos com base nessa ideia. Veja a demonstração de trabalho abaixo (desculpe, estou usando Java como a maneira mais rápida de fornecer este exemplo rápido e um pouco sujo):

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

Não deve ser um problema implementar um comportamento semelhante no iOS, pois você só precisa de vários eventos e coordenadas. Algo como o seguinte (veja o exemplo ):

- (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];    
}

Existem várias melhorias possíveis.

Comece a qualquer momento

O requisito atual é começar a desenhar um círculo a partir do ponto médio superior devido à seguinte simplificação:

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

Observe que o valor padrão de indexé usado. Uma simples pesquisa nas "partes" disponíveis da forma removerá essa limitação. Observe que você precisará usar um buffer circular para detectar uma forma completa:

No sentido horário e anti-horário

Para oferecer suporte a ambos os modos, você precisará usar o buffer circular do aprimoramento anterior e pesquisar nas duas direções:

Desenhar uma elipse

Você tem tudo o que precisa já na boundsmatriz.

Basta usar esses dados:

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

Outros gestos (opcional)

Finalmente, você só precisa lidar adequadamente com uma situação em que dx(ou dy) seja igual a zero para suportar outros gestos:

Atualizar

Esse pequeno PoC recebeu muita atenção, então eu atualizei o código um pouco para fazê-lo funcionar sem problemas e fornecer algumas dicas de desenho, destacar pontos de apoio etc.:

Aqui está o código:

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

Uma técnica clássica de visão computacional para detectar uma forma é a transformação de Hough. Uma das coisas boas da Hough Transform é que ela é muito tolerante com dados parciais, dados imperfeitos e ruídos. Usando Hough para um círculo: http://en.wikipedia.org/wiki/Hough_transform#Circle_detection_process

Dado que seu círculo é desenhado à mão, acho que a transformação de Hough pode ser uma boa combinação para você.

Aqui está uma explicação "simplificada", peço desculpas por não ser tão simples assim. Muito disso é de um projeto escolar que eu fiz muitos anos atrás.

A Hough Transform é um esquema de votação. Uma matriz bidimensional de números inteiros é alocada e todos os elementos são definidos como zero. Cada elemento corresponde a um único pixel na imagem que está sendo analisada. Essa matriz é chamada de matriz acumuladora, pois cada elemento acumula informações, votos, indicando a possibilidade de um pixel estar na origem de um círculo ou arco.

Um detector de borda do operador de gradiente é aplicado à imagem e os pixels da borda, ou bordas, são gravados. Um edgel é um pixel que possui uma intensidade ou cor diferente em relação aos seus vizinhos. O grau de diferença é chamado de magnitude do gradiente. Para cada edgel de magnitude suficiente é aplicado um esquema de votação que incrementará elementos da matriz do acumulador. Os elementos que estão sendo incrementados (votados) correspondem às possíveis origens dos círculos que passam pelo edgel em consideração. O resultado desejado é que, se existir um arco, a verdadeira origem receberá mais votos do que as falsas origens.

Observe que os elementos da matriz do acumulador que estão sendo visitados para votação formam um círculo em torno do edgel em consideração. Calcular as coordenadas x, y para votar é o mesmo que calcular as coordenadas x, y de um círculo que você está desenhando.

Na imagem desenhada à mão, você poderá usar os pixels definidos (coloridos) diretamente, em vez de calcular os bordos.

Agora, com pixels imperfeitamente localizados, você não obterá necessariamente um único elemento da matriz do acumulador com o maior número de votos. Você pode obter uma coleção de elementos de matriz vizinhos com muitos votos, um cluster. O centro de gravidade deste aglomerado pode oferecer uma boa aproximação para a origem.

Observe que talvez você precise executar a Transformação de Hough para diferentes valores do raio R. O que produz o conjunto de votos mais denso é o ajuste "melhor".

Existem várias técnicas a serem usadas para reduzir votos em origens falsas. Por exemplo, uma vantagem do uso de bordas é que elas não apenas possuem uma magnitude, mas também têm uma direção. Ao votar, precisamos votar apenas em possíveis origens na direção apropriada. Os locais que receberam votos formariam um arco em vez de um círculo completo.

Aqui está um exemplo. Começamos com um círculo de raio um e uma matriz de acumulador inicializada. Como cada pixel é considerado, origens potenciais são votadas. A verdadeira origem recebe mais votos, que neste caso são quatro.

.  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

Aqui está outro caminho. Usando o UIView touchesBegan, touchesMoved, touchesEnded e adicionando pontos a uma matriz. Você divide a matriz em metades e testa se cada ponto em uma matriz tem aproximadamente o mesmo diâmetro de sua contraparte na outra matriz que todos os outros pares.

    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);

}

Isso soa bem? :)

Não sou especialista em reconhecimento de formas, mas eis como posso abordar o problema.

Primeiro, enquanto exibe o caminho do usuário à mão livre, acumule secretamente uma lista de amostras de pontos (x, y) juntamente com o tempo. Você pode obter os dois fatos dos eventos de arrastar, agrupá-los em um objeto de modelo simples e empilhá-los em uma matriz mutável.

Você provavelmente deseja colher as amostras com bastante frequência - digamos, a cada 0,1 segundos. Outra possibilidade seria começar muito frequente, talvez a cada 0,05 segundos, e observar quanto tempo o usuário se arrasta; se eles arrastarem mais do que um certo período de tempo, reduza a frequência da amostra (e largue todas as amostras que seriam perdidas) para algo como 0,2 segundos.

(E não tome meus números para o evangelho, porque eu os tirei do meu chapéu. Experimente e encontre valores melhores.)

Segundo, analise as amostras.

Você vai querer derivar dois fatos. Primeiro, o centro da forma, que (IIRC) deve ser apenas a média de todos os pontos. Segundo, o raio médio de cada amostra desse centro.

Se, como @ user1118321 adivinhou, você deseja suportar polígonos, o restante da análise consiste em tomar essa decisão: se o usuário deseja desenhar um círculo ou polígono. Você pode ver as amostras como um polígono para começar a fazer essa determinação.

Existem vários critérios que você pode usar:

• Tempo: se o usuário pairar por mais tempo em alguns pontos do que outros (que, se as amostras estiverem em um intervalo constante, aparecerão como um cluster de amostras consecutivas próximas no espaço), esses podem ser cantos. Você deve reduzir seu limite de canto para que o usuário possa fazer isso inconscientemente, em vez de ter que parar deliberadamente em cada canto.
• Ângulo: Um círculo terá aproximadamente o mesmo ângulo de uma amostra para a seguinte. Um polígono terá vários ângulos unidos por segmentos de linha reta; os ângulos são os cantos. Para um polígono regular (o círculo até a elipse de um polígono irregular), os ângulos dos cantos devem ser aproximadamente os mesmos; um polígono irregular terá ângulos de canto diferentes.
• Intervalo: os cantos de um polígono regular terão espaço igual na dimensão angular e o raio será constante. Um polígono irregular terá intervalos angulares irregulares e / ou um raio não constante.

O terceiro e último passo é criar a forma, centralizada no ponto central previamente determinado, com o raio previamente determinado.

Não há garantias de que qualquer coisa que eu disse acima funcione ou seja eficiente, mas espero que pelo menos o coloque no caminho certo - e, por favor, se alguém que sabe mais sobre o reconhecimento de formas do que eu (que é uma barra muito baixa) vê isso, fique à vontade para postar um comentário ou sua própria resposta.

Eu tive muita sorte com um reconhecedor de US $ 1 devidamente treinado ( http://depts.washington.edu/aimgroup/proj/dollar/ ). Usei-o para círculos, linhas, triângulos e quadrados.

Isso foi há muito tempo, antes do UIGestureRecognizer, mas acho que deve ser fácil criar subclasses apropriadas do UIGestureRecognizer.

Depois de determinar que o usuário terminou de desenhar sua forma onde eles começaram, você pode pegar uma amostra das coordenadas pelas quais ele desenhou e tentar ajustá-las em um círculo.

Há uma solução MATLAB para esse problema aqui: http://www.mathworks.com.au/matlabcentral/fileexchange/15060-fitcircle-m

Que é baseado no trabalho de mínimos quadrados de círculos e elipses de Walter Gander, Gene H. Golub e Rolf Strebel: http://www.emis.de/journals/BBMS/Bulletin/sup962/gander.pdf

O Dr. Ian Coope, da Universidade de Canterbury, Nova Zelândia, publicou um artigo com o resumo:

O problema de determinar o círculo de melhor ajuste para um conjunto de pontos no plano (ou a óbvia generalização para n-dimensões) é facilmente formulado como um problema de mínimos quadrados totais não lineares que pode ser resolvido usando um algoritmo de minimização de Gauss-Newton. Essa abordagem direta mostra-se ineficiente e extremamente sensível à presença de discrepantes. Uma formulação alternativa permite que o problema seja reduzido a um problema linear de mínimos quadrados que é resolvido trivialmente. A abordagem recomendada mostra a vantagem adicional de ser muito menos sensível a valores discrepantes do que a abordagem não linear de mínimos quadrados.

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

O arquivo MATLAB pode calcular o problema TLS não linear e LLS linear.

Aqui está uma maneira bastante simples de usar:

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

assumindo esta grade matricial:

 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

Coloque algumas UIViews nos locais "X" e teste-as para serem atingidas (em sequência). Se todos eles forem atingidos em sequência, acho que seria justo deixar o usuário dizer "Muito bem, você desenhou um círculo"

Parece bom? (e simples)