realize a circle passing through multiple points

[cacciatorino]

you have to divide in three circular sectors the cloud of points (120°), for each sector to make the arithmetic average of the cordinate (x1+x2...)/n; (y1+...)/n: (z1+...)/n, points. find the three points with cooedinate x,y,z. through which you build your circumference. the programs I know with double clik above the point give me the coordinates of the point.

But I'm sorry, the center of an arch is not on the arch itself but well moved to the center. doing as you say maybe you can estimate the center with good precision but not the radius.

 

[Fulvio Romano]

But I'm sorry, the center of an arch is not on the arch itself but well moved to the center. doing as you say maybe you can estimate the center with good precision but not the radius.

Exactly, what I said in the previous post.

 

[cacciatorino]

Exactly, what I said in the previous post.

Sorry I didn't really see page two of the discussion!!!! I ask forgiveness!

 

[Antosacca]

You're right, the center of gravity doesn't work.
I would return to the coordinates average.

 

[Giuseppe Mauro]

you do not take it, even if I have not been able to find a solution, it does not mean that if I find a mistake in yours I do not have the right to make it present. If I see a car against my hand, I'll let the driver know if I don't have a driver's license, right? :finger:

I quote this of yours, fulvio, for I find that you are right, and therefore I also bring back the initial question of geo mouse

of a circular tube I detected many points on its perimeter. now I have to return a single circle (and then locate the center "half" and its radius "half").
It is therefore a circle that passes through multiple points (from 4 to 20 variables) or better as close as possible to these points.
Topogee

now, keeping in mind the question, I make my comments on your images, from "without license":
image 1:
It's the one closest to reality, except for the fact that the "nuvola" of points, is reduced, first because being a tube, can't have measured inside, second instance because mouse will have detected at max 20,
distributed along the perimeter

image 3:
absolutely out of hypothetical range. if one who wants to detect a tube, imagine to detect it by concentrating all the jokes on one side of the circumference.... simply need to "recommend" and in September repair examination.

image 2:
That's what I'm saying about image 3, unless you have points on the other side. In this case, the over abundance of points on the one hand is to be considered as an unnecessarily reluctant information, whose only effect, if included for the purposes of calculation, is to move to that area the averages and then mislead the final result.

I think you're moving the problem, from a major problem on the field, to that of mathematical abstraction.
If mouse is a good detector, then he will have placed his points more or less equally distributed along the circumference.
If mouse is a good detector, he won't have 20 points on half the circumference.
if topogee has detected with a topographic odour, then he will have used a tool that will have an averagely low error, which allows him to have a location of points with error less than 1/500l (circ. 2/92)
If mouse is a good detector, he will know that a 3% error in construction is still considered as tolerance.


demonstrating (as I have shown) that starting from more or less distributed points, taken with a tolerance of +/-5%, it becomes to a final error of 2per thousand, I imagine what happens if I pass the procedure for points moved in origin of the 2per thousand. I would probably get a circle with error compared to the real of 1/10.000
I would say that the topogee question is not only satisfied, but gives it a safety margin that is largely part of the relief standards.

If we want to move it to mathematical abstraction, then the speech changes completely

 

[Fulvio Romano]

first because being a tube, he can't have measured inside.

Huh?
if a tool measures a point on the tube, it has the same probability of wrong in excess or in defect. What does the points have to do with the inside?

absolutely out of hypothetical range. if one who wants to detect a tube, imagine to detect it by concentrating all the jokes on one side of the circumference.... simply need to "recommend" and in September repair examination.

I'm sorry to contradict you, but that's exactly what you usually do. often some areas of the pipe are not accessible, so the profile is reconstructed from other areas.

In this case, the over abundance of points on the one hand is to be considered as an unnecessarily reluctant information, whose only effect, if included for the purposes of calculation, is to move to that area the averages and then mislead the final result.

Excess points is not a desired thing, but something that can happen in some cases. a priori you cannot know how the points are distributed, so you cannot establish a method that works only if these are distributed "good".

dimostrando (come ho dimostrato)

