从用户的触摸中画出一个完美的圆圈

我有这个练习项目，允许用户用手指触摸屏幕。 非常简单的应用程序，我作为锻炼方式回来。 我的小表弟冒险用他的手指在我的iPad上用这个应用程序绘制东西（孩子们的图画：圆圈，线条等等，不pipe他在想什么）。 然后他开始画圈子，然后他让我把它做成“好圈子”（从我的理解上来说：把画出来的圆圈做得很圆，我们知道无论我们用手指在屏幕上画什么东西，圆圈永远不会像圆圈一样圆润）。

所以我的问题是，在代码中有什么办法，我们可以首先检测用户绘制的线形成一个圆，并通过使其在屏幕上完美地生成大致相同的大小的圆。 做一个不那么直线的东西我会知道该怎么做，但是对于圈子，我不太清楚如何用Quartz或其他方法来做这件事。

我的推理是，在用户举起手指来certificate他试图画出一个圆圈的事实后，线条的起点和终点必须相互接触或交叉。

有时花一些时间重新发明是非常有用的。 正如你可能已经注意到有很多框架，但是实现一个简单而又有用的解决scheme并不难，而不会引入所有的复杂性。 （请不要误解我的意思，因为任何严肃的目的，最好使用一些成熟的，经过validation的稳定框架）。

我将首先介绍我的结果，然后解释他们背后的简单而直接的想法。

在这里输入图像说明

你会看到在我的实现中没有必要分析每一个点，并做复杂的计算。 这个想法是发现一些有价值的元信息。 我将用切线作为例子：

在这里输入图像说明

让我们确定一个简单和直接的模式，典型的选定形状：

在这里输入图像说明

所以基于这个思想实现一个循环检测机制并不难。 查看下面的工作演示（对不起，我使用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(bx, by, ex, ey); } 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的默认值。 通过形状的可用“部分”的简单search将消除该限制。 请注意，您需要使用循环缓冲区才能检测完整的形状：

在这里输入图像说明

顺时针和逆时针

为了支持这两种模式，您将需要使用以前增强的循环缓冲区并在两个方向上进行search：

在这里输入图像说明

绘制一个椭圆

在bounds数组中，您已经拥有了所需的一切。

在这里输入图像说明

简单地使用这些数据： 

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

其他手势（可选）

最后，当dx （或dy ）等于零以便支持其他手势时，您只需要正确处理这种情况：

在这里输入图像说明

更新

这个小小的PoC受到了很高的关注，为了使它工作顺利，并提供了一些graphics提示，突出支持点等，我做了一些更新。

在这里输入图像说明

这里是代码： 

 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(bx, by, ex, ey); } 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); }

用于检测形状的经典计算机视觉技术是霍夫变换。 霍夫变换的好处之一是对部分数据，数据和噪声都非常宽容。 使用Hough作为圆圈： http : //en.wikipedia.org/wiki/Hough_transform#Circle_detection_process

鉴于你的圈子是手绘的，我认为霍夫变换可能是一个很好的匹配你。

这里有一个“简化”的解释，我对此并不那么简单抱歉。 其中大部分来自我多年前做的一个学校项目。

Hough变换是一个投票scheme。 整数的二维数组被分配并且所有元素被设置为零。 每个元素对应于被分析图像中的单个像素。 这个数组被称为累加器数组，因为每个元素将累积信息，投票，表明一个像素可能位于圆或圆弧的原点的可能性。

将梯度算子边缘检测器应用于图像，并logging边缘像素或边缘。 edgel是一个像素，与其相邻的像素具有不同的强度或颜色。 差异程度称为梯度大小。 对于具有足够大小的每个边缘1，应用投票scheme，其将增加累加器arrays的元素。 递增（投票）的元素对应于通过考虑边缘的圆的可能起源。 理想的结果是，如果存在一个弧，那么真正的起源将获得比错误起源更多的选票。

请注意，正在考虑的正在被访问的累加器arrays的元素形成围绕边界1的圆圈。 计算投票的x，y坐标与计算正在绘制的圆的x，y坐标相同。

在您的手绘图像中，您可以直接使用设置（彩色）像素，而不是计算边缘。

现在，如果像素位置不完善，则不一定会得到具有最多投票数的单个累加器数组元素。 你可能会得到一堆相邻数组元素的集合。 这个聚类的重心可能为原点提供了一个很好的近似值。

请注意，您可能必须针对半径R的不同值运行霍夫变换。生成更密集的选票集合的是“更好”拟合。

有各种技术可以用来减less对错误来源的投票。 例如使用边缘的一个优点是它们不仅有一个大小，而且它们也有一个方向。 投票时，我们只需要对可能的来源进行投票。 获得选票的地点将形成一个弧形，而不是一个完整的圆圈。

