Narysuj idealne koło za pomocą dotyku użytkownika

176

Mam ten projekt ćwiczeń, który pozwala użytkownikowi rysować na ekranie podczas dotykania palcami. Bardzo prosta aplikacja, którą zrobiłem jako ćwiczenie w przeszłości. Mój mały kuzyn pozwolił sobie rysować palcem za pomocą mojego iPada w tej aplikacji (rysunki dla dzieci: kółka, linie itp., Cokolwiek przyszło mu do głowy). Potem zaczął rysować koła, a potem poprosił mnie, żebym zrobił to „dobre koło” (z mojego rozumienia: spraw, aby narysowany okrąg był idealnie okrągły, ponieważ wiemy, jak stabilnie próbujemy narysować coś palcem na ekranie, okrąg nigdy nie jest tak zaokrąglony, jak powinien być).

Więc moje pytanie jest takie, czy jest jakiś sposób w kodzie, w którym możemy najpierw wykryć linię narysowaną przez użytkownika, która tworzy okrąg i generuje mniej więcej ten sam rozmiar koła, czyniąc go idealnie okrągłym na ekranie. Umiem zrobić niezbyt prostą linię prostą, ale jeśli chodzi o koło, nie bardzo wiem, jak to zrobić za pomocą kwarcu lub innych metod.

Moje rozumowanie jest takie, że punkt początkowy i końcowy linii muszą się stykać lub przecinać po tym, jak użytkownik podniesie palec, aby uzasadnić fakt, że faktycznie próbował narysować okrąg.

Unheilig
źródło
2
W tym scenariuszu może być trudno odróżnić okrąg od wielokąta. Co powiesz na „Narzędzie okręgu”, w którym użytkownik klika, aby zdefiniować środek lub jeden róg prostokąta ograniczającego, i przeciąga, aby zmienić promień lub ustawić przeciwległy róg?
user1118321
2
@ user1118321: To obala koncepcję możliwości narysowania koła i uzyskania idealnego koła. W idealnym przypadku aplikacja powinna rozpoznać na podstawie samego rysunku użytkownika, czy użytkownik narysował okrąg (mniej więcej), elipsę czy wielokąt. (Poza tym wielokąty mogą nie być objęte zakresem tej aplikacji - mogą to być tylko okręgi lub linie).
Peter Hosey,
Jak myślisz, na którą odpowiedź powinienem przyznać nagrodę? Widzę wielu dobrych kandydatów.
Peter Hosey
@Unheilig: Nie mam żadnej wiedzy na ten temat, poza rodzącym się zrozumieniem trig. To powiedziawszy, odpowiedzi, które pokazują mi największy potencjał to stackoverflow.com/a/19071980/30461 , stackoverflow.com/a/19055873/30461 , stackoverflow.com/a/18995771/30461 , może stackoverflow.com/a/ 18992200/30461 i moje własne. To są te, które spróbuję najpierw. Rozkaz pozostawiam tobie.
Peter Hosey,
1
@Gene: Być może mógłbyś w odpowiedzi podsumować istotne informacje i podać link do dodatkowych szczegółów.
Peter Hosey

Odpowiedzi:

381

Czasami naprawdę warto poświęcić trochę czasu na wymyślenie koła na nowo. Jak być może zauważyłeś, istnieje wiele frameworków, ale nie jest tak trudno wdrożyć proste, ale użyteczne rozwiązanie bez wprowadzania całej złożoności. (Proszę, nie zrozumcie mnie źle, dla każdego poważnego celu lepiej jest użyć dojrzałej i sprawdzonej, stabilnej platformy).

Najpierw przedstawię moje wyniki, a następnie wyjaśnię prostą i prostą ideę, która się za nimi kryje.

wprowadź opis obrazu tutaj

Zobaczysz, że w mojej realizacji nie ma potrzeby analizowania każdego punktu i wykonywania skomplikowanych obliczeń. Chodzi o to, aby znaleźć cenne metainformacje. Będzie używać styczną jak np

wprowadź opis obrazu tutaj

Określmy prosty i nieskomplikowany wzór, typowy dla wybranego kształtu:

wprowadź opis obrazu tutaj