to prove that a method works, does not mean to make a single test, among other things built ad hoc. so demonstrate that the method works on your example, not in general. on the contrary, yes. finding a single case in which a method does not work means showing that the method is wrong.

If we want to move it to mathematical abstraction, then the speech changes completely

I'm not mathematically abstracting. I am saying that there are wrong methods and that you have to be careful to use them.
then if you want to approximate by saying "vabbé but so much the error is small", then find to the eye the center and draws by hand the circumference. you will certainly make even smaller mistakes.

 

[Joseph]

return to the initial statement:gave a tube circular I found a lot of points on his perimeter.if the beaten points are on the perimeter, which is openly declared to be a circle, why seek more than 3?

supposing instead that the tube is not circular, I kept a solution easily translated into lisp code:
- taking the points to groups of 3, building (with a cycle) more circumferences of which are determined the respective centers;
- the centre of all circulatory centres is determined;
- the average distance of all points from the previous centre is calculated;
- traces the circumference with radius = average distance and center=baricentro of the centers.


Good Sunday

 

[Fulvio Romano]

Let's do something. to simplify the problem we try to understand what the limits are.
how are the points around the circumference distributed?
because if they are uniformly distributed, there is certainly no need to do all these mental pimps. There is no need to resort to stratagems with triangles, baricentres, etc.

simply, the center of the circumference will coincide with the center of the points, its radius, with the average radius.

Let's see.

with the following generosity code the circumference:

% I define the parameters of circumference
r=100;
xc=50;
yc=50;
error=20;

% genero la circumference
♪[0 : 0.01 : 6.28]; % I generate the axis of the corners
x=xc+r*sin(t);% I generate x of the circumference points
y=yc+r*cos(t);% genero la y dei punti di circumference

plot(x,y,'b'); % drawing circumference
axis equal; % I make equal axes
hold on;

with the following simulus the measure. You will notice that the error is on average nothing, and the amount of points is constant with the angle. a rather strong assumption when it comes to measures.

% of the measuring points
re=r+(rand(1,numel(t))-0.5)* error; % calculation of rays as a normal distribution
% and symmetrical with respect to circumference
for i=1:numel(t)
xi(s)=xc+ri(s)*sin(s));% I generate x of measuring points
yi(i)=yc+ri(i)*cos(t(i));% genero la y of measuring points
end

plot(xi,yi,'.r'); % drawing the measuring points

Now let's see the algorithm I wrote above:

xcc = mean(xi);
ycc = mean(yi);
rr = mean(re)

xxi=xcc+rr*sin(t);% I generate x of the reconstructed circumference points
yyi=ycc+rr*cos(t);% genero la y of the reconstructed circumference points

plot(xxi,yyi,'r'); % drawing circumference

What comes out of it?

in blue the initial circumference, in red the reconstructed one and the measuring points.

real / calculated radius = 100 / 100.15
distance between centres = 0.213

in the second image I brought the error from 20% to 60%

here we have real radius / calculated 100 / 101.44
and distance between centres = 0.45864

If this is enough, the right algorithm is this. but a measurement system that you respect cannot require, to work, such stringent assumptions on the starting data.

 

[Giuseppe Mauro]

Huh?
if a tool measures a point on the tube, it has the same probability of wrong in excess or in defect. What does the points have to do with the inside?

the inside/out as the tolerance of the instrument is considered. if you read bele I said deviation +/-5%
a 10% measurement error of the measured object is a mistake and must be discarded.
you have points that are inside (but also out) unreally. Are you detecting "eye"?

I'm sorry to contradict you, but that's exactly what you usually do. often some areas of the pipe are not accessible, so the profile is reconstructed from other areas.

then had satisfied with the (gross) tolerances you can get.
When I read, I find "a way" in the important phase, to establish in a unique way where an object is. If one is puppy, and the relief can't do it... Then he went to seed potatoes.
if you can do so, then you get the most out of what you can challenge your "competitor" to do better in equal terms.

Huh?
Excess points is not a desired thing, but something that can happen in some cases. a priori you cannot know how the points are distributed, so you cannot establish a method that works only if these are distributed "good".

