Si j'ai par exemple 20 points, comment puis-je vérifier si ces points compensent un cercle? Cela ne doit pas être un cercle parfait.
Par exemple, si je stocke les coordonnées de ma souris tous les 200ms (comme l'utilisateur déplace la souris), je veux voir si l'utilisateur fait un geste de cercle. Et je ne peux pas m'attendre à ce que l'utilisateur fait un cercle parfait.
3 Réponses :
mise à jour: avec la suggestion de @LastCoder pour déposer des points consécutifs trop près de la précédente (je définirai le seuil sur la distance de 10; peut-être peut-être être augmenté) et le niveau de tolérance réglé sur 0,25 (c.-à-d. Distance de 25 % de la distance moyenne du point central est acceptable), l'application que j'ai faite reconnaît mes "cercles" dans plus de demi-cas et n'est plus trompé par des carrés. Alors pourrait ne pas être une mauvaise idée, après tout.
Je trouverais le Centroid pour l'ensemble de points donné et vérifier si La distance entre le Centroid à chaque point est plus ou moins la même (supposant que vous vous attendez à une approximation du cercle complet, pas seulement d'un arc).
Cela fonctionne pour moi dans la pratique pour le problème de la détection d'un geste de cercle effectué avec la souris; Voir Un exemple en C # (VS2010, la forme principale uniquement, le reste de l'application est un plaque automatique automatique; ignorer les erreurs à Ideone) et une capture d'écran pour cela ici:
+1. N'oubliez pas que la déviation radiale doit être proportionnelle au rayon, ou vous finissez par détecter un non-mouvement en cercle. Cet algorithme peut être implémenté efficacement comme algorithme en ligne, où le score de circularité est recalculé car de nouveaux échantillons arrivent.
Cela se brisera si les points ne sont pas uniformément dispensés autour du cercle entier, tirant le centre de la centrale du centre du cercle.
@ Rafałdowgird & Autres: Je suis d'accord, mais pour le problème de la détection de geste de la souris, on peut s'attendre à ce que des points soient dispensés assez uniformément; et il est confirmé avec l'expérience (voir la réponse mise à jour) :)
Performance sage, cela semble être l'estimation la plus efficace. Pour rendre le Centroid plus précis, vous pouvez éliminer les points consécutifs si la distance est trop proche de l'autre (pour la détection de geste, cela pourrait être calibré assez facilement et retirer le poids supplémentaire causé en se déplaçant lentement dans une partie du cercle mais non L'autre).
@LastCoder: Merci pour la suggestion, une bonne idée d'essayer. Le problème est arrivé intéressant et amusant, ouais? :)
+1 Pour la mise en œuvre, les tests, revenir avec vos résultats et démontrer tout cela fonctionne. Bien joué!
Je ferais ce qui suit;
C'est probablement la méthode la plus correcte, mais cela semble être une entreprise de la mettre en œuvre dans le code. Il serait probablement toujours assez rapide pour la reconnaissance de geste en temps réel en fonction du nombre de points.
Il serait probablement préférable d'utiliser l_1 ajustement, car cela est moins sensible aux valeurs aberrantes. Une autre possibilité est l'ajustement L_∞ (minimum annulus), où le test pourrait être basé sur le rapport de la largeur des annulus au rayon moyen. Il y a une belle enquête sur algorithmes de montage de cercle ici , avec des liens vers le code et d'autres ressources. Une recherche sur le Web pour L1 Circle Fitting présente beaucoup de ressources pour les algorithmes L_1 et L_∞.
@Té, merci beaucoup pour le lien, très utile. J'ai eu la seule question des points-volants dans le passé.
@LastCoder, j'utilise quelque chose de très similaire à celui-ci pour un logiciel de modélisation que je développe, et il est assez rapide pour la mise à jour en temps réel du cercle lorsque la souris se déplace sur une solution de bureau C ++. La performance pourrait devenir un problème sur une plate-forme basculée inférieure (par exemple mobile) sur une langue plus lente. Remarque Il existe de nombreuses optimisations simples telles que la comparaison des distances <, ==, vous pouvez laisser tomber la racine carrée.
Voici une méthode simple, avec une mise en œuvre de travail que j'ai jeté ensemble.
http://jsfiddle.net.net / kbsdw / 29 /
Cela fonctionne bien pour l'utilisateur de l'utilisateur comme à partir d'une souris ou d'un capteur tactile. Cet algorithme est O (n ^ 2) et utilise la distance de Delta Max par opposition à la recherche du centre de masse et de vérifier les distances de rayon.
Il "semble" être plus efficace que le meilleur cercle méthode qui doit calculer sur chaque combinaison de 3 points.
Ce hack ~ algo tire parti du fait que la distance maximale entre deux points sur un cercle est le diamètre du cercle. < Pré> xxx
+1. Mais math.abs (avgdistance - poids [i])> ErrorConstraint est trop simpliste. Pensez à quelqu'un qui commence au milieu du cercle. Vous avez besoin d'une majorité de points en vérifiant cela. Donc 2 paramètres.
@Umnyobe - c'est pourquoi il renvoie de faux dans ces cas et ne renvoie que vrais si "toutes" des longueurs se situe dans la tolérance. Vous pouvez également effectuer un certain traitement supplémentaire au tableau des poids et enlever les valeurs aberrantes, mais je ne l'ai pas fait dans le simple exemple, Jsfiddle.
J'ai joué un peu avec votre mise en œuvre. Même avec le niveau de tolérance défini sur 0,15, il peut envisager un carré et même un triangle (si près d'équilatéral) en cercle :)
@Alexey. Les faux négatifs existeront toujours. C'est la reconnaissance de modèle. Sauf s'il veut aussi commencer à reconnaître les carrés, cela est déjà solide.
@Alexy, quatre points sur les coins d'un carré ou de tout triangle sont co-circulaires. Serait-il échouer pour un plus grand nombre de points sur la même géométrie? Je ne le pense pas, comme vous avez des distances plus variées impliquées.
Pourriez-vous être plus précis dans ce que vous essayez d'accomplir?
Je continuerai sur la déclaration de Don Roby - "Qu'est-ce qu'un cercle imparfait". Supposons que vous échantillonniez un cercle parfait en 4 points. Supposons que ces points sont: à partir de 45 degrés. et tournant autour du cercle de 90 degrés. Cela vous donnera 4 points qui sont situés exactement où ils devraient être pour un cercle parfait. Mais si vous dessinez ces 4 points, vous finirez par dessiner un rectangle à la place. Est-ce un cercle imparfait ou parfait?
@Brano, je prends un cercle imparfait comme un ensemble de points co-circulaires à une tolérance déclarée. par exemple. Si vous créez un cercle le mieux adapté à travers les points et que 85% des points se trouvent dans une distance de 20% du rayon du cercle d'ajustement, vous avez un "cercle imparfait" de types. Remarque Vous avez besoin de quatre points ou plus pour commencer et vous devez accorder vos critères d'acceptation pour différentes applications et peut-être des utilisateurs.
Je ne sais pas pourquoi cette question était fermée. Changer éventuellement le terme "constituer un cercle" à "co-circulaire" éliminerait l'ambiguïté.