Zeichnen Sie einen perfekten Kreis aus der Berührung des Benutzers

176

Ich habe dieses Übungsprojekt, mit dem der Benutzer auf dem Bildschirm zeichnen kann, wenn er mit den Fingern berührt. Sehr einfache App, die ich vor langer Zeit als Übung gemacht habe. Mein kleiner Cousin hat sich erlaubt, mit meinem iPad in dieser App Dinge mit dem Finger zu zeichnen (Kinderzeichnungen: Kreis, Linien usw., was auch immer ihm in den Sinn kam). Dann fing er an, Kreise zu zeichnen, und dann bat er mich, einen "guten Kreis" zu machen (nach meinem Verständnis: Machen Sie den gezeichneten Kreis perfekt rund, da wir wissen, egal wie stabil wir versuchen, etwas mit dem Finger auf dem Bildschirm zu zeichnen, a Kreis ist nie wirklich so gerundet wie ein Kreis sein sollte).

Meine Frage hier ist also, ob es im Code eine Möglichkeit gibt, zuerst eine vom Benutzer gezeichnete Linie zu erkennen, die einen Kreis bildet, und ungefähr die gleiche Größe des Kreises zu erzeugen, indem wir ihn auf dem Bildschirm perfekt rund machen. Ich würde wissen, wie man eine nicht so gerade Linie gerade macht, aber was den Kreis betrifft, weiß ich nicht genau, wie ich es mit Quarz oder anderen Methoden machen soll.

Meine Argumentation ist, dass sich Start- und Endpunkt der Linie berühren oder kreuzen müssen, nachdem der Benutzer seinen Finger gehoben hat, um die Tatsache zu rechtfertigen, dass er versucht hat, tatsächlich einen Kreis zu zeichnen.

Unheilig
quelle
2
In diesem Szenario kann es schwierig sein, den Unterschied zwischen einem Kreis und einem Polygon zu erkennen. Wie wäre es mit einem "Kreiswerkzeug", bei dem der Benutzer klickt, um die Mitte oder eine Ecke eines Begrenzungsrechtecks ​​zu definieren, und zieht, um den Radius zu ändern oder die gegenüberliegende Ecke festzulegen?
user1118321
2
@ user1118321: Dies widerspricht dem Konzept, nur einen Kreis zeichnen zu können und einen perfekten Kreis zu haben. Im Idealfall sollte die App allein anhand der Zeichnung des Benutzers erkennen, ob der Benutzer einen Kreis (mehr oder weniger), eine Ellipse oder ein Polygon gezeichnet hat. (Außerdem sind Polygone für diese App möglicherweise nicht verfügbar - es können nur Kreise oder Linien sein.)
Peter Hosey
Also, auf welche Antwort sollte ich das Kopfgeld geben? Ich sehe viele gute Kandidaten.
Peter Hosey
@Unheilig: Ich habe keine Fachkenntnisse in diesem Bereich, abgesehen von einem entstehenden Verständnis von Trig. Die Antworten, die für mich das größte Potenzial aufweisen, sind stackoverflow.com/a/19071980/30461 , stackoverflow.com/a/19055873/30461 , stackoverflow.com/a/18995771/30461 , möglicherweise stackoverflow.com/a/ 18992200/30461 und meine eigene. Das sind diejenigen, die ich zuerst versuchen würde. Ich überlasse die Bestellung Ihnen.
Peter Hosey
1
@Gene: Vielleicht könnten Sie die relevanten Informationen zusammenfassen und in einer Antwort auf weitere Details verweisen.
Peter Hosey

Antworten:

381

Manchmal ist es wirklich nützlich, etwas Zeit damit zu verbringen, das Rad neu zu erfinden. Wie Sie vielleicht bereits bemerkt haben, gibt es viele Frameworks, aber es ist nicht so schwer, eine einfache, aber dennoch nützliche Lösung zu implementieren, ohne all diese Komplexität einzuführen. (Bitte verstehen Sie mich nicht falsch, für jeden ernsthaften Zweck ist es besser, ein ausgereiftes und nachweislich stabiles Framework zu verwenden.)

Ich werde zuerst meine Ergebnisse präsentieren und dann die einfache und unkomplizierte Idee dahinter erläutern.

Geben Sie hier die Bildbeschreibung ein

Sie werden sehen, dass in meiner Implementierung nicht jeder einzelne Punkt analysiert und komplexe Berechnungen durchgeführt werden müssen. Die Idee ist, einige wertvolle Metainformationen zu finden. Ich werde Tangente als Beispiel verwenden:

Geben Sie hier die Bildbeschreibung ein