What? a priori cannot know how the points are distributed? but do you do the relief, or do you find the measurements scattered on the ground near the relief zone?
When I pick up, I want to know that point. I'm not batting "sex organ" points.
so the quantity and the distribution of points, I decide.
from this comes that I may not have access to a certain area, but never have excess points where I do not need and absent where I would need at least one.
If you read the criteria you described... I understand some things I've seen around.

to prove that a method works, does not mean to make a single test, among other things built ad hoc. so demonstrate that the method works on your example, not in general.

2 examples with different rays and different distribution of "relevated" points (tolerance from detection, do not throw them as yours)

Huh?
so show that the method works on your example, not in general. on the contrary, yes. finding a single case in which a method does not work means showing that the method is wrong.

in fact so far you have only "detracted" from the solutions of all, without bringing tangible human and simple solutions to those who had posted the question.
I think it's the pd's run for the last 20 years... "I oppose myself!" (I don't know what but in the meantime I start opposing myself).

I'm not mathematically abstracting. I am saying that there are wrong methods and that you have to be careful to use them.

When you ask yourself, "I have 20 points on a circle" and you take 20 points out here and there.
at the moment when you reiterate "but I am on the circle" and you move them all on one side
at the moment when you come to say "I have to return an average circle with an average radius" and you come to me to talk about "energy" for the arm of the distance from point to circumference....

Well, you're abstracting. you are trying to find a general rule, in variable conditions, faced with a unique, tangible and defined problem.
Topogee asks how to collect an apple fall... and you're looking for the law of universal gravitation to calculate where the next apple will fall.

then if you want to approximate by saying "vabbé but so much the error is small", then find to the eye the center and draws by hand the circumference. you will certainly make even smaller mistakes.

Well, you're the vest of the situation, come on, here are parchment paper and brush. I am in trepidation waiting for your perfect circle. . .

return to the initial statement:gave a tube circular I found a lot of points on his perimeter.if the beaten points are on the perimeter, which is openly declared to be a circle, why seek more than 3?

supposing instead that the tube is not circular, I kept a solution easily translated into lisp code:
- taking the points to groups of 3, building (with a cycle) more circumferences of which are determined the respective centers;
- the centre of all circulatory centres is determined;
- the average distance of all points from the previous centre is calculated;
- traces the circumference with radius = average distance and center=baricentro of the centers.


good Sunday[/quote
Good evening to you josh...
and be careful what you say, because it's very easy to demolish what you wrote.
You do not make the reliefs with points along the circumference. are made of male sex organ canine:biggrin:

 

[Fulvio Romano]

I find myself also testing with the three sectors:

the code is this:

% according to algorithm: centre of sectors
% design of the three sectors
plot (xi(1:numel(ri)/3), yi(1:numel(ri)/3), '.r') % first sector
plot (xi(numel(ri)/3:numel(ri)*2/3), yi(numel(ri)/3:numel(ri)*2/3), '.g') % second sector
plot (xi(numel(s)*2/3:numel(s)), yi(numel(s)*2/3:numel(s)), '.b') % third sector

xg1 = mean(xi(1:numel(ri)/3)); % calculation of the centre of the three sectors
yg1 = mean(yi(1:numel(ri)/3));

xg2 = mean(xi(numel(s)/3:numel(s)*2/3));
yg2 = mean(yi(numel(ri)/3:numel(ri)*2/3));

xg3 = mean(xi(numel(s)*2/3:numel(s));
yg3 = mean(yi(numel(re)*2/3:numel(re));

plot(xg1, yg1, '*r'); % design of the three centerpieces
plot(xg2, yg2, '*g');
plot(xg3, yg3, '*b');

It seems quite evident what he wrote as a hunter.

 

[Fulvio Romano]

If you read the criteria you described... I understand some things I've seen around.

You're starting to offend deliberately, so I close here. I made it right in time to propose a simpler solution (baricentre + average of the rays) and that gets the same result. wrong, but he gets it.

I know what it means to make measuring instruments. You're obviously not, because you're saying a lot of inaccuracies. knowing how to make a relief should not be a precondition for using a tool, otherwise you have no hope of selling it.
finding an algorithm that returns correct values even in "difficult" measurement conditions is what I do (and not only in this thread!), what makes the market, what makes the rest of the world around you.

I suggest you fill in with humility, understand what I wrote before spitting on it (if you confuse lyapunov with a calculation of baricentro, do more beautiful figure to say "I don't know, explain me?", and anyway just wikipedia), and to return to the sown. I didn't tell you to go to seed potatoes, despite the big inaccuracies distributed in your post, and by inaccuracies I mean... so we understood!

 

[Giuseppe Mauro]

You're starting to offend deliberately, so I close here.

I offend because I say that I have seen reliefs around, made by Mooool studies appointed, which had errors of the order of 15cm/m?
All right, offend, what do you want me to say?

I made it right in time to propose a simpler solution (baricentre + average of the rays) and that gets the same result. wrong, but he gets it.

Is that something very close to what has already been proposed as a solution and that you liquidated as invalid?
I mean, you're telling me that if a hunter says so, rather than an antoniov isn't valid, if it comes from your ecumenicals, it's not accurate, but it's welcome? Is that what you're telling me?

I know what it means to make measuring instruments. You're obviously not, because you're saying a lot of inaccuracies. knowing how to make a relief should not be a precondition for using a tool, otherwise you have no hope of selling it.

No, maybe you're approaching the problem from a point of view away from reality.
The instrument is functional to the relief, not the reverse. The relief is an art. if you have not had good teachers or good experience, you do not learn it.
If we want to transport the speech to painting (for example), you take care of brushes. but forget that your brush, albeit ultrasophageal, paints a monne lisa alone:smile: .
Keep in mind that the reliefs and measures, albeit with due difficulty, are carried out since the night of time. and I don't think the timer, there was a Roman lightning bolt with its sophisticated instruments.
If you want to make a tool that does without the human being, please, red carpet. It means we're gonna have a series of automatons pressing a pusantino and have made the relief. Then after that, those like me will intervene, which will correct those reliefs.
sale of tools for you, which generates work for me, excellent commercial solution.

finding an algorithm that returns correct values even in "difficult" measurement conditions is what I do (and not only in this thread!), what makes the market, what makes the rest of the world around you.

Then I'm not mistaken. you are mathematically abstracting to find a generically valid solution, starting from a peculiar problem.
You're right. Believe me, I won't ask you for any money.
And you make us even more beautiful. the transparency of mind always pays.

I suggest you fill in with humility, understand what I wrote before spitting on it (if you confuse lyapunov with a calculation of baricentro, do more beautiful figure to say "I don't know, explain me?", and anyway just wikipedia), and to return to the sown.

Well, I don't confuse lyapunov with a baricentro, but I have no difficulty stating that for me lyapunov could also be the cousin of krushov.
but in the same way, from the top of 24 years of reliefs/restitutions, you don't have to tell me what it takes and how it detects, especially a circular tube. . .
To make you understand who you're talking to, I'm just telling you that one of my reliefs went to portgallo from a certain old siza, who had to revise an executive project.
I saw your work. Very beautiful. But I don't think I've seen any trace.

I didn't tell you to go to seed potatoes, despite the big inaccuracies distributed in your post, and by inaccuracies I mean... so we understood!

No, I didn't understand you. generally "we understand each other" says who wants to mean, without exposing himself. afraid to be contradicted, ing?
I said if one's a puppy and he can't make the relief, he'd go.
What is the reason why you included yourself in that portion of humanity, ing.?

As I could see, you have not commented on the other 2 important examples, with decentralized/asymmetrical points. particular reasons for failure to comment?

 

[Fulvio Romano]

solved!

renounced to lyapunov, solved with a more "traditional" method.

works very well also for big errors and incomplete scans of the circumference.
to demonstrate that, with a solid "theoretical" preparation, a bit of determination is enough to solve any problem.
for this I must thank very much Giuseppe mauro. If I hadn't had the need to prove something, I would probably have quit before. but you know, this is a known problem of us engineers. . .

I have not tried yet with particularly "bad" compensations and outliers.

all explained in the annex. Excuse any refugees, but given the time...
:finger:

 

[Giuseppe Mauro]

Good lightning. found a pretty manageable solution.
I would have tried to turn your list into a lisp list, but there's a point where there's a problem.

you start by building your circumference, drawing the x and y of the points, through the function of the circumference.
All right here. then draw the deviated points, and to distribute the points, randomize an addition/detraction to the xy of the points, along the circumference, using the thing. so far all right.
After that, the deviations of the points, reconstructing the components x and y of the points (cycle for i=1, npunti) and refer to the cos and sin.

but this works because you built the points around a 0.0 origin, which is your starting circle.
In reality you should not know the origin 0.0 of the cloud, you should seek it. and the coordinates of origin (i.e. the center of the circle) are uniquely linked to the distribution of the cloud of points.
I don't know anything about matlab, but reading the functions this was my impression.
If you can, move the cloud of points out of the center of origin of the initial circle, and check if turning the program, it returns you the same result.

As for approximations, I'd say they're more than good.

 

[Fulvio Romano]

all part of code before:

% --> problem resolution <--

only to generate points. You don't need this part in the lisp because in the real case the cloud of points you already have. I used it because I didn't have the cloud of points and I had to do it.

the whole part later instead solves the problem. in xi(s) and yi(s) variables there are the points of the cloud, and if you look well I use only this information to find xcc, ycc and rr, that is the coordinates of the center and the radius.
I have no further information about building the initial circle.

 

[topogeo]

Thank you all for your passion in looking for the solution to my problem.
I would like to point out that the problem arises from a concrete case:
we have a forced conduct realized with a tube that "would" be circular with a diameter of about 2 mt. now we viole embroidered i.e. we want to insert a new circular tube inside it (i.e., made circular with mm precision). I have to detect the existing one. I can make it from the inside (of course it takes off the water!) with topographic instrumentation: 1" angular precision and 1mm+1.5ppm spacer. the collimation will be automatic ( sqm 1.5 mm up to 200 mt). therefore precision waiting for the relief about 2-3 mm per point (of course we use forced centering for stations). the relief is required one section every 5 mt (the conduct is about 1500 mt long) and on each section will be detected about 10 points. the customer requires : a) the axis (center) of each section, b) the circle "medium" which more approximates the actual circumference of the tube.
Starting from work, it is good to find a solution that is valid for any case where "from a cloud of points, not equally distributed, can find the circle that best represents it".
in mathematical terms the optimal solution is to determine with the method of minimum squares the values describing the circle (center and diameter) that best approximates the points.
This is the approach followed by dotsoft .
In fact, it is useful to have a mirror that brings back to every point the distance that this is the average calculated circumference.
So if the theoretical approach you found correctly (in my opinion) follows a nice lisp, the problem is solved (and I do not stay with entering the tube .. hoping that the lever of "reopening" of the water is well blocked!).

Topogee

 

[Fulvio Romano]

the code made by me uses precisely the minimum squares.

I have also come to mind other algorithms, one in particular reported in lime, but less points with very big errors, reliability should be the same as the one proposed with the minimum squares.

p.s.
If it should be complicated to make a lisp, I could try to make a program that takes in a dxf with the points and returns a dxf with the circle and a set of data.
I'm sorry, but I can't work directly on the dwg.

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
other algorithm
often you find yourself making laser readings in tube speed. in this case sometimes it is found of the environmental powder that brings some points very far from the real ones.

If you take three points at 120° between those of the cloud, you can locate center and radius of a circumference. by turning these three points between all those of the cloud you get n/3 circumferences, of which you can make an average, discarding through analysis of variance those clearly out of center.

In this way it is obvious to the problem, but topogee does not have. therefore the method to the minimum squares should have the same precision, indeed, perhaps even slightly higher.
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

[Giuseppe Mauro]

all part of code before:
the whole part later instead solves the problem. in xi(s) and yi(s) variables there are the points of the cloud, and if you look well I use only this information to find xcc, ycc and rr, that is the coordinates of the center and the radius.
I have no further information about building the initial circle.

in fact, fuvio. I understood that.
what I can't make to square and that a thing or a sin make sense when you know the origin. If you don't know the origin (why are you looking for it) how do you get a corner? a corner is a portion of space between 3 points.
One is the point at that time, one is the x (or y) component of the point in question, the other is the origin. but you don't know the origin, so you can't delimite a portion of space to measure the corner.
I hope I've been clearer.

we have a forced conduct realized with a tube that "would" be circular with a diameter of about 2 mt. now we viole embroidered i.e. we want to insert a new circular tube inside it (i.e., made circular with mm precision). I have to detect the existing one. I can make it from the inside (of course it takes off the water!) with topographic instrumentation: 1" angular precision and 1mm+1.5ppm spacer. the collimation will be automatic ( sqm 1.5 mm up to 200 mt). therefore precision waiting for the relief about 2-3 mm per point (of course we use forced centering for stations). the relief is required one section every 5 mt (the conduct is about 1500 mt long) and on each section will be detected about 10 points. the customer requires : a) the axis (center) of each section, b) the circle "medium" which more approximates the actual circumference of the tube.
Topogee

because you will have very low errors, the method of the region with consequent recalculation of origin and area, in my opinion it fits you great. the only neo, to do it "handed" for 300 sections.. .
I have to tell you that I can't write an ad hoc lisp for a long time.
But since the tube section is long, could it not be worth interlogging with a company that owns a 3d laser scanner?

going instead in off-topic regarding your problem, I find the solution they want to adopt to embroider the very slender tube, in front of the result you want to get.
There are more efficient recovery techniques to solve this type of problem.
and I'll tell you about cipp, where you put a tube in fabric (liner), inflate it to adhere to the walls, then apply energy (heat or uv rays) to polymerize the resins with which the liner is funneled
or cml (cement mortar lining), where high speed projectors a cementitious layer on the walls of the existing tube. . .

p.s. do not speak with the clients... with these techniques you would lose the need for a relief of the existing....

 

[AntonioV]

for the "rich flat" series, here is my modest geometric solution, created with autocad map2006:

1] I create a circular crown containing randomly arranged points



2] by means of the free dtm.vlx I join the 3 sets of points to form 3 distinct dye (triangular irregular network)



3] with the command _union balances the 3 rectors to form 3 distinct regions, and for each of the 3 regions, I create a topology with its center (for the definition in Italian of "topological centerroid" I ask for help to pr and tristan, thank you)



4] I connect the 3 centerpieces with circle passing for 3 points.