Dlatego nie jest trudno wdrożyć mechanizm wykrywania koła w oparciu o ten pomysł. Zobacz działające demo poniżej (przepraszam, używam Javy jako najszybszego sposobu na przedstawienie tego szybkiego i nieco brudnego przykładu):

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

Wdrożenie podobnego zachowania na iOS nie powinno stanowić problemu, ponieważ potrzebujesz tylko kilku zdarzeń i współrzędnych. Coś podobnego do następującego (patrz przykład ):

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

Istnieje kilka możliwych ulepszeń.

Zacznij w dowolnym momencie

Aktualnym wymaganiem jest rozpoczęcie rysowania okręgu od górnego środkowego punktu ze względu na następujące uproszczenie:

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

Zwróć uwagę, że indexużywana jest domyślna wartość . Proste przeszukiwanie dostępnych „części” kształtu usunie to ograniczenie. Pamiętaj, że aby wykryć pełny kształt, musisz użyć okrągłego bufora:

wprowadź opis obrazu tutaj

Zgodnie z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara

Aby obsługiwać oba tryby, będziesz musiał użyć okrągłego bufora z poprzedniego rozszerzenia i przeszukiwać w obu kierunkach:

wprowadź opis obrazu tutaj

Narysuj elipsę

Masz już wszystko, czego potrzebujesz w boundstablicy.

wprowadź opis obrazu tutaj

Po prostu użyj tych danych:

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

Inne gesty (opcjonalnie)

Na koniec wystarczy odpowiednio poradzić sobie z sytuacją, gdy dx(lub dy) jest równe zero, aby obsługiwać inne gesty:

wprowadź opis obrazu tutaj

Aktualizacja

Ten mały dokument PoC wzbudził dość duże zainteresowanie, więc zaktualizowałem nieco kod, aby działał płynnie i zawierał wskazówki dotyczące rysowania, wyróżnienia punktów pomocniczych itp.:

wprowadź opis obrazu tutaj

Oto kod:

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
źródło
76
Spektakularna odpowiedź Renat. Jasny opis podejścia, obrazy dokumentujące proces, animacje. Wydaje się również najbardziej uogólnionym, solidnym rozwiązaniem. Styczne brzmią jak naprawdę sprytny pomysł - podobnie jak początkowe (obecne?) Techniki rozpoznawania pisma ręcznego. Pytanie dodane do zakładek ze względu na tę odpowiedź. :)
enhzflep
27
Bardziej ogólnie: zwięzłe, zrozumiałe wyjaśnienie ORAZ diagramy ORAZ animowane demo ORAZ kod ORAZ odmiany? To idealna odpowiedź na przepełnienie stosu.
Peter Hosey
11
To taka dobra odpowiedź, prawie wybaczam, że robi grafikę komputerową w Javie! ;)
Nicolas Miari
4
Czy będą jakieś zaskakujące aktualizacje (tj. Więcej kształtów itp.) Na te Święta, Święty Renacie? :-)
Unheilig
1
Łał. Tour de force.
Wogsland
14

Klasyczną techniką widzenia komputerowego do wykrywania kształtu jest transformacja Hougha. Jedną z fajnych rzeczy w Transformacie Hougha jest to, że jest bardzo odporny na częściowe dane, niedoskonałe dane i szum. Używanie Hough dla kręgu: http://en.wikipedia.org/wiki/Hough_transform#Circle_detection_process

Biorąc pod uwagę, że twój okrąg jest narysowany ręcznie, myślę, że transformacja Hough może być dla ciebie dobrym dopasowaniem.

Oto „uproszczone” wyjaśnienie, przepraszam, że nie jest takie proste. Wiele z tego pochodzi z projektu szkolnego, który zrobiłem wiele lat temu.

Transformacja Hougha to schemat głosowania. Dwuwymiarowa tablica liczb całkowitych jest przydzielana, a wszystkie elementy są ustawiane na zero. Każdy element odpowiada pojedynczemu pikselowi w analizowanym obrazie. Ta tablica jest nazywana tablicą akumulatorów, ponieważ każdy element będzie gromadził informacje, głosy, wskazujące na możliwość, że piksel może znajdować się na początku okręgu lub łuku.

