根据用户的触摸画一个完美的圆圈

有时花点时间重新发明轮子真的很有用。正如您可能已经注意到的那样,有很多框架,但在不引入所有复杂性的情况下实现一个简单但有用的解决方案并不难。(请不要误解我的意思,出于任何严肃的目的,最好使用一些成熟且已证明稳定的框架)。

我将首先介绍我的结果,然后解释它们背后简单明了的想法。

您将在我的实现中看到,不需要分析每一个点并进行复杂的计算。这个想法是为了发现一些有价值的元信息。我会使用 tangent 例如:

让我们确定一个简单明了的模式,这是所选形状的典型模式:

因此,基于该思想实现圆检测机制并不难。请参阅下面的工作演示(对不起,我使用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上实现类似的行为应该不是问题,因为您只需要几个事件和坐标。类似以下内容(请参见 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];    
}

有几种可能的增强功能。

从任何一点开始

由于以下简化,目前的要求是从顶部中点开始绘制圆:

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

用于检测形状的经典计算机视觉技术是霍夫变换。霍夫变换的一个优点是它对部分数据、不完美数据和噪声都非常宽容。将霍夫用于圆: http://en.wikipedia.org/wiki/Hough_transform#Circle_detection_process

考虑到你的圆圈是手绘的,我认为霍夫变换可能很适合你。

这是一个“简化”的解释,我很抱歉没有那么简单。其中大部分来自我多年前做的一个学校项目。

霍夫变换是一个投票方案。分配一个二维整数数组,所有元素都设置为零。每个元素对应于正在分析的图像中的单个像素。该阵列被称为累加器阵列,因为每个元素都将累积信息、投票,指示像素可能位于圆或弧的原点的可能性。

将梯度算子边缘检测器应用于图像,并记录边缘像素或边缘。边缘像素是相对于其相邻像素具有不同强度或颜色的像素。差异的程度称为梯度幅度。对于足够大小的每个边缘,应用将递增累加器阵列的元素的表决方案。被递增(投票支持)的元素对应于通过所考虑的边缘的圆的可能起源。理想的结果是,如果存在弧,那么真正的起源将比虚假的起源获得更多的选票。

注意,为了投票而访问的累加器阵列的元素围绕所考虑的边缘形成一个圆圈。计算要投票的x,y坐标与计算正在绘制的圆的x,y坐标相同。

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

现在,对于位置不完全的像素,您不一定会得到一个具有最大票数的累加器数组元素。您可能会得到一个相邻数组元素的集合,其中包含一堆投票,即一个集群。这个星团的重心可能为原点提供了一个很好的近似值。

请注意,您可能需要对半径R的不同值运行霍夫变换。产生更密集的投票簇的是“更好”的拟合。

有各种各样的技术可以用来减少虚假来源的选票。例如,使用扁边的一个优点是,它们不仅有大小,而且还有方向。在投票时,我们只需要在适当的方向上对可能的起源进行投票。接受投票的地点将形成一个弧形,而不是一个完整的圆圈。

这是一个例子。我们从一个半径为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和向数组添加点。将数组一分为二,并测试一个数组中的每个点与另一个数组的对应点的直径是否与其他所有对的直径大致相同。

    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猜测的那样,您想要支持多边形,那么分析的其余部分包括做出决定:用户是想要画一个圆还是一个多边形。您可以将样本视为一个多边形来开始进行确定。

您可以使用以下几个标准:

• 时间:如果用户在某些点停留的时间比其他点长(如果采样间隔不变,则会在空间中显示为一组相邻的连续采样),则这些点可能是角落。你应该把你的角落阈值设置得很小,这样用户就可以无意识地做到这一点,而不是故意在每个角落停下来。
• 角度:一个圆从一个样本到下一个样本的角度大致相同。一个多边形将有多个由直线段连接的角度;角就是角。对于正多边形(从圆到不规则多边形的椭圆),转角应该大致相同;不规则多边形将具有不同的转角。
• 间隔:正多边形的角在角度维度内的间距相等,半径不变。不规则多边形将具有不规则的角度间隔和/或不恒定的半径。

第三步也是最后一步是创建以先前确定的中心点为中心、具有先前确定的半径的形状。

不能保证我上面说的任何话都会奏效或有效,但我希望它至少能让你走上正轨。如果有人比我更了解形状识别(这是一个很低的门槛),请随时发表评论或自己的回答。

一旦确定用户在开始绘制形状的位置完成绘制,就可以对用户绘制的坐标进行采样,并尝试将其拟合到一个圆中。

这里有一个MATLAB解决方案来解决这个问题: 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维的明显推广)很容易 公式化为非线性全最小二乘问题 使用高斯-牛顿最小化算法求解。这 直截了当的方法被证明是低效的,而且极其低效 对异常值的存在敏感。一种替代配方 允许将问题简化为线性最小二乘问题 这是微不足道地解决的。推荐的方法显示 对异常值的敏感性远低于 非线性最小二乘法。

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

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