Lassen Sie uns ein einfaches und einfaches Muster identifizieren, das für die ausgewählte Form typisch ist:

Geben Sie hier die Bildbeschreibung ein

Es ist also nicht so schwer, einen Kreiserkennungsmechanismus zu implementieren, der auf dieser Idee basiert. Siehe Arbeitsdemo unten (Entschuldigung, ich verwende Java als schnellsten Weg, um dieses schnelle und etwas schmutzige Beispiel bereitzustellen):

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

Es sollte kein Problem sein, ein ähnliches Verhalten unter iOS zu implementieren, da Sie nur mehrere Ereignisse und Koordinaten benötigen. So etwas wie das Folgende (siehe Beispiel ):

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

Es sind mehrere Verbesserungen möglich.

Beginnen Sie an einem beliebigen Punkt

Derzeit ist es aufgrund der folgenden Vereinfachung erforderlich, einen Kreis vom oberen Mittelpunkt aus zu zeichnen:

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

Bitte beachten Sie, dass der Standardwert von indexverwendet wird. Eine einfache Suche durch die verfügbaren "Teile" der Form hebt diese Einschränkung auf. Bitte beachten Sie, dass Sie einen kreisförmigen Puffer verwenden müssen, um eine vollständige Form zu erkennen:

Geben Sie hier die Bildbeschreibung ein

Im Uhrzeigersinn und gegen den Uhrzeigersinn

Um beide Modi zu unterstützen, müssen Sie den Ringpuffer aus der vorherigen Erweiterung verwenden und in beide Richtungen suchen:

Geben Sie hier die Bildbeschreibung ein

Zeichne eine Ellipse

Sie haben alles, was Sie brauchen, bereits im boundsArray.

Geben Sie hier die Bildbeschreibung ein

Verwenden Sie einfach diese Daten:

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

Andere Gesten (optional)

Schließlich müssen Sie nur eine Situation richtig behandeln, in der dx(oder dy) gleich Null ist, um andere Gesten zu unterstützen:

Geben Sie hier die Bildbeschreibung ein

Aktualisieren

Dieser kleine PoC hat eine ziemlich hohe Aufmerksamkeit erhalten, daher habe ich den Code ein wenig aktualisiert, damit er reibungslos funktioniert und einige Zeichenhinweise enthält, unterstützende Punkte hervorhebt usw.:

Geben Sie hier die Bildbeschreibung ein

Hier ist der Code:

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);
}
Renat Gilmanov
quelle
76
Spektakuläre Antwort Renat. Klare Beschreibung des Ansatzes, Bilder, die den Prozess dokumentieren, auch Animationen. Scheint auch die allgemeinste, robusteste Lösung zu sein. Tangenten klingen nach einer wirklich cleveren Idee - ähnlich wie anfängliche (aktuelle?) Handschrifterkennungstechniken. Frage mit Lesezeichen für diese Antwort. :)
Enhzflep
27
Allgemeiner: Eine kurze, verständliche Erklärung UND Diagramme UND eine animierte Demo UND Code UND Variationen? Dies ist eine ideale Antwort auf den Stapelüberlauf.
Peter Hosey
11
Dies ist eine so gute Antwort, ich kann fast verzeihen, dass er Computergrafiken in Java macht! ;)
Nicolas Miari
4
Wird es zu Weihnachten, Santa Renat, weitere überraschende Updates (dh mehr Formen usw.) geben? :-)
Unheilig
1
Beeindruckend. Tour de Force.
Wogsland
14

Eine klassische Computer Vision-Technik zum Erkennen einer Form ist die Hough-Transformation. Eines der schönen Dinge an der Hough-Transformation ist, dass sie sehr tolerant gegenüber Teildaten, unvollständigen Daten und Rauschen ist. Verwenden von Hough für einen Kreis: http://en.wikipedia.org/wiki/Hough_transform#Circle_detection_process

Angesichts der Tatsache, dass Ihr Kreis von Hand gezeichnet ist, denke ich, dass die Hough-Transformation gut zu Ihnen passt.

Hier ist eine "vereinfachte" Erklärung, ich entschuldige mich dafür, dass es nicht wirklich so einfach ist. Ein Großteil davon stammt aus einem Schulprojekt, das ich vor vielen Jahren durchgeführt habe.

Die Hough-Transformation ist ein Abstimmungsschema. Ein zweidimensionales Array von Ganzzahlen wird zugewiesen und alle Elemente werden auf Null gesetzt. Jedes Element entspricht einem einzelnen Pixel im zu analysierenden Bild. Dieses Array wird als Akkumulatorarray bezeichnet, da jedes Element Informationen und Stimmen akkumuliert, was auf die Möglichkeit hinweist, dass sich ein Pixel am Ursprung eines Kreises oder Bogens befindet.

