ios - guide - Dibuja un círculo perfecto desde el tacto del usuario

ios frameworks

Question

Tengo este proyecto de práctica que permite al usuario dibujar en la pantalla mientras toca con los dedos. Una aplicación muy simple que hice hace mucho tiempo. Mi pequeño primo se tomó la libertad de dibujar cosas con su dedo con mi iPad en esta aplicación (dibujos de niños: círculo, líneas, etc., lo que sea que se le venga a la mente). Luego comenzó a dibujar círculos y luego me pidió que lo convirtiera en un "buen círculo" (según entiendo: haga el círculo dibujado perfectamente redondo, ya que sabemos que no importa cuán estable tratemos de dibujar algo con el dedo en la pantalla, el círculo nunca es tan redondeado como debería ser un círculo).

Así que mi pregunta aquí es, ¿hay alguna forma en el código donde podamos detectar primero una línea dibujada por el usuario que forma un círculo y generar aproximadamente el mismo tamaño del círculo haciendo que sea perfectamente redondo en la pantalla. Hacer una recta no tan recta es algo que yo sabría hacer, pero en cuanto al círculo, no sé cómo hacerlo con Quartz u otros métodos.

Mi razonamiento es que, el inicio y el punto final de la línea deben tocarse o cruzarse después de que el usuario levanta su dedo para justificar el hecho de que estaba tratando de dibujar un círculo.

Answer 1

A veces es realmente útil dedicar un tiempo a reinventar la rueda. Como ya habrás notado, hay muchos frameworks, pero no es tan difícil implementar una solución simple pero útil sin introducir toda esa complejidad. (Por favor, no me malinterpreten, para cualquier propósito serio, es mejor usar un marco maduro y probado para ser estable).

Presentaré mis resultados primero y luego explicaré la idea simple y directa detrás de ellos.

Verá en mi implementación que no hay necesidad de analizar cada punto y hacer cálculos complejos. La idea es detectar alguna metainformación valiosa. tangent como ejemplo:

Identifiquemos un patrón simple y directo, típico de la forma seleccionada:

Entonces no es tan difícil implementar un mecanismo de detección de círculo basado en esa idea. Ver demostración de trabajo a continuación (Lo siento, estoy usando Java como la forma más rápida de proporcionar este rápido y un poco sucio ejemplo):

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

No debería ser un problema implementar un comportamiento similar en iOS, ya que solo necesitas varios eventos y coordenadas. Algo como el siguiente (ver 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];    
}

Hay varias mejoras posibles.

Comience en cualquier punto

El requisito actual es comenzar a dibujar un círculo desde el punto medio superior debido a la siguiente simplificación:

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

Tenga en cuenta que se utiliza el valor predeterminado del index . Una simple búsqueda a través de las "partes" disponibles de la forma eliminará esa limitación. Tenga en cuenta que deberá usar un búfer circular para detectar una forma completa:

En sentido horario y antihorario

Para admitir ambos modos, necesitará usar el búfer circular de la mejora anterior y buscar en ambas direcciones:

Dibuja una elipse

Ya tienes todo lo que necesitas en la matriz de bounds .

Simplemente usa esa información:

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

Otros gestos (opcional)

Finalmente, solo necesita manejar adecuadamente una situación cuando dx (o dy ) es igual a cero para admitir otros gestos:

Actualizar

Este pequeño PoC recibió una gran atención, así que actualicé un poco el código para que funcione sin problemas y proporcionar algunos consejos de dibujo, resaltar puntos de apoyo, etc.

Aquí está el 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);
}

Answer 2

Aquí hay otra manera. Utilizando UIView toca Bean, tocaMovido, tocaEnder y agrega puntos a una matriz. Usted divide la matriz en mitades y prueba si cada punto de una matriz tiene aproximadamente el mismo diámetro que su contraparte en la otra matriz como todos los demás 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);

}

Ese sonido esta bien? :)

Answer 3

Aquí hay una manera bastante simple de usar:

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

