Check if a 2D Point lies on a given Arc or not

Hi,

I have set of 2D Points ,which represent an Arc.

I would like to know if a certain 2D Point lies on this arc or not (with some tolerance).

My 2D Points representing the arc are as follows:

0 0
0.00510736 0.0485933
0.00851245 0.0809906
0.0119173 0.113385
0.0153224 0.145782
0.0187272 0.178177
0.0400463 0.225069
0.0775509 0.270257
0.0971418 0.300953
0.132944 0.329943
0.168746 0.358935
0.204548 0.387925
0.238648 0.400718
0.27445 0.429708
0.30855 0.442501
0.34265 0.455295
0.376749 0.468089
0.410849 0.4
80879
0.444949 0.493673
0.477346 0.490268
0.509718 0.486866
0.542115 0.48346
0.574512 0.480055
0.639307 0.473245
0.671704 0.46984
0.71861 0.448532
0.751007 0.445127
0.783405 0.441722
0.814087 0.422123
0.843079 0.38632
0.888267 0.348818
0.901061 0.314718
0.913855 0.280621
0.926646 0.246522
0.939439 0.212424
0.952233 0.178325
0.965027 0.144225
0.977818 0.110128
0.974413 0.0777306
0.987206 0.0436334
1 0.00953356

Now,I would like to check,if a certian 2D Point i.e. (0.965027 0.144225) lies on the given arc or not.
end


Thanks in advance!

[Math Enthusiast]

@KSSV: please do help

Answer 1

[Adam Danz]

My solution calculates the euclidean distance between the 'test point' to all points on the arc. If the minimum distance is below threshold, a message prints to the screen confirming that the test point is "on" the arc. If not, a message displays saying that the point is not on the arc. The threshold is set in the code; it's a maximum euclidean distance allowed from the arc.

To test, try point [0.1 0.3] which is at a distance of 0.003 from the 9th point on the arc. Whether that's on or off the arc depends on how you set your tolerance. In my code it's set to 0.001 so this example would be considered "off" the arc. See text below for limitations.

% Your data (cleaned up)
p = [0 0
0.00510736 0.0485933
0.00851245 0.0809906
0.0119173 0.113385
0.0153224 0.145782
0.0187272 0.178177
0.0400463 0.225069
0.0775509 0.270257
0.0971418 0.300953
0.132944 0.329943
0.168746 0.358935
0.204548 0.387925
0.238648 0.400718
0.27445 0.429708
0.30855 0.442501
0.34265 0.455295
0.376749 0.468089
0.410849 0.480879
0.444949 0.493673
0.477346 0.490268
0.509718 0.486866
0.542115 0.48346
0.574512 0.480055
0.639307 0.473245
0.671704 0.46984
0.71861 0.448532
0.751007 0.445127
0.783405 0.441722
0.814087 0.422123
0.843079 0.38632
0.888267 0.348818
0.901061 0.314718
0.913855 0.280621
0.926646 0.246522
0.939439 0.212424
0.952233 0.178325
0.965027 0.144225
0.977818 0.110128
0.974413 0.0777306
0.987206 0.04363341 
]; 

% Here's the test point
testpoint = [0.965027 0.144225]; 

% Visualize the arc and test point
plot(p(:,1), p(:,2), 'o-')
hold on
plot(testpoint(1), testpoint(2), 'r*', 'linewidth', 2)

% Calculate distance of testpoint to all other points
d = sqrt((testpoint(1) - p(:,1)).^2 + (testpoint(2) - p(:,2)).^2);

% Find minimum distance 
[minDist, minDistIdx] = min(d); 

% Set tolerance and determine if testpoint is concidered 'on' arc
tol = 0.001;  % this is the max distance allowed to be considered 'on' arc.
if minDist < tol
    % The testpoint is considered to be "on" the arc
    fprintf('Testpoint is on the arc at index number %d with a distance of %.5f\n', minDistIdx, minDist); 
else
    fprintf('Testpoint is NOT on the arc but is closest to index number %d with a distance of %.5f\n', minDistIdx, minDist); 
end

Testpoint is on the arc at index number 37 with a distance of 0.00000

A considerable limitation to this method is when the test point is "on" the arc but between two points. Consider the point [0.153, 0.3448]. That point is on the interpolated arc but not near any of the points. If you'd like to consider these cases you'll need to interpolate the points on your arc prior to calculating the distance.

[Math Enthusiast]

@Adam: Thanks for your answer.I will slightly modify my query.I would like to know, if certain points in a dataset represent arc or not.

Like,I just want to somehow,calulcate the accuracy of it being an arc or not.

You can take the above points and predict the percentage of it,being detected as an arc.

Thanks

[Adam Danz]

Oh, that's a completely different question with a completey different answer ;)

Any single point isn't an arc. Your original question provides a single data point and you ask whether it's on the arc or not. Instead, are you asking whether a subsection of points form an arch of not?

If that's what you're asking, and you're using the classic definition of arc (a portion of the circumference of a circle) try this proceedure:

1. Fit your data to a circle to get the best fit diameter of your data.
2. measure the error between your data and the best fit circle
3. deteremine if the error is within threshold to consider it an arc.

[Math Enthusiast]

@Adam: exactly,I am asking that.

Could you please provide your solution via MATLAB Code.I understand the concept a bit,but would be glad if you could provide the code.

Basically,I need the code for the three steps,you described above.

[Math Enthusiast]

@Adam: thanks for your response.I found out a MATLAB Function circfit(),which calculates the radius, center for my set of points.

The function is as follows:

function   [xc,yc,R,a] = circfit(x,y)
    x=x(:); y=y(:);
   a=[x y ones(size(x))]\[-(x.^2+y.^2)];
   xc = -.5*a(1);
   yc = -.5*a(2);
   R  =  sqrt((a(1)^2+a(2)^2)/4-a(3));
   
   

After this, could you explain,how I can check 2nd and 3rd steps,you described.

[Adam Danz]

I can guide you and help you when you get stuck.

The good news: there a function on the file exchange that will help you and it's pretty easy to use. Follow these steps and let me know if you get stuck

1. Go through this very short tutorial on how to fit your data to a circle. It explains how to use this function. That will provide you with the center point and radius of your fitted circle. https://blogs.mathworks.com/pick/2008/03/14/fitting-a-circle-easily/
2. Then you must compute the error which is the difference between your data points and the circle. I suggest using mean squared error but there are alternatives; the equation is shown below. To calculate the MSE, first caluculate the distance of each of your points to the circle's center. Use the distance equation I wrote in my original answer. Second, for each distance subtract the radius length and square that. Then add up all of those squared values and divide by the number of data points (just as the equation form wiki indicates).
3. Now you've got the MSE which is the error between your data and the circle. You'll need to decide what threshold to use to consider it a circle or not.

Let me know if you get stuck. I should mention that there's lots of alternatives to step 2 and the methodology really depends on how you'll use this data. For example, you could also fit the data to an ellipse to determine if it's a better fit than a cirlce. If the ellips is a better fit, you'd conclude that the data are not an arc.

[Math Enthusiast]

Great solution mate! Thanks a lot!

[Adam Danz]

My pleasure!

[sri harsha chilakamarri]

@Adam Danz: I have one more query to add up.

Once,I know that the entity is an circular Arc, How do I determine the angle of the arc.

Like,I want to find the angle made by the starting point of the arc to the endinpoint of the arc (either clockwise or anticlockwise).I tried it, but was unable to manage the different cases and put it in a code.

Thanks

[Adam Danz]

That's an interesting task. There are multiple ways to go about this and none of them are trivial. I've thought about it for a while and I think the method requiring the least amount of work is the following.

You'll need to calculate the angle between a vertical line passing through the center of your circle and a line extending from the center of your circle to each of your points. You can search for 'how to calculate an angle between two vectors'. If you have 'n' points, that will give you n angles. Then you'll need to subtract max(n)-min(n) to get the interior angle between the start and end of your arc. Look carefully at the angle results to make sure they are in the expected direction around the circle. Once you have the interior angle (theta, degrees) and the diameter of the cirlce (d), the arc length is

arcLen = (theta / 360) * pi * d;

[sri harsha chilakamarri]

@Adam: yeah,I get your logic, but somehow not able to put this logic into the code :(.Could you please elaborate more on "carefully looking at the angle results"

[Adam Danz]

Previously I suggested calculating the angle from vertical but your reference line is arbitrary and the math is easier if the reference line is horizontal so in this example we'll use a horizontal reference angle.

Let's say that the center of your fitted circle is at (x,y) and you're calculating the angle between horizontal and point (a,b) passing through the center of the circle.

1) You need the slope of each line. The horizontal slope is 0 (no math needed). The slope of the line passing through (x,y) and (a,b) is just

m = (b-y)/(a-x); 

2) The angle between two lines is calculated by

angle = atan((mb - ma) /  (1 + (ma * mb))); 

where mb and ma are the slopes of the two lines and angle is in radians. So just plug in your two slopes to get the inner angle. If you want the result in degrees,

angDeg = (180/pi) * angRadians;

You'll need to do that for all of your points and avoid using a loop; all the math above can be vectors that cover all of your points.

3) Now you've got a bunch of angles, one for each of your points. Look at the data. Are they as expected? If your points pass through the x axis, are any of the angles calculated in the 'wrong' direction? Are the signs as expected? Try a bunch of variations to make sure you don't need to adjust the direction of the angle for dots that pass the x axis.

4) After you confirm that your data are correct, all you need to do is calculate the difference between the max and min angle to get the inner angle of your arc.

5) Now you can calculate arc length via the equation below (note use of degrees)

arcLength =  (innerAngle / 360) * circumference;