Ein Gradientenoperator-Kantendetektor wird auf das Bild angewendet und Kantenpixel oder Kanten werden aufgezeichnet. Ein Rand ist ein Pixel, das in Bezug auf seine Nachbarn eine andere Intensität oder Farbe aufweist. Der Grad der Differenz wird als Gradientengröße bezeichnet. Für jede Kante mit ausreichender Größe wird ein Abstimmungsschema angewendet, das Elemente des Akkumulatorarrays inkrementiert. Die Elemente, die inkrementiert (gewählt) werden, entsprechen den möglichen Ursprüngen von Kreisen, die durch den betrachteten Rand verlaufen. Das gewünschte Ergebnis ist, dass wenn ein Bogen existiert, der wahre Ursprung mehr Stimmen erhält als der falsche Ursprung.

Es ist zu beachten, dass Elemente des Akkumulatorarrays, die zur Abstimmung besucht werden, einen Kreis um den betrachteten Rand bilden. Die Berechnung der zu stimmenden x, y-Koordinaten entspricht der Berechnung der x, y-Koordinaten eines Kreises, den Sie zeichnen.

In Ihrem handgezeichneten Bild können Sie möglicherweise die festgelegten (farbigen) Pixel direkt verwenden, anstatt Kanten zu berechnen.

Mit unvollständig angeordneten Pixeln erhalten Sie nicht unbedingt ein einzelnes Akkumulator-Array-Element mit der größten Anzahl von Stimmen. Möglicherweise erhalten Sie eine Sammlung benachbarter Array-Elemente mit einer Reihe von Stimmen, einen Cluster. Der Schwerpunkt dieses Clusters kann eine gute Annäherung für den Ursprung bieten.

Beachten Sie, dass Sie möglicherweise die Hough-Transformation für verschiedene Werte des Radius R ausführen müssen. Diejenige, die den dichteren Stimmencluster erzeugt, ist die "bessere" Anpassung.

Es gibt verschiedene Techniken, um Stimmen für falsche Ursprünge zu reduzieren. Ein Vorteil der Verwendung von Kanten ist beispielsweise, dass sie nicht nur eine Größe haben, sondern auch eine Richtung. Bei der Abstimmung müssen wir nur für mögliche Ursprünge in die entsprechende Richtung stimmen. Die Orte, die Stimmen erhalten, würden eher einen Bogen als einen vollständigen Kreis bilden.

Hier ist ein Beispiel. Wir beginnen mit einem Kreis mit dem Radius eins und einem initialisierten Akkumulatorarray. Da jedes Pixel als potenzielle Herkunft betrachtet wird, wird abgestimmt. Der wahre Ursprung erhält die meisten Stimmen, in diesem Fall vier.

.  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
Perpenso
quelle
5

Hier ist ein anderer Weg. Verwenden von UIView touchBegan, touchMoved, touchEnded und Hinzufügen von Punkten zu einem Array. Sie teilen das Array in zwei Hälften und testen, ob jeder Punkt in einem Array ungefähr den gleichen Durchmesser wie sein Gegenstück im anderen Array hat wie alle anderen Paare.

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

}

Das klingt okay? :) :)

dijipiji
quelle
3

Ich bin kein Experte für Formerkennung, aber hier ist, wie ich das Problem angehen könnte.

Während Sie den Pfad des Benutzers als Freihand anzeigen, sammeln Sie zunächst heimlich eine Liste von Punkt- (x, y) Abtastwerten zusammen mit den Zeiten. Sie können beide Fakten aus Ihren Drag-Ereignissen abrufen, sie in ein einfaches Modellobjekt einwickeln und diese in einem veränderlichen Array stapeln.

Sie möchten die Proben wahrscheinlich ziemlich häufig entnehmen - beispielsweise alle 0,1 Sekunden. Eine andere Möglichkeit wäre, wirklich anzufangen häufig , vielleicht alle 0,05 Sekunden, und zu beobachten, wie lange der Benutzer schleppt. Wenn sie länger als eine gewisse Zeit ziehen, senken Sie die Sample-Frequenz (und lassen Sie alle Samples fallen, die übersehen worden wären) auf etwa 0,2 Sekunden.

(Und nimm meine Zahlen nicht für das Evangelium, weil ich sie einfach aus meinem Hut gezogen habe. Experimentiere und finde bessere Werte.)

Zweitens analysieren Sie die Proben.

