Нарисуйте идеальный круг от прикосновения пользователя

У меня есть этот практический проект, который позволяет пользователю рисовать на экране, когда они касаются их пальцами. Очень простое приложение, которое я сделал в качестве упражнения назад. Мой маленький двоюродный брат позволил себе рисовать вещи с помощью моего iPad в этом приложении (детские рисунки: круги, линии и т. Д., Что бы ему ни приходило в голову). Затем он начал рисовать круги, а затем попросил меня сделать его «хорошим кругом» (из моего понимания: сделать нарисованный круг идеально круглым, поскольку мы знаем, насколько бы устойчивыми мы не пытались рисовать что-то пальцем на экране, круг никогда не бывает таким округлым, каким должен быть круг).

Поэтому мой вопрос здесь заключается в том, существует ли какой-либо способ в коде, где мы можем сначала обнаружить линию, нарисованную пользователем, которая образует круг, и создать примерно такой же размер круга, сделав его идеально круглым на экране. Я бы знал, как сделать не очень прямую прямую линию, но что касается круга, я не совсем знаю, как это сделать с помощью кварца или других методов.

Я рассуждаю так: начальная и конечная точки линии должны касаться друг друга или пересекаться после того, как пользователь поднимает палец, чтобы оправдать тот факт, что он действительно пытался нарисовать круг.

Иногда действительно полезно потратить некоторое время на изобретение колеса. Как вы, возможно, уже заметили, существует множество фреймворков, но не так сложно реализовать простое, но полезное решение, не представляя всей этой сложности. (Пожалуйста, не поймите меня неправильно, для каких-либо серьезных целей лучше использовать некоторые зрелые и зарекомендовавшие себя стабильные рамки).

Сначала я представлю свои результаты, а затем объясню простую и понятную идею.

Вы увидите, что в моей реализации нет необходимости анализировать каждую точку и выполнять сложные вычисления. Идея состоит в том, чтобы найти некоторую ценную метаинформацию. Я буду использовать тангенс в качестве примера:

Давайте определим простой и понятный шаблон, типичный для выбранной фигуры:

Так что не так сложно реализовать механизм обнаружения кругов, основанный на этой идее. См. Рабочую демонстрацию ниже (извините, я использую Java как самый быстрый способ предоставить этот быстрый и немного грязный пример):

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

Это не должно быть проблемой для реализации аналогичного поведения на iOS, так как вам просто нужно несколько событий и координат. Что-то вроде следующего (см. Пример ):

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

Есть несколько возможных улучшений.

Начать в любой момент

Текущее требование состоит в том, чтобы начать рисовать круг от верхней средней точки из-за следующего упрощения:

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

Обратите внимание, что используется значение по умолчанию index. Простой поиск доступных «частей» фигуры устранит это ограничение. Обратите внимание, что вам нужно использовать круговой буфер для определения полной формы:

По часовой стрелке и против часовой стрелки

Для поддержки обоих режимов вам нужно будет использовать кольцевой буфер из предыдущего улучшения и искать в обоих направлениях:

Нарисуйте эллипс

У вас есть все, что вам нужно, уже в boundsмассиве.

Просто используйте эти данные:

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

Другие жесты (необязательно)

Наконец, вам просто нужно правильно обработать ситуацию, когда dx(или dy) равен нулю, чтобы поддерживать другие жесты:

Обновить

Этому маленькому PoC уделялось достаточно много внимания, поэтому я немного обновил код, чтобы он работал плавно и предоставил некоторые подсказки по рисованию, выделение опорных точек и т. Д.

Вот код:

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

Классической техникой Computer Vision для определения формы является преобразование Хафа. Одна из приятных особенностей Hough Transform заключается в том, что она очень терпима к частичным данным, несовершенным данным и шумам. Использование Hough для круга: http://en.wikipedia.org/wiki/Hough_transform#Circle_detection_process