for those who want to examine the source, here it is

 

[Fulvio Romano]

in fact, fuvio. I understood that.
what I can't make to square and that a thing or a sin make sense when you know the origin. If you don't know the origin (why are you looking for it) how do you get a corner? a corner is a portion of space between 3 points.
One is the point at that time, one is the x (or y) component of the point in question, the other is the origin. but you don't know the origin, so you can't delimite a portion of space to measure the corner.
I hope I've been clearer.

You mean the fat part?

for i=1:npunti
ax(i, = [1, cos(t(i))];
bx(i, = [xi(i)];
ay(i, = [1, sin(t(i))];
by(i) = [yi(i)];
end
xx = inv(transpose(ax)*ax)*transpose(ax)*bx;
xy = inv(transpose(ay)*ay)*transpose(ay)*by;xcc = xx(1);
ycc = xy(1);
rr = (xx(2)+xy(2))/2;% design reconstructed circumferencexxi=xcc+rr*cos(t);% I generate x of the reconstructed circumference points
yyi=ycc+rr*sin(t);% genero la y of the reconstructed circumference pointsplot(xxi,yyi,'r'); % drawing circumference

that part there only serves to draw the circumference. in the previous part of code I found center and radius of the circumference (underlined part), and here ends the solution.
then to draw it with a plot (which draws only lines) I have to build the circumference as a line between the points. But that's not about the algorithm. If I had to export a dxf, I would simply pass the three highlighted numbers.