Do obrazu stosuje się detektor krawędzi operatora gradientu, a piksele krawędzi lub krawędzie są rejestrowane. Krawędź to piksel, który ma inną intensywność lub kolor w porównaniu z sąsiadami. Stopień różnicy nazywany jest wielkością gradientu. Dla każdego obrzeża o dostatecznej wielkości stosowany jest schemat głosowania, który zwiększy elementy tablicy akumulatorów. Elementy, które są zwiększane (na które głosowano) odpowiadają możliwemu pochodzeniu okręgów przechodzących przez rozważany obrzeże. Pożądanym rezultatem jest to, że jeśli łuk istnieje, to prawdziwe pochodzenie otrzyma więcej głosów niż fałszywe pochodzenie.

Zwróć uwagę, że elementy zestawu akumulatorów odwiedzane w celu głosowania tworzą okrąg wokół rozważanego krawędzi. Obliczanie współrzędnych x, y, na które chcesz głosować, jest tym samym, co obliczanie współrzędnych x, y okręgu, który rysujesz.

Na swoim ręcznie narysowanym obrazie możesz być w stanie bezpośrednio użyć zestawu (kolorowych) pikseli zamiast obliczać krawędzie.

Teraz z niedokładnie zlokalizowanymi pikselami niekoniecznie otrzymasz pojedynczy element tablicy akumulatorów z największą liczbą głosów. Możesz otrzymać kolekcję sąsiednich elementów tablicy z kilkoma głosami, klaster. Środek ciężkości tej gromady może stanowić dobre przybliżenie pochodzenia.

Zauważ, że być może będziesz musiał uruchomić transformatę Hough dla różnych wartości promienia R. Tym, który tworzy gęstszą grupę głosów, jest „lepsze” dopasowanie.

Istnieją różne techniki zmniejszania liczby głosów za fałszywe pochodzenie. Na przykład jedną z zalet używania obrzeży jest to, że mają nie tylko wielkość, ale także kierunek. Podczas głosowania wystarczy tylko głosować na ewentualne pochodzenie w odpowiednim kierunku. Lokalizacje otrzymujące głosy utworzyłyby raczej łuk niż pełne koło.

Oto przykład. Zaczynamy od koła o promieniu jeden i zainicjalizowanej tablicy akumulatorów. Ponieważ każdy piksel jest rozpatrywany, głosowane są na potencjalne źródła. Prawdziwe pochodzenie otrzymuje najwięcej głosów, w tym przypadku cztery.

.  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
źródło
5

Oto inny sposób. Korzystanie z UIView touchBegan, touchesMoved, touchesEnded i dodawania punktów do tablicy. Dzielisz tablicę na połówki i sprawdzasz, czy każdy punkt w jednej tablicy ma mniej więcej taką samą średnicę jak jego odpowiednik w drugiej tablicy, co wszystkie inne pary.

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

}

Ten dźwięk w porządku? :)

dijipiji
źródło
3

Nie jestem ekspertem w rozpoznawaniu kształtów, ale oto jak mogę podejść do problemu.

Po pierwsze, wyświetlając ścieżkę użytkownika jako odręczną, potajemnie zbierz listę próbek punktowych (x, y) wraz z czasami. Możesz pobrać oba fakty ze zdarzeń przeciągania, zawinąć je w prosty obiekt modelu i ułożyć je w zmiennej tablicy.

Prawdopodobnie chcesz pobierać próbki dość często - powiedzmy co 0,1 sekundy. Inną możliwością byłoby rozpoczynanie pracy bardzo często, może co 0,05 sekundy, i obserwowanie, jak długo użytkownik się przeciąga; jeśli przeciągają się dłużej niż jakiś czas, zmniejsz częstotliwość próbkowania (i upuść wszystkie próbki, które zostałyby pominięte) do około 0,2 sekundy.

(I nie bierz moich liczb do ewangelii, ponieważ właśnie wyciągnąłem je z kapelusza. Eksperymentuj i znajduj lepsze wartości.)

Po drugie, przeanalizuj próbki.

Będziesz chciał wyprowadzić dwa fakty. Po pierwsze, środek kształtu, który (IIRC) powinien być średnią wszystkich punktów. Po drugie, średni promień każdej próbki z tego środka.