Учитывая, что ваш круг нарисован от руки, я думаю, что преобразование Хафа может вам подойти.

Вот «упрощенное» объяснение, я прошу прощения за то, что это не так просто. Во многом это из школьного проекта, который я сделал много лет назад.

Hough Transform - это схема голосования. Выделен двумерный массив целых чисел, и все элементы установлены в ноль. Каждый элемент соответствует одному пикселю в анализируемом изображении. Этот массив называется массивом-накопителем, поскольку каждый элемент будет накапливать информацию, голоса, указывающие на вероятность того, что пиксель может находиться в начале круга или дуги.

Детектор края оператора градиента применяется к изображению, и краевые пиксели или края записываются. Край - это пиксель, который имеет разную интенсивность или цвет по отношению к своим соседям. Степень различия называется величиной градиента. Для каждого ребра достаточной величины применяется схема голосования, которая будет увеличивать элементы массива аккумуляторов. Увеличиваемые элементы (за которые проголосовали) соответствуют возможным источникам окружностей, которые проходят через рассматриваемый край. Желаемый результат состоит в том, что если дуга существует, то истинное происхождение получит больше голосов, чем ложное происхождение.

Обратите внимание, что элементы массива аккумуляторов, которые посещаются для голосования, образуют окружность вокруг рассматриваемого края. Вычисление координат x, y для голосования аналогично вычислению координат x, y круга, который вы рисуете.

На рисованном изображении вы можете использовать заданные (цветные) пиксели напрямую, а не вычислять края.

Теперь с несовершенно расположенными пикселями вы не обязательно получите один элемент массива аккумуляторов с наибольшим количеством голосов. Вы можете получить коллекцию соседних элементов массива с кучей голосов, кластер. Центр тяжести этого скопления может предложить хорошее приближение к началу координат.

Обратите внимание, что вам, возможно, придется запустить преобразование Хафа для различных значений радиуса R. Тот, который производит более плотную группу голосов, - это «лучшее» соответствие.

Существуют различные методы, чтобы уменьшить количество голосов за ложное происхождение. Например, одним из преимуществ использования ребер является то, что они не только имеют величину, но и направление. При голосовании нам нужно только проголосовать за возможное происхождение в соответствующем направлении. Места, получающие голоса, будут образовывать дугу, а не полный круг.

Вот пример. Начнем с круга радиуса один и инициализированного массива аккумуляторов. Поскольку каждый пиксель считается потенциальным источником проголосовали за. Истинное происхождение получает большинство голосов, в данном случае это четыре.

.  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

Вот другой способ. Использование UIView touchSbegin, touchesMoved, touchesEnded и добавление точек в массив. Вы делите массив на две половины и проверяете, имеет ли каждая точка в одном массиве примерно такой же диаметр от своего аналога в другом массиве, что и все остальные пары.

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

}

Это звучит хорошо? :)

Я не эксперт по распознаванию фигур, но вот как я могу подойти к проблеме.

Во-первых, отображая путь пользователя от руки, тайно собирайте список точек (x, y) вместе со временем. Вы можете получить оба факта из событий перетаскивания, обернуть их в простой объект модели и собрать их в изменяемый массив.

Вы, вероятно, хотите брать образцы довольно часто, скажем, каждые 0,1 секунды. Другой возможностью было бы начать действительно часто, возможно, каждые 0,05 секунды, и посмотреть, как долго пользователь тянет; если они тянутся дольше, чем какое-то время, уменьшите частоту сэмплов (и отбросьте все пропущенные сэмплы) до 0,2 секунд

(И не принимайте мои цифры за Евангелие, потому что я просто вытащил их из своей шляпы. Экспериментируйте и найдите лучшие значения.)

Во-вторых, проанализируйте образцы.

Вы хотите получить два факта. Во-первых, центр фигуры, который (IIRC) должен быть просто средним из всех точек. Во-вторых, средний радиус каждого образца из этого центра.

