Si varios puntos compensan un círculo?

Question

Si tengo, por ejemplo, 20 puntos, ¿cómo puedo verificar si esos puntos constituyen un círculo? No tiene que ser un círculo perfecto.

Por ejemplo, si almaceno las coordenadas de mi mouse cada 200ms (mientras el usuario mueve el mouse), quiero ver si el usuario hace un gesto de círculo. Y no puedo esperar que el usuario haga un círculo perfecto.

Answer 1

me gustaría hacer la siguiente;

• Compute un best fit circle through the points
• Calcular un residual para cada punto (la distancia unirse desde el centro hasta el punto menos la mejor radio del círculo ajuste)
• aceptar el resultado si un gran porcentaje suficiente de los residuos eran debajo de un cierto valor definido como un pequeño porcentaje del radio de mejor ajuste. Estos parámetros serían criterios de aceptación definibles por el usuario.

Answer 2

Actualización: con la sugerencia de @LastCoder para eliminar puntos consecutivos demasiado cerca de la anterior (establezco el umbral en la distancia de 10, tal vez se puede aumentar) y el nivel de tolerancia establecido en 0,25 (es decir, discrepancia de El 25% de la distancia promedio al punto central es aceptable), la aplicación que hice reconoce mis "círculos" en más de la mitad de los casos, y ya no me engañan los cuadrados. Entonces, puede que no sea una mala idea, después de todo.

---

que iba a encontrar la centroid para el conjunto dado de puntos, y comprobar si la distancia desde el centroide de cada punto es más o menos lo mismo (suponiendo que se espera una aproximación al punto de partida, no sólo una arco).

Funciona para mí en la práctica por el problema de detectar un gesto de círculo hecho con el mouse; ver an example in C# (VS2010, sólo la forma principal, el resto de la aplicación es repetitivo automático; ignorar los errores en Ideone) y una captura de pantalla aquí:

Answer 3

Aquí hay un método simple, con una implementación de trabajo que lancé.

http://jsfiddle.net/kBsdW/29/

• bucle a través de los puntos
• Encuentra un segundo punto con la distancia máxima desde el primer
• Registre la distancia
• Una vez que tenga todas las distancias Max los promedio y calcular la tolerancia de error
• Compruebe todas las distancias registradas contra su tolerancia de error

Esto funciona muy bien para la entrada del usuario, como un mouse o un sensor táctil. Este algoritmo es O (n^2) y utiliza la distancia máxima delta en lugar de encontrar el centro de masa y verificar distancias de radios.

"Parece" ser más eficiente que el método del mejor círculo que debe calcularse en cada combinación de 3 puntos.

Este truco ~ algo aprovecha el hecho de que la distancia máxima entre dos puntos en un círculo es el diámetro del círculo.

function isCircle(points, error) { 
    if(points.length <= 2) return true; 
    var weights = []; 
    var maxDistance = 0; 
    var sumDistance = 0; 
    var avgDistance = 0; 
    var errorConstraint = 0; 
    for(var i=0; i<points.length; i++) { 
     var distance = 0; 
     for(var j=0; j<points.length; j++) { 
      var d = getDistance(points[i], points[j]); 
      if(d > distance) { 
       distance = d; 
      } 
     } 
     if(distance > 0) { 
      if(distance > maxDistance) maxDistance = distance; 
      sumDistance += distance; 
      weights.push(distance); 
     } 
    } 
    avgDistance = sumDistance/weights.length; 
    errorConstraint = error * avgDistance; 
    for(var i=0; i<weights.length; i++) { 
     if(Math.abs(avgDistance - weights[i]) > errorConstraint) { 
      return false; 
     } 
    } 
    return true; 
}