Sie möchten zwei Fakten ableiten. Erstens das Zentrum der Form, das (IIRC) nur der Durchschnitt aller Punkte sein sollte. Zweitens der durchschnittliche Radius jeder Probe von diesem Zentrum.

Wenn Sie, wie @ user1118321 vermutet, Polygone unterstützen möchten, besteht der Rest der Analyse darin, diese Entscheidung zu treffen: ob der Benutzer einen Kreis oder ein Polygon zeichnen möchte. Sie können die Beispiele zunächst als Polygon betrachten, um diese Bestimmung vorzunehmen.

Es gibt verschiedene Kriterien, die Sie verwenden können:

  • Zeit: Wenn der Benutzer an einigen Punkten länger schwebt als an anderen (die, wenn sich die Samples in einem konstanten Intervall befinden, als Cluster aufeinanderfolgender Samples im Raum nahe beieinander erscheinen), können dies Ecken sein. Sie sollten Ihre Eckschwelle klein machen, damit der Benutzer dies unbewusst tun kann, anstatt absichtlich an jeder Ecke pausieren zu müssen.
  • Winkel: Ein Kreis hat ungefähr den gleichen Winkel von einer Probe zur nächsten. Ein Polygon hat mehrere Winkel, die durch gerade Liniensegmente verbunden sind. Die Winkel sind die Ecken. Für ein reguläres Polygon (der Kreis zur Ellipse eines unregelmäßigen Polygons) sollten die Eckwinkel alle ungefähr gleich sein. Ein unregelmäßiges Polygon hat unterschiedliche Eckwinkel.
  • Intervall: Die Ecken eines regulären Polygons haben innerhalb der Winkelbemaßung den gleichen Abstand und der Radius ist konstant. Ein unregelmäßiges Polygon hat unregelmäßige Winkelintervalle und / oder einen nicht konstanten Radius.

Der dritte und letzte Schritt besteht darin, die Form, die auf dem zuvor bestimmten Mittelpunkt zentriert ist, mit dem zuvor bestimmten Radius zu erstellen.

Keine Garantie, dass alles, was ich oben gesagt habe, funktioniert oder effizient ist, aber ich hoffe, es bringt Sie zumindest auf den richtigen Weg - und bitte, wenn jemand, der mehr über Formerkennung weiß als ich (was ein sehr niedriger Balken ist), sieht Fühlen Sie sich frei, einen Kommentar oder Ihre eigene Antwort zu posten.

Peter Hosey
quelle
+1 Hallo, danke für die Eingabe. Sehr informativ. Ebenso wünsche ich mir, dass der iOS / "Formerkennungs" -Superman diesen Beitrag irgendwie sieht und uns weiter aufklärt.
Unheilig
1
@ Unheilig: Gute Idee. Getan.
Peter Hosey
1
Ihr Algorithmus klingt gut. Ich würde eine Überprüfung hinzufügen, wie weit der Pfad des Benutzers von einem perfekten Kreis / Polygon abweicht. (Beispiel: Prozent mittlere quadratische Abweichung.) Wenn sie zu groß ist, möchte der Benutzer möglicherweise nicht die ideale Form. Für einen erfahrenen Kritzler wäre der Cutoff kleiner als für einen schlampigen Kritzler. Dies würde es dem Programm ermöglichen, Künstlern künstlerische Freiheit zu geben, Anfängern jedoch viel Hilfe.
dmm
@ user2654818: Wie würden Sie das messen?
Peter Hosey
1
@PeterHosey: Erklärung für Kreise: Sobald Sie den idealen Kreis haben, haben Sie den Mittelpunkt und den Radius. Sie nehmen also jeden gezeichneten Punkt und berechnen seinen quadratischen Abstand vom Zentrum, der ((x-x0) ^ 2 + (y-y0) ^ 2) ist. Subtrahieren Sie das vom Quadrat des Radius. (Ich vermeide viele Quadratwurzeln, um die Berechnung zu speichern.) Nennen Sie das den quadratischen Fehler für einen gezeichneten Punkt. Den quadratischen Fehler für alle gezeichneten Punkte mitteln, dann quadratwurzeln und durch den Radius dividieren. Das ist Ihre durchschnittliche prozentuale Abweichung. (Die Mathematik / Statistik ist wahrscheinlich schreckenswürdig, aber es würde in der Praxis funktionieren.)
dmm
2

