Czy wiele punktów składa się na okrąg?

Question

Jeśli mam np. 20 punktów, jak mogę sprawdzić, czy te punkty składają się na okrąg? To nie musi być idealne koło.

Na przykład, jeśli przechowuję współrzędne mojej myszy co 200 ms (gdy użytkownik przesuwa mysz), chcę sprawdzić, czy użytkownik wykonuje gest okrężny. I nie mogę oczekiwać, że użytkownik zrobi idealne koło.

Answer 1

zrobiłbym następujące;

• obliczyć best fit circle through the points
• obliczyć pozostały na każdy punkt (odległość przyłączyć od środka do punktu minus najlepiej promienia okręgu Fit)
• zaakceptować wyników, jeśli dostatecznie duża część reszt były poniżej pewnej wartości zdefiniowanej jako niewielki procent najlepiej dopasowanego promienia. Te parametry będą definiowanymi przez użytkownika kryteriami akceptacji.

Answer 2

Aktualizacja: z sugestią @LastCoder, aby upuścić kolejne punkty zbyt blisko poprzedniej (ustawiam próg w odległości 10, być może można go zwiększyć) i poziom tolerancji ustawiony na 0.25 (czyli rozbieżność 25% od średniej odległości do punktu środkowego jest dopuszczalne), aplikacja, którą utworzyłem, rozpoznaje moje "okręgi" w ponad połowie przypadków i nie jest już oszukiwana przez kwadraty. Więc może nie jest to zły pomysł.

---

znajdę centroid dla danego zbioru punktów, i sprawdzić, czy odległość od środka ciężkości do każdego punktu jest mniej więcej taka sama (przy założeniu, że można oczekiwać przybliżenie pełne koło, a nie tylko łuk).

W praktyce sprawdza się w przypadku wykrycia gestu wykonanego za pomocą myszy; zobacz an example in C# (VS2010, tylko główną formą, reszta aplikacji jest automatyczne boilerplate; ignorować błędy w ideone) i zrzut ekranu dla tutaj:

Answer 3

Oto prosta metoda, z działającą implementacją, którą zrzuciłem razem.

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

• Loop przez punkty
• Znajdź drugi punkt z maksymalną odległością od pierwszego
• Record od odległości
• Kiedy masz wszystkie Maxa odległościach uśrednić je i obliczyć tolerancja błędu:
• Sprawdź wszystkie zarejestrowane dystanse na podstawie tolerancji błędów

Działa to doskonale do wprowadzania danych przez użytkownika, jak z myszy lub czujnika dotykowego. Algorytm ten ma postać O (n^2) i wykorzystuje deltowy dystans maksymalny w przeciwieństwie do znajdowania środka masy i sprawdzania odległości promieni.

"Wydaje się" być bardziej wydajnym niż metoda najlepszego dopasowania, która musi obliczyć przy każdej kombinacji 3 punktów.

Ten hack ~ algo wykorzystuje fakt, że maksymalna odległość między dwoma punktami na okręgu to średnica okręgu.

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