我有一个训练有素的1美元识别器,运气很好( http://depts.washington.edu/aimgroup/proj/dollar/ ). 我用它来画圆、线、三角形和正方形。

这是很久以前的事了,在UIGestureRecognizer之前,但我认为创建合适的UIGesture Recognizer子类应该很容易。

以下是一种相当简单的使用方法:

- (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”位置,并测试它们是否命中(按顺序)。如果他们都按顺序被击中,我认为让用户说“干得好,你画了一个圆圈”可能是公平的

听起来还好吗?(而且很简单)

用户触摸的像素是x-y坐标的集合。Ian Coope在这里提出了一种用于非迭代拟合圆的线性最小二乘算法: https://ir.canterbury.ac.nz/handle/10092/11104 其思想是使用变量的简单变化来使拟合线性化。

我做了一个简单的python实现,如下所述: https://scikit-guess.readthedocs.io/en/latest/generated/skg.nsphere_fit.html .

你可以在GitHub上找到来源: https://github.com/madphysicist/scikit-guess/blob/master/src/skg/nsphere.py 。由于该函数只有大约20行长,只要您可以访问允许反转矩阵的库,就可以将其翻译成您选择的语言。事实上,这里描述的问题只需要反转3x3矩阵,这可以通过算术运算手动完成。

这里有一个针对2D情况的简单Java实现。我没有包括缩放,这对于生产应用程序来说可能是个好主意,或者如果你有大量的像素,但这是一个非常简单的预处理和后处理步骤,留给读者练习:

// This is just a container for the result for the example.
// Make it proper with getters and setters if you like.
public class Circle
{
    public final double radius;
    public final double x;
    public final double y;

    public Circle(double radius, double x, double y)
    {
        this.radius = radius;
        this.x = x;
        this.y = y;
    }

    public static fit(int[] x, int[] y)
    {
        // exercise for the reader: check that x.length == y.length

        // To solve b * x = d in terms of least-squares projection
        //   1. bT * b * x = bT * y
        //   2. x = inv(bT * b) * bT * d
        // Matrix b[i] = [x[i], y[i], 1]
        // Vector d[i] = [x[i]*x[i] + y[i]*y[i]]
        long[][] bTb = new long[3][3] = {{0L, 0L, 0L},
                                         {0L, 0L, 0L},
                                         {0L, 0L, 0L}};
        long[] bTd = new long[3] {0L, 0L, 0L};

        for(int i = 0; i < x.length; i++) {
            long x2 = x[i] * x[i];
            long y2 = y[i] * y[i];
            long xy = x[i] * y[i];
            bTb[0][0] += x2;
            bTb[0][1] += xy;
            bTb[1][0] += xy;
            bTb[1][1] += y2;
            bTb[0][2] += x[i];
            bTb[2][0] += x[i];
            bTb[1][2] += y[i];
            bTb[2][1] += y[i];
            bTb[2][2] += 1L;
            long d = x2 + y2;
            bTd[0] += x[i] * d;
            bTd[1] += y[i] * d;
            bTd[2] += d;
        }

        // invert the matrix, e.g.: https://www.wikihow.com/Find-the-Inverse-of-a-3x3-Matrix
        double det_bTb =
            bTb[0][0] * (bTb[1][1] * bTb[2][2] - bTb[2][1] * bTb[1][2]) -
            bTb[0][1] * (bTb[1][0] * bTb[2][2] - bTb[2][0] * bTb[1][2]) +
            bTb[0][2] * (bTb[1][0] * bTb[2][1] - bTb[2][0] * bTb[1][1]);
        // exercise for reader: check if determinant is zero
        double[][] inv_bTb = new double[3][3];
        inv_bTb[0][0] = (double)(bTb[1][1] * bTb[2][2] - bTb[1][2] * bTb[2][1]) / det_bTb;
        inv_bTb[0][1] = (double)(bTb[0][2] * bTb[2][1] - bTb[0][1] * bTb[2][2]) / det_bTb;
        inv_bTb[0][2] = (double)(bTb[0][1] * bTb[1][2] - bTb[0][2] * bTb[1][1]) / det_bTb;
        inv_bTb[1][0] = (double)(bTb[2][0] * bTb[1][2] - bTb[1][0] * bTb[2][2]) / det_bTb;
        inv_bTb[1][1] = (double)(bTb[0][0] * bTb[2][2] - bTb[2][0] * bTb[0][2]) / det_bTb;
        inv_bTb[1][2] = (double)(bTb[1][0] * bTb[0][2] - bTb[0][0] * bTb[1][2]) / det_bTb;
        inv_bTb[2][0] = (double)(bTb[1][0] * bTb[2][1] - bTb[2][0] * bTb[1][1]) / det_bTb;
        inv_bTb[2][1] = (double)(bTb[2][0] * bTb[0][1] - bTb[0][0] * bTb[2][1]) / det_bTb;
        inv_bTb[2][2] = (double)(bTb[0][0] * bTb[1][1] - bTb[0][1] * bTb[1][0]) / det_bTb;

        double[] result = new double[3] {
            bTd[0] * inv_bTb[0][0] + bTd[1] * inv_bTb[0][1] + bTd[2] * inv_bTb[0][2],
            bTd[0] * inv_bTb[1][0] + bTd[1] * inv_bTb[1][1] + bTd[2] * inv_bTb[1][2],
            bTd[0] * inv_bTb[2][0] + bTd[1] * inv_bTb[2][1] + bTd[2] * inv_bTb[2][2]
        };


        return new Circle(Math.sqrt(result[2] +
                               0.25 * result[0] * result[0] +
                               0.25 * result[1] * result[1]),
                          0.5 * result[0], 0.5 * result[1]);
    }
}

这是我画的一个手绘圆的样本,以及当所有黑色像素的坐标都通过时,这个解决方案的拟合: