Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Estimate circumference of a set of scattered data in 2-D

Subject: Estimate circumference of a set of scattered data in 2-D

From: pdafniotis@yahoo.com (Petros Dafniotis)

Date: 10 Jan, 2002 07:55:52

Message: 1 of 9

I have a problem which can be recast as follows.

1. Consider a circle and generate say 100 points (x(i), y(i)) using its
   parametric equations
2. Shuffle around the 100 points so that (x(2),y(2)) is not say neighbor of
   x(3), y(3)
3. Add some noise to the x,y data

Objective: Calculate an approximate circumference or find a best fit curve, etc.

I can calculate the convex hull but in my problem the curve is generally not convex.

Thank you for any pointers/help. Kind regards,

Petros
---
Petros Dafniotis, PhD
pdafniotis@yahoo.com

Subject: Estimate circumference of a set of scattered data in 2-D

From: nospam@thank.you (Denis Gilbert)

Date: 11 Jan, 2002 14:24:55

Message: 2 of 9

On 10 Jan 2002 07:55:52 -0800, pdafniotis@yahoo.com (Petros Dafniotis)
wrote:

>I have a problem which can be recast as follows.
>
>1. Consider a circle and generate say 100 points (x(i), y(i)) using its
> parametric equations
>2. Shuffle around the 100 points so that (x(2),y(2)) is not say neighbor of
> x(3), y(3)
>3. Add some noise to the x,y data
>
>Objective: Calculate an approximate circumference or find a best fit curve, etc.
>
>I can calculate the convex hull but in my problem the curve is generally not convex.
>
>Thank you for any pointers/help. Kind regards,
>
>Petros
>---
>Petros Dafniotis, PhD
>pdafniotis@yahoo.com


Hi Petros,

Here's a neat function I obtained from a posting in this newsgroup a
couple of years ago. Your circumference is then simply 2*pi*R.

hth, Denis.


function [xc,yc,R,a] = circlefit(x,y)
%CIRCLEFIT - Fits a circle to data
%
% [xc, yx, R] = circlefit(x,y)
%
% fits a circle in x,y plane
%
% Result is center point (xc, yc) and radius R
% an optional output is the vector of coeficient a
% describing the circle's equation
%
% x^2+y^2+a(1)*x+a(2)*y+a(3)=0
%
% by Bucher izhak 25/oct/1991

n=length(x); xx=x.*x; yy=y.*y; xy=x.*y;
A=[sum(x) sum(y) n;sum(xy) sum(yy) sum(y);sum(xx) sum(xy) sum(x)];
B=[-sum(xx+yy) ; -sum(xx.*y+yy.*y) ; -sum(xx.*x+xy.*y)];
a=A\B;
xc = -.5*a(1);
yc = -.5*a(2);
R = sqrt((a(1)^2+a(2)^2)/4-a(3));

%End of code

Subject: Estimate circumference of a set of scattered data in 2-D

From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)

Date: 11 Jan, 2002 17:01:33

Message: 3 of 9

In article <e54adf36.0201100755.1c81b5a6@posting.google.com>,
 pdafniotis@yahoo.com (Petros Dafniotis) writes:
|> I have a problem which can be recast as follows.
|>
|> 1. Consider a circle and generate say 100 points (x(i), y(i)) using its
|> parametric equations
|> 2. Shuffle around the 100 points so that (x(2),y(2)) is not say neighbor of
|> x(3), y(3)
|> 3. Add some noise to the x,y data
|>
|> Objective: Calculate an approximate circumference or find a best fit curve, etc.


what you need to know is the order of your points on the curve relative to its
"true" standard parametrization , so if you could write the curve as
  x=f(t)
  y=g(t)
then x(i)=f(t(i)) , y(i)=f(t(i)) i=1,..,N and t(1)<t(2)<t(N).
from your description I assume this is the case.
since you want a closed cccurve add
x(N+1)=x(1), y(n+1)=y(1) to your data list.
then you can approximate the curve by a smooth vector function
(f(t),g(t)) and
length= integral_{t(1) to t(N+1)} sqrt(f'(t)^2+g'(t)^2) dt.
a good basic choice for t(i) might by the arclenth of the piecewise linear
path connecting the points and a choice for f(t) and g(t) the two
cubic splines interpolating the data (t(i),x(i)) and (t(i),y(i)), i=1,...,N+1
using a periodic spline you can make the total curve C2. (otherwise a
discontinuity
of the derivative will occur in t(1) resp t(N+1). )
hth
peter

Subject: Estimate circumference of a set of scattered data in 2-D

From: Randy Poe

Date: 11 Jan, 2002 12:52:08

Message: 4 of 9

Denis Gilbert wrote:
> Hi Petros,
>
> Here's a neat function I obtained from a posting in this newsgroup a
> couple of years ago. Your circumference is then simply 2*pi*R.
>
> hth, Denis.

Without going through the code mathematically in gory
detail, I get the impression it is doing a least-squares
fit to the data. Agreed, a useful thing, and probably
suits the OP's purpose.

But in general, what if you wanted a bounding circle
instead of a fitted circle? Or more generally, what
if you wanted some sort of 2-d quantile, i.e. a
contour that contained p% of the data?

Is there an easy way to do that? Does this start to
become a clustering algorithm? (my interest is not
entirely idle, such a thing would be pretty useful
to something I'm doing right now).

       - Randy

Subject: Estimate circumference of a set of scattered data in 2-D

From: Nathan Cahill

Date: 11 Jan, 2002 13:52:59

Message: 5 of 9

You can find a bounding circle by doing a least squares fit subject to
the constraint(s) that the residuals are positive.

I'm not sure if there's an easy way to get quantiles.

HTH,
Nathan Cahill

Randy Poe wrote:
>
> Denis Gilbert wrote:
> > Hi Petros,
> >
> > Here's a neat function I obtained from a posting in this newsgroup a
> > couple of years ago. Your circumference is then simply 2*pi*R.
> >
> > hth, Denis.
>
> Without going through the code mathematically in gory
> detail, I get the impression it is doing a least-squares
> fit to the data. Agreed, a useful thing, and probably
> suits the OP's purpose.
>
> But in general, what if you wanted a bounding circle
> instead of a fitted circle? Or more generally, what
> if you wanted some sort of 2-d quantile, i.e. a
> contour that contained p% of the data?
>
> Is there an easy way to do that? Does this start to
> become a clustering algorithm? (my interest is not
> entirely idle, such a thing would be pretty useful
> to something I'm doing right now).
>
> - Randy

Subject: Estimate circumference of a set of scattered data in 2-D

From: nospam@thank.you (Denis Gilbert)

Date: 11 Jan, 2002 19:07:12

Message: 6 of 9

On Fri, 11 Jan 2002 12:52:08 -0500, Randy Poe <rpoe@atl.lmco.com>
wrote:

> in general, what if you wanted a bounding circle
>instead of a fitted circle? Or more generally, what
>if you wanted some sort of 2-d quantile, i.e. a
>contour that contained p% of the data?
>
>Is there an easy way to do that? Does this start to
>become a clustering algorithm? (my interest is not
>entirely idle, such a thing would be pretty useful
>to something I'm doing right now).
>
> - Randy


Hi Randy,

look at the function ROPE on Matlab Central File Exchange. It uses
ellipses rather than circles but I am sure you will find it useful.

http://www.mathworks.com/matlabcentral/fileexchange/Files.jsp?type=category&id=&fileId=273

Denis.

Subject: Estimate circumference of a set of scattered data in 2-D

From: Randy Poe

Date: 11 Jan, 2002 16:38:37

Message: 7 of 9

Denis Gilbert wrote:
>
> On Fri, 11 Jan 2002 12:52:08 -0500, Randy Poe <rpoe@atl.lmco.com>
> wrote:
>
> > in general, what if you wanted a bounding circle
> >instead of a fitted circle? Or more generally, what
> >if you wanted some sort of 2-d quantile, i.e. a
> >contour that contained p% of the data?
> >
> >Is there an easy way to do that? Does this start to
> >become a clustering algorithm? (my interest is not
> >entirely idle, such a thing would be pretty useful
> >to something I'm doing right now).
> >
> > - Randy
>
> Hi Randy,
>
> look at the function ROPE on Matlab Central File Exchange. It uses
> ellipses rather than circles but I am sure you will find it useful.
>
> http://www.mathworks.com/matlabcentral/fileexchange/Files.jsp?type=category&id=&fileId=273

Actually, yes, that sounds like exactly what I was thinking of.

Thank you.

           - Randy

Subject: Estimate circumference of a set of scattered data in 2-D

From: pdafniotis@yahoo.com (Petros Dafniotis)

Date: 12 Jan, 2002 09:10:56

Message: 8 of 9

Peter-
my problem is exactly that.

The worse part is how to put all points in some order.
I was looking into Delaunay, natural neighbors, or anything else that could
put things in order. The general shape is not a circle, I just used this as an
example. Any ideas?

Kind regards,
Petros

spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) wrote in message news:<a1n5pd$2en$3@sun27.hrz.tu-darmstadt.de>...
> In article <e54adf36.0201100755.1c81b5a6@posting.google.com>,
> pdafniotis@yahoo.com (Petros Dafniotis) writes:
> |> I have a problem which can be recast as follows.
> |>
> |> 1. Consider a circle and generate say 100 points (x(i), y(i)) using its
> |> parametric equations
> |> 2. Shuffle around the 100 points so that (x(2),y(2)) is not say neighbor of
> |> x(3), y(3)
> |> 3. Add some noise to the x,y data
> |>
> |> Objective: Calculate an approximate circumference or find a best fit curve, etc.
>
>
> what you need to know is the order of your points on the curve relative to its
> "true" standard parametrization , so if you could write the curve as
> x=f(t)
> y=g(t)
> then x(i)=f(t(i)) , y(i)=f(t(i)) i=1,..,N and t(1)<t(2)<t(N).
> from your description I assume this is the case.
> since you want a closed cccurve add
> x(N+1)=x(1), y(n+1)=y(1) to your data list.
> then you can approximate the curve by a smooth vector function
> (f(t),g(t)) and
> length= integral_{t(1) to t(N+1)} sqrt(f'(t)^2+g'(t)^2) dt.
> a good basic choice for t(i) might by the arclenth of the piecewise linear
> path connecting the points and a choice for f(t) and g(t) the two
> cubic splines interpolating the data (t(i),x(i)) and (t(i),y(i)), i=1,...,N+1
> using a periodic spline you can make the total curve C2. (otherwise a
> discontinuity
> of the derivative will occur in t(1) resp t(N+1). )
> hth
> peter

Subject: Estimate circumference of a set of scattered data in 2-D

From: Tom Davis

Date: 13 Jan, 2002 21:31:02

Message: 9 of 9

Total least squares (TLS) curve fitting minimizes the sum of squared
orthogonal distances from the data to the curve. The result is a
maximum likelihood estimator when both the x and y data are subject to
errors that are independently and identically distributed with zero mean
and common variance.

function [f,r] = objective(z,x,y)
% TLS circle fit objective f and radius r
n=length(x);
r=sum(sqrt((x-z(1)).^2+(y-z(2)).^2))/n;
f=(x-z(1))'*(x-z(1))+(y-z(2))'*(y-z(2))-n*r^2;

Examples:

x=[0.7;3.3;5.6;7.5;6.4;4.4;0.3;-1.1];
y=[4;4.7;4;1.3;-1.1;-3;-2.5;1.3];
options=optimset('TolFun',1e-10);
z0=[0,0]; % center estimate
z=fminsearch('objective',z0,options,x,y)
% center z = [3.0432, 0.7457]
[f,r]=objective(z,x,y)
% radius r = 4.1059

x=[5;10;7;9;2;-1;0;-1];
y=[-3;3;5;9;8;7;3;-1];
z0=[0,0]; % center estimate
z=fminsearch('objective',z0,options,x,y)
% center z = [4.1714, 2.8790]
[f,r]=objective(z,x,y)
% radius r = 5.7389

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us