Se più punti costituiscono un cerchio?

Question

Se ho per es. 20 punti, come posso verificare se quei punti compensano un cerchio? Non deve essere un cerchio perfetto.

Ad esempio se memorizzo le coordinate del mio mouse ogni 200 ms (mentre l'utente sposta il mouse), voglio vedere se l'utente fa un gesto circolare. E non posso aspettarmi che l'utente faccia un cerchio perfetto.

Answer 1

farei quanto segue;

• calcolare un best fit circle through the points
• Calcolare un residuo per ciascun punto (la distanza join dal centro al punto meno il migliore raggio del cerchio fit)
• accettare il risultato se una grande abbastanza percentuale dei residui erano sotto un certo valore definito come una piccola percentuale del raggio di adattamento ottimale. Questi parametri sarebbero criteri di accettazione definibili dall'utente.

Answer 2

Aggiornamento: con il suggerimento da @LastCoder per rilasciare punti consecutivi troppo vicini a quello precedente (ho impostato la soglia alla distanza di 10, forse può essere aumentato) e il livello di tolleranza impostato su 0,25 (es. Discrepanza di Il 25% dalla distanza media al punto centrale è accettabile), l'app che ho realizzato riconosce i miei "cerchi" in più della metà dei casi e non viene più ingannata dai quadrati. Quindi potrebbe non essere una cattiva idea, dopo tutto.

---

avrei trovato il centroid per il set data di punti, e verificare se la distanza dal baricentro per ogni punto è più o meno lo stesso (supponendo che ci si aspetta un'approssimazione del cerchio completo, non solo un arco).

Funziona in pratica per il problema di rilevare un gesto circolare eseguito con il mouse; vedi an example in C# (VS2010, solo la forma principale, il resto della app è boilerplate automatica; ignorare gli errori a Ideone) e uno screenshot per esso qui:

Answer 3

Ecco un metodo semplice, con un'implementazione funzionante che ho creato.

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

• Loop attraverso i punti
• Trova un secondo punto con la massima distanza dal primo
• Registra la distanza
• Una volta che avete tutte le distanze max loro media e calcolare la tolleranza di errore
• Controllare tutte le distanze registrate rispetto alla tolleranza di errore

Questo funziona perfettamente per l'input dell'utente come da un mouse o sensore tattile. Questo algoritmo è O (n^2) e utilizza la distanza massima delta anziché trovare il centro di massa e controllare le distanze dei raggi.

"sembra" essere più efficiente del metodo best-fit-circle che deve calcolare su ogni combinazione di 3 punti.

Questo trucchetto si avvantaggia del fatto che la distanza massima tra due punti su un cerchio corrisponde al diametro del cerchio.

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