Jeśli, jak domyślił się @ user1118321, chcesz obsługiwać wielokąty, to reszta analizy polega na podjęciu decyzji: czy użytkownik chce narysować okrąg, czy wielokąt. Na początek możesz spojrzeć na próbki jako wielokąt, aby to określić.

Istnieje kilka kryteriów, których możesz użyć:

  • Czas: Jeśli użytkownik unosi się dłużej w niektórych punktach niż inne (które, jeśli próbki są w stałych odstępach, pojawią się jako skupisko kolejnych próbek blisko siebie w przestrzeni), mogą to być narożniki. Powinieneś zmniejszyć próg narożny, aby użytkownik mógł to zrobić nieświadomie, zamiast celowo zatrzymywać się na każdym rogu.
  • Kąt: koło będzie miało mniej więcej taki sam kąt od jednej próbki do drugiej na całym obwodzie. Wielokąt będzie miał kilka kątów połączonych odcinkami prostymi; kąty to rogi. W przypadku wielokąta regularnego (od koła do elipsy wielokąta nieregularnego) kąty narożników powinny być mniej więcej takie same; nieregularny wielokąt będzie miał różne kąty naroża.
  • Interwał: Rogi regularnego wielokąta będą w równych odstępach w wymiarze kątowym, a promień będzie stały. Nieregularny wielokąt będzie miał nieregularne odstępy kątowe i / lub zmienny promień.

Trzecim i ostatnim krokiem jest utworzenie kształtu, wyśrodkowanego na wcześniej ustalonym punkcie środkowym, z uprzednio określonym promieniem.

Nie ma gwarancji, że wszystko, co powiedziałem powyżej, będzie działać lub będzie wydajne, ale mam nadzieję, że przynajmniej zaprowadzi Cię na właściwą ścieżkę - i proszę, jeśli ktoś, kto wie więcej o rozpoznawaniu kształtów niż ja (co jest bardzo niską poprzeczką), zobaczy to, nie krępuj się opublikować komentarz lub własną odpowiedź.