asumiendo esta grilla matriz:

 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 algunos UIViews en las ubicaciones "X" y pruébelos para que sean golpeados (en secuencia). Si todos son golpeados en secuencia, creo que sería justo dejar que el usuario diga "Bien hecho, dibujaste un círculo"

Suena bien? (y simple)

Answer 4

He tenido bastante suerte con un reconocedor de $ 1 debidamente entrenado ( http://depts.washington.edu/aimgroup/proj/dollar/ ). Lo usé para círculos, líneas, triángulos y cuadrados.

Fue hace mucho tiempo, antes de UIGestureRecognizer, pero creo que debería ser fácil crear subclases UIGestureRecognizer adecuadas.

Answer 5

No soy un experto en reconocimiento de formas, pero así es como podría abordar el problema.

Primero, mientras se muestra la ruta del usuario a mano alzada, se acumula en secreto una lista de muestras de puntos (x, y) junto con las horas. Puedes obtener ambos hechos de tus eventos de arrastre, envolverlos en un objeto modelo simple y apilarlos en una matriz mutable.

Probablemente desee tomar las muestras con bastante frecuencia, por ejemplo, cada 0.1 segundos. Otra posibilidad sería comenzar muy frecuentemente, tal vez cada 0.05 segundos, y observar cuánto tiempo demora el usuario; si se arrastran más de una cantidad de tiempo, entonces baje la frecuencia de la muestra (y suelte las muestras que se habrían perdido) a algo así como 0,2 segundos.

(Y no tome mis números para el evangelio, porque los saqué de mi sombrero. Experimente y encuentre mejores valores).

Segundo, analiza las muestras.

Querrá obtener dos hechos. Primero, el centro de la forma, que (IIRC) debería ser el promedio de todos los puntos. Segundo, el radio promedio de cada muestra de ese centro.

Si, como supuso @ user1118321, desea admitir polígonos, entonces el resto del análisis consiste en tomar esa decisión: si el usuario desea dibujar un círculo o un polígono. Puede ver las muestras como un polígono para comenzar a hacer esa determinación.

Hay varios criterios que puede usar:

• Tiempo: si el usuario permanece más tiempo en algunos puntos que en otros (que, si las muestras están en un intervalo constante, aparecerán como un grupo de muestras consecutivas cerca unas de otras en el espacio), esas pueden ser esquinas. Debe reducir el umbral de su esquina para que el usuario pueda hacer esto inconscientemente, en lugar de tener que pausar deliberadamente en cada esquina.
• Ángulo: un círculo tendrá aproximadamente el mismo ángulo de una muestra a la siguiente en todos los sentidos. Un polígono tendrá varios ángulos unidos por segmentos de línea recta; los ángulos son las esquinas. Para un polígono regular (el círculo para una elipse de un polígono irregular), los ángulos de las esquinas deben ser todos aproximadamente iguales; un polígono irregular tendrá diferentes ángulos de esquina.
• Intervalo: las esquinas de un polígono regular estarán separadas por un espacio igual dentro de la dimensión angular, y el radio será constante. Un polígono irregular tendrá intervalos angulares irregulares y / o un radio no constante.

El tercer y último paso es crear la forma, centrada en el punto central previamente determinado, con el radio previamente determinado.

No hay garantías de que todo lo que he dicho arriba funcione o sea eficiente, pero espero que al menos lo lleve por el camino correcto, y por favor, si alguien sabe más sobre reconocimiento de formas que yo (que es un nivel muy bajo) ve esto, siéntase libre de publicar un comentario o su propia respuesta.

Answer 6

Una técnica clásica de Visión por Computadora para detectar una forma es la Transformada Hough. Una de las cosas buenas de la Transformada Hough es que es muy tolerante con los datos parciales, los datos imperfectos y el ruido. Usando Hough para un círculo: http://en.wikipedia.org/wiki/Hough_transform#Circle_detection_process

Dado que su círculo está dibujado a mano, creo que la transformación de Hough puede ser una buena opción para usted.

Aquí hay una explicación "simplificada", me disculpo porque realmente no es tan simple. Gran parte de esto proviene de un proyecto escolar que hice hace muchos años.

La Transformada Hough es un esquema de votación. Se asigna una matriz bidimensional de enteros y todos los elementos se establecen en cero. Cada elemento corresponde a un solo píxel en la imagen que se analiza. Esta matriz se conoce como la matriz de acumuladores ya que cada elemento acumulará información, votos, lo que indica la posibilidad de que un píxel pueda estar en el origen de un círculo o arco.

Se aplica un detector de borde de operador de gradiente a la imagen y se graban los píxeles de borde, o bordes. Un edgel es un píxel que tiene una intensidad o color diferente con respecto a sus vecinos. El grado de diferencia se llama magnitud de gradiente. Para cada editor de suficiente magnitud, se aplica un esquema de votación que incrementará los elementos del conjunto de acumuladores. Los elementos que se incrementan (votaron) corresponden a los posibles orígenes de los círculos que pasan por el edgel bajo consideración. El resultado deseado es que si existe un arco, el verdadero origen recibirá más votos que los orígenes falsos.

Tenga en cuenta que los elementos del conjunto de acumuladores que se visitan para votar forman un círculo alrededor del editor en cuestión. Calcular las coordenadas x, y para votar es lo mismo que calcular las coordenadas x, y de un círculo que está dibujando.

En su imagen dibujada a mano, puede usar los píxeles configurados (coloreados) directamente en lugar de calcular los bordes.

Ahora, con píxeles ubicados imperfectamente, no necesariamente obtendrá un solo elemento de matriz de acumuladores con el mayor número de votos. Puede obtener una colección de elementos de matriz vecinos con un montón de votos, un clúster. El centro de gravedad de este grupo puede ofrecer una buena aproximación para el origen.

Tenga en cuenta que es posible que deba ejecutar la Transformada Hough para diferentes valores de radio R. La que produce el grupo más denso de votos es el ajuste "mejor".

Hay varias técnicas para usar para reducir votos por orígenes falsos. Por ejemplo, una ventaja del uso de edgels es que no solo tienen una magnitud sino que también tienen una dirección. Al votar, solo necesitamos votar por posibles orígenes en la dirección adecuada. Las ubicaciones que reciben votos formarán un arco en lugar de un círculo completo.

Aquí hay un ejemplo. Comenzamos con un círculo de radio uno y un conjunto de acumuladores inicializado. A medida que se considera cada píxel, se votan los orígenes potenciales. El verdadero origen recibe la mayor cantidad de votos, que en este caso es cuatro.

.  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

Answer 7

Una vez que determina que el usuario terminó de dibujar su forma donde comenzaron, puede tomar una muestra de las coordenadas que dibujaron e intentar ajustarlas a un círculo.

Aquí hay una solución de MATLAB para este problema: http://www.mathworks.com.au/matlabcentral/fileexchange/15060-fitcircle-m

El cual se basa en el documento Least-Squares Fitting of Circles and Ellipses de Walter Gander, Gene H. Golub y Rolf Strebel: http://www.emis.de/journals/BBMS/Bulletin/sup962/gander.pdf

El Dr. Ian Coope de la Universidad de Canterbury, Nueva Zelanda publicó un documento con el resumen:

El problema de determinar el círculo de mejor ajuste para un conjunto de puntos en el plano (o la generalización obvia para n dimensiones) se formula fácilmente como un problema de mínimos cuadrados totales no lineales que puede resolverse usando un algoritmo de minimización de Gauss-Newton. Este enfoque directo es ineficiente y extremadamente sensible a la presencia de valores atípicos. Una formulación alternativa permite que el problema se reduzca a un problema lineal de mínimos cuadrados que se resuelve trivialmente. Se muestra que el enfoque recomendado tiene la ventaja adicional de ser mucho menos sensible a los valores atípicos que el enfoque de mínimos cuadrados no lineales.

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

El archivo MATLAB puede calcular tanto el TLS no lineal como el problema lineal de LLS.