Если, как догадался @ user1118321, вы хотите поддерживать полигоны, то остальная часть анализа состоит в принятии этого решения: хочет ли пользователь нарисовать круг или многоугольник. Вы можете посмотреть на образцы как на полигон, чтобы начать это определение.

Есть несколько критериев, которые вы можете использовать:

• Время: если пользователь зависает дольше в одних точках, чем в других (которые, если сэмплы находятся с постоянным интервалом, будут отображаться в виде скопления последовательных сэмплов рядом друг с другом в пространстве), это могут быть углы. Вы должны сделать свой угловой порог небольшим, чтобы пользователь мог делать это неосознанно, вместо того, чтобы вынужденно останавливаться на каждом углу.
• Угол: у окружности будет примерно один и тот же угол от одного образца к следующему. Многоугольник будет иметь несколько углов, соединенных отрезками прямых линий; углы углы. Для правильного многоугольника (от окружности до эллипса неправильного многоугольника) угловые углы должны быть примерно одинаковыми; неправильный многоугольник будет иметь разные угловые углы.
• Интервал: Углы правильного многоугольника будут находиться на одинаковом расстоянии друг от друга в пределах углового размера, а радиус будет постоянным. Неправильный многоугольник будет иметь неправильные угловые интервалы и / или непостоянный радиус.

Третий и последний шаг заключается в создании фигуры с центром в предварительно определенной центральной точке с заранее определенным радиусом.

Нет никаких гарантий, что все, что я сказал выше, будет работать или будет эффективно, но я надеюсь, что это, по крайней мере, выведет вас на правильный путь - и, пожалуйста, если кто-то, кто знает больше о распознавании формы, чем я (что является очень низкой планкой), видит это, не стесняйтесь оставить комментарий или свой собственный ответ.

Мне очень повезло с правильно обученным распознавателем за 1 доллар ( http://depts.washington.edu/aimgroup/proj/dollar/ ). Я использовал его для кругов, линий, треугольников и квадратов.

Это было давно, до UIGestureRecognizer, но я думаю, что это должно быть легко создать правильные подклассы UIGestureRecognizer.

Как только вы определили, что пользователь закончил рисовать свою форму, где он начал, вы можете взять образец координат, которые они нарисовали, и попытаться подогнать их к кругу.

Здесь есть решение MATLAB для решения этой проблемы: http://www.mathworks.com.au/matlabcentral/fileexchange/15060-fitcircle-m

Который основан на статье « Подгонка кругов и эллипсов по методу наименьших квадратов » Уолтера Гандера, Джина Х. Голуба и Рольфа Штребеля: http://www.emis.de/journals/BBMS/Bulletin/sup962/gander.pdf

Доктор Ян Купе из Кентерберийского университета, Новая Зеландия опубликовал статью с рефератом:

Задача определения круга, наилучшим образом подходящего к набору точек на плоскости (или очевидное обобщение на n-измерения), легко формулируется как нелинейная задача наименьших квадратов, которая может быть решена с использованием алгоритма минимизации Гаусса-Ньютона. Этот прямой подход неэффективен и чрезвычайно чувствителен к присутствию выбросов. Альтернативная формулировка позволяет свести задачу к линейной задаче наименьших квадратов, которая решается тривиально. Показано, что рекомендуемый подход имеет дополнительное преимущество, поскольку он гораздо менее чувствителен к выбросам, чем нелинейный метод наименьших квадратов.

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

Файл MATLAB может вычислять как нелинейную задачу TLS, так и линейную задачу LLS.

Вот довольно простой способ использования:

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

предполагая эту матрицу сетки:

 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

Поместите несколько UIViews в местах «X» и проверьте их на предмет попадания (по порядку). Если их всех ударить последовательно, я думаю, что было бы справедливо позволить пользователю сказать: «Хорошо, вы нарисовали круг»

Звучит хорошо? (и просто)