这是一个例子。 我们从一个半径为1的圆和一个初始化的累加器数组开始。 由于每个像素被认为是潜在的起源投票。 真正的起源获得最多的票数，在这种情况下是四个。 

 . 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 touchesBegan，touchesMoved，touchesEnded和添加点数组。 将数组分成两半，并testing一个数组中的每个点是否与另一个数组中的每个点的直径大致相同。 

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

那声音好吗？ 🙂

我不是形状识别专家，但这是我可能会遇到的问题。

首先，在自由地显示用户的path的同时，随着时间偷偷地累积点（x，y）样本的列表。 您可以从拖动事件中获取这两个事实，将它们包装到一个简单的模型对象中，然后将这些事件堆放在一个可变数组中。

你可能想要相当频繁地采样 – 比方说每0.1秒。 另一种可能性是开始真正频繁，也许每隔0.05秒，观察用户拖了多久; 如果它们的拖动时间超过一定的时间，则降低采样频率（并丢弃任何可能已经丢失的采样），例如0.2秒。

（不要把我的号码作为福音，因为我只是把他们从帽子里拿出来，试着find更好的价值。）

其次，分析样本。

你会想要得出两个事实。 首先，形状的中心（IIRC）应该是所有点的平均值。 其次，来自该中心的每个样本的平均半径。

如果@ user1118321猜到了，你想要支持多边形，那么剩下的分析包括做出这个决定：用户是否想绘制一个圆或多边形。 您可以将样品视为多边形，然后开始进行测定。

有几个标准可以使用：

  • 时间：如果用户在某些点上的hover时间比其他时间长（如果采样间隔恒定，则会在空间中显示为彼此靠近的连续样本的集合），那些可能是angular落。 你应该把你的angular落门槛设置得很小，这样用户就可以无意识地做到这一点，而不必在每个angular落刻意停下来。
  • angular度：从一个样本到下一个样本，一个圆圈的angular度大致相同。 一个多边形将有几个直线连接的angular度; angular是angular落。 对于一个正多边形（圆形到一个不规则的多边形的椭圆），angular的angular度应该大致相同; 一个不规则的多边形将有不同的angular落angular度。
  • 间隔：正多边形的angular将在angular度尺寸内相等的空间分开，并且半径将是恒定的。 不规则的多边形将具有不规则的angular度间隔和/或非恒定的半径。

第三步也是最后一步是创build以先前确定的中心点为中心的形状，并使用之前确定的半径。

不保证我上面所说的任何东西都能奏效，或者说效率很高，但是我希望它至less能让你走上正确的轨道，如果有人比我更了解形状认知（这是一个非常低的栏）这个，随时发表评论或你自己的答案。

我已经有一个经过适当训练的$ 1识别器（ http://depts.washington.edu/aimgroup/proj/dollar/ ）相当好运。 我用它的圆圈，线条，三angular形和正方形。

很早以前，在UIGestureRecognizer之前，我认为应该很容易地创build适当的UIGestureRecognizer子类。

一旦你确定用户完成绘制他们的形状开始，你可以采取他们绘制的坐标的样品，并尝试将它们适合一个圆圈。

这里有个解决这个问题的MATLAB解决scheme： http : //www.mathworks.com.au/matlabcentral/fileexchange/15060-fitcircle-m

这是基于Walter Gander，Gene H. Golub和Rolf Strebel的论文“圈与椭圆的最小二乘拟合” ： http ://www.emis.de/journals/BBMS/Bulletin/sup962/gander.pdf

新西兰坎特伯雷大学的Ian Coope博士发表了一篇摘要：

确定平面上一组点的最佳拟合圆的问题（或对n维的显而易见的推广）可以很容易地表示为一个非线性总最小二乘问题，可以使用高斯 – 牛顿最小化algorithm来解决。 这种直接的方法被certificate是低效率的，并且对exception值的存在极其敏感。 另一个公式可以将问题简化为线性最小二乘问题，这个问题可以平均解决。 与非线性最小二乘方法相比，所推荐的方法显示出具有对exception值更不敏感的附加优点。

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

MATLAB文件可以计算非线性TLS和线性LLS问题。

这是一个相当简单的方法： 

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

假设这个matrix网格： 

  ABCDEFGH 1 XX 2 XX 3 XX 4 XX 5 XX 6 XX 7 8

放置一些UIViews在“X”的位置，并testing它们成为命中（按顺序）。 如果他们都被顺序击中，我认为让用户说“做得好，你画了一个圈子”可能是公平的。

听起来不错？ （和简单）

Interesting Posts