Peter Hosey
źródło
+1 Cześć, dzięki za wkład. Bardzo informujące. Chciałbym również, aby superman iOS / „rozpoznawanie kształtów” jakoś zobaczył ten post i oświecił nas dalej.
Unheilig
1
@Unheilig: Dobry pomysł. Gotowe.
Peter Hosey
1
Twój algorytm brzmi dobrze. Dodałbym sprawdzenie, jak daleko ścieżka użytkownika odbiegała od idealnego koła / wielokąta. (Na przykład, średnie odchylenie kwadratowe w procentach). Jeśli jest zbyt duże, użytkownik może nie chcieć idealnego kształtu. Dla wprawnego doodlera odcięcie byłoby mniejsze niż dla niechlujnego doodlera. Mając to pozwoliłoby programowi dać artystyczną wolność artystom, ale dużą pomoc dla początkujących.
dmm,
@ user2654818: Jak byś to zmierzył?
Peter Hosey
1
@PeterHosey: Wyjaśnienie dotyczące okręgów: Kiedy masz idealny okrąg, masz środek i promień. Więc bierzesz każdy narysowany punkt i obliczasz jego kwadratową odległość od środka, która wynosi ((x-x0) ^ 2 + (y-y0) ^ 2). Odejmij to od promienia do kwadratu. (Unikam wielu pierwiastków kwadratowych, aby zaoszczędzić obliczenia). Nazwijmy to błędem kwadratu dla narysowanego punktu. Uśrednij kwadrat błędu dla wszystkich narysowanych punktów, następnie pierwiastek kwadratowy, a następnie podziel przez promień. To twoja średnia procentowa dywergencja. (Matematyka / statystyki są prawdopodobnie godne uwagi, ale w praktyce
sprawdzą się
2

Miałem sporo szczęścia z odpowiednio wyszkolonym narzędziem rozpoznającym 1 USD ( http://depts.washington.edu/aimgroup/proj/dollar/ ). Użyłem go do okręgów, linii, trójkątów i kwadratów.

To było dawno temu, zanim UIGestureRecognizer, ale myślę, że powinno być łatwo stworzyć odpowiednie podklasy UIGestureRecognizer.

Martin Adoue
źródło
2

Gdy określisz, że użytkownik skończył rysować swój kształt w miejscu, w którym zaczął, możesz pobrać próbkę współrzędnych, przez które narysował, i spróbować dopasować je do koła.

Jest tutaj rozwiązanie tego problemu MATLAB: http://www.mathworks.com.au/matlabcentral/fileexchange/15060-fitcircle-m

Który jest oparty na artykule Dopasowanie kół i elips metodą najmniejszych kwadratów autorstwa Waltera Gandera, Gene H. Goluba i Rolfa Strebela: http://www.emis.de/journals/BBMS/Bulletin/sup962/gander.pdf

Dr Ian Coope z University of Canterbury w Nowej Zelandii opublikował artykuł zawierający streszczenie:

Problem określenia okręgu najlepszego dopasowania do zbioru punktów na płaszczyźnie (lub oczywiste uogólnienie do n-wymiarów) można łatwo sformułować jako nieliniowy całkowity problem najmniejszych kwadratów, który można rozwiązać za pomocą algorytmu minimalizacji Gaussa-Newtona. Okazuje się, że to proste podejście jest nieefektywne i niezwykle wrażliwe na obecność wartości odstających. Alternatywne sformułowanie pozwala zredukować problem do liniowego problemu najmniejszych kwadratów, który jest trywialnie rozwiązany. Wykazano, że zalecane podejście ma tę dodatkową zaletę, że jest znacznie mniej wrażliwe na wartości odstające niż nieliniowe podejście najmniejszych kwadratów.

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

Plik MATLAB może obliczyć zarówno problem nieliniowego TLS, jak i liniowego LLS.

David Lawson
źródło
0

Oto dość prosty sposób użycia:

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

zakładając tę ​​siatkę macierzową:

 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

Umieść kilka UIVview w miejscach „X” i przetestuj je pod kątem trafienia (po kolei). Jeśli wszystkie zostaną trafione w kolejności, myślę, że uczciwe byłoby pozwolenie użytkownikowi powiedzieć „Dobra robota, narysowałeś okrąg”

Brzmi dobrze? (i proste)

dijipiji
źródło
Cześć, Lemon. Dobre rozumowanie, ale w powyższym scenariuszu oznacza to, że musielibyśmy mieć 64 UIViews, aby wykryć dotknięcia, prawda? A jak zdefiniowałbyś rozmiar jednego UIView, jeśli płótno ma rozmiar na przykład iPada? Wydaje się, że jeśli okrąg jest mały, a rozmiar pojedynczego UIView jest większy, w tym przypadku nie moglibyśmy sprawdzić sekwencji, ponieważ wszystkie narysowane punkty znajdowałyby się w jednym UIView.
Unheilig
Tak - ten prawdopodobnie działa tylko wtedy, gdy przymocujesz płótno do czegoś w rodzaju 300x300, a następnie masz obok niego płótno „przykładowe” z rozmiarem koła, które użytkownik ma narysować. Jeśli tak, wybrałbym 50x50 kwadratów * 6, musisz również wyrenderować tylko widoki, które chcesz trafić w odpowiednich lokalizacjach, a nie wszystkie 6 * 6 (36) lub 8 * 8 (64)
dijipiji
@Unheilig: Właśnie to robi to rozwiązanie. Wszystko, co jest wystarczająco okrągłe, aby przejść przez prawidłową sekwencję widoków (i potencjalnie możesz pozwolić na maksymalną liczbę objazdów w celu uzyskania dodatkowego slopu), będzie pasowało jako okrąg. Następnie przyciągasz go do idealnego koła pośrodku wszystkich tych widoków, którego promień sięga wszystkich (lub przynajmniej większości) z nich.
Peter Hosey
@PeterHosey Ok, spróbuję to obejść. Byłbym wdzięczny, gdyby którykolwiek z was mógł dostarczyć kod, aby to uruchomić. W międzyczasie spróbuję to obejść, a potem zrobię to samo z częścią kodującą. Dzięki.
Unheilig
Właśnie przedstawiłem dla Ciebie inny sposób, który moim zdaniem może być lepszy
dijipiji