Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Whether multiple points make up for a circle? [closed]

If I have e.g. 20 points, how can i check to see if those points make up for a circle? It doesnt have to be a perfect circle.

For example if I store the coordinates of my mouse every 200ms (as the user moves the mouse), I want to see if the user makes a circle gesture. And I cant expect the user to make a perfect circle.

like image 896
Afra Avatar asked Jan 30 '12 12:01

Afra


People also ask

Can any 3 points form a circle?

A circle is defined by any three non-collinear points. This means that, given any three points that are not on the same line, you can draw a circle that passes through them. It is possible to construct this circle using only a compass and straightedge.

How many points make up a circle?

Three points uniquely define a circle. If you circumscribe a circle around a triangle, the circumcenter of that triangle will also be the center of that circle. Created by Sal Khan.

Are circles made of points?

A circle is all points in the same plane that lie at an equal distance from a center point. The circle is only composed of the points on the border. You could think of a circle as a hula hoop. It's only the points on the border that are the circle.

Can we draw circle with 4 points?

If a circle can be drawn through four points, the quadrilateral they make is called cyclic.


3 Answers

I'd do the following;

  • Compute a best fit circle through the points
  • Calculate a residual for each point (the join distance from the centre to the point minus the best fit circle radius)
  • Accept the result if a large enough percentage of the residuals were below a certain value defined as a small percentage of the best fit radius. These parameters would be user definable acceptance criteria.
like image 99
SmacL Avatar answered Nov 08 '22 14:11

SmacL


Update: with the suggestion from @LastCoder to drop consecutive points too close to the previous one (I set the threshold at the distance of 10; perhaps it can be increased) and the tolerance level set to 0.25 (i.e. discrepancy of 25% from the average distance to the centre point is acceptable), the app I made recognizes my "circles" in more than half cases, and is not deceived by squares anymore. So might be not a bad idea, after all.


I would find the centroid for the given set of points, and check if the distance from the centroid to each point is more or less the same (assuming that you expect an approximation of full circle, not just an arc).

It works for me in practice for the problem of detecting a circle gesture done with mouse; see an example in C# (VS2010, the main form only, the rest of app is automatic boilerplate; ignore the errors at ideone) and a screenshot for it here:

Certainly I am bad at drawing circles with laptop's touch-stick

like image 20
Alexey Kukanov Avatar answered Nov 08 '22 12:11

Alexey Kukanov


Here's a simple method, with a working implementation I threw together.

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

  • Loop through the points
  • Find a second point with the maximum distance from the first
  • Record the distance
  • Once you have all of the max distances average them and calculate the error tolerance
  • Check all your recorded distances against your error tolerance

This works great for user input like from a mouse or touch sensor. This algorithm is O(n^2) and uses the delta max distance as opposed to finding the center of mass and checking radii distances.

It "seems" to be more efficient than the best-fit-circle method which has to calculate on every combination of 3 points.

This hack~algo takes advantage of the fact that the maximum distance between two points on a circle is the diameter of the circle.

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;
}
like image 31
Louis Ricci Avatar answered Nov 08 '22 14:11

Louis Ricci