Ich hatte ziemlich viel Glück mit einem gut ausgebildeten 1-Dollar-Erkenner ( http://depts.washington.edu/aimgroup/proj/dollar/ ). Ich habe es für Kreise, Linien, Dreiecke und Quadrate verwendet.

Es war lange her, bevor UIGestureRecognizer, aber ich denke, es sollte einfach sein, richtige UIGestureRecognizer-Unterklassen zu erstellen.

Martin Adoue
quelle
2

Sobald Sie festgestellt haben, dass der Benutzer seine Form dort gezeichnet hat, wo er begonnen hat, können Sie eine Stichprobe der Koordinaten nehmen, durch die er gezeichnet hat, und versuchen, sie an einen Kreis anzupassen.

Hier gibt es eine MATLAB-Lösung für dieses Problem: http://www.mathworks.com.au/matlabcentral/fileexchange/15060-fitcircle-m

Was auf der Arbeit Least-Squares Fitting of Circles and Ellipses von Walter Gander, Gene H. Golub und Rolf Strebel basiert : http://www.emis.de/journals/BBMS/Bulletin/sup962/gander.pdf

Dr. Ian Coope von der University of Canterbury, Neuseeland, veröffentlichte einen Artikel mit der Zusammenfassung:

Das Problem der Bestimmung des Kreises der besten Anpassung an eine Menge von Punkten in der Ebene (oder die offensichtliche Verallgemeinerung auf n-Dimensionen) kann leicht als nichtlineares Problem der kleinsten Quadrate formuliert werden, das unter Verwendung eines Gauß-Newton-Minimierungsalgorithmus gelöst werden kann. Es zeigt sich, dass dieser unkomplizierte Ansatz ineffizient und äußerst empfindlich gegenüber Ausreißern ist. Eine alternative Formulierung ermöglicht es, das Problem auf ein lineares Problem der kleinsten Quadrate zu reduzieren, das trivial gelöst ist. Es wird gezeigt, dass der empfohlene Ansatz den zusätzlichen Vorteil hat, dass er gegenüber Ausreißern viel weniger empfindlich ist als der nichtlineare Ansatz der kleinsten Quadrate.

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

Die MATLAB-Datei kann sowohl das nichtlineare TLS- als auch das lineare LLS-Problem berechnen.

David Lawson
quelle
0

Hier ist eine ziemlich einfache Möglichkeit:

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

unter der Annahme dieses Matrixgitters:

 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

Platzieren Sie einige UIViews an den "X" -Positionen und testen Sie sie (nacheinander) auf Treffer. Wenn sie alle nacheinander getroffen werden, ist es meiner Meinung nach fair, den Benutzer sagen zu lassen: "Gut gemacht, Sie haben einen Kreis gezeichnet."

Klingt okay? (und einfach)

dijipiji
quelle
Hallo Zitrone. Gute Argumentation, aber im obigen Szenario bedeutet dies, dass wir 64 UIViews benötigen würden, um die Berührungen zu erkennen, oder? Und wie würden Sie die Größe für eine einzelne UIView definieren, wenn die Leinwand beispielsweise die Größe eines iPad hat? Wenn der Kreis klein ist und die Größe einer einzelnen UIView größer ist, können wir in diesem Fall die Reihenfolge nicht überprüfen, da alle gezeichneten Punkte innerhalb einer einzelnen UIView liegen würden.
Unheilig
Ja - dies funktioniert wahrscheinlich nur, wenn Sie die Leinwand auf etwa 300 x 300 fixieren und dann eine "Beispiel" -Leinwand mit der Kreisgröße daneben haben, die der Benutzer zeichnen soll. Wenn ja, würde ich mit 50x50 Quadraten * 6 gehen, müssen Sie auch nur die Ansichten rendern, die Sie an den richtigen Stellen
treffen möchten
@Unheilig: Genau das macht diese Lösung. Alles, was kreisförmig genug ist, um eine korrekte Abfolge von Ansichten zu durchlaufen (und Sie könnten möglicherweise eine maximale Anzahl von Umwegen für eine zusätzliche Neigung zulassen), wird als Kreis abgeglichen. Sie fangen es dann an einem perfekten Kreis ein, der in der Mitte all dieser Ansichten zentriert ist und dessen Radius alle (oder zumindest die meisten) von ihnen erreicht.
Peter Hosey
@PeterHosey Ok, lass mich versuchen, mich darum zu kümmern. Ich würde mich freuen, wenn einer von Ihnen Code bereitstellen könnte, um dies ins Rollen zu bringen. In der Zwischenzeit werde ich auch versuchen, mich darum zu kümmern, und danach werde ich dasselbe mit dem Codierungsteil tun. Vielen Dank.
Unheilig
Ich habe gerade einen anderen Weg für Sie eingereicht, den ich für besser
halte