realize a circle passing through multiple points

[topogeo]

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.
Do you know a lisp for a fee?

Topogee

 

[PlannerRoad]

a small presentation is welcome first:
http://www.cad3d.it/forum1/showthread.php?t=187

 

[Giuseppe Mauro]

I don't think it exists. mathematically you can get a 3-point circle (the 3 points of an arc), but already at the 4th point if the point does not lie exactly on circle becomes a problem.

The advice I give you is to proceed gradually.
create n look for 3 points (6 in your case) and then create circles for 3 points that will be the intersections of the circles you previously obtained.
It's the way it gives you less chance of error.
summarized 6 circles for 3 points -> 3 circles for the 6 intersections (if esistino) -> 1 circle for the new intersections of the last 3 circles.
It's true you dropped two points, but you went on average weighing on 18, I see it pretty accurate.

 

[topogeo]

Of course a circle can't pass exactly for four or more points.
There must be a discard on each one.
What I'm looking for is a lisp that I created this "medium" circle.

I have to tell you that a first solution I raised it in a collection of utilities http://www.dotsoft.com/mwdesign.htm in the command "curves" controlled fit.
but I hope to receive more reports.

I'm gonna piss him off.

 

[Antosacca]

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.

 

[AntonioV]

great idea, anto', but uncomfortable if the cloud of points contains dozens of points, unless some "master lisparo" does not automate the procedure.. .

:

 

[Antosacca]

more simply but less accurate: always three sectors and build a surface among the most extreme points, snap on baricentro surfaces and make you your beautiful circumference, (alias circle) with the three points.

 

[AntonioV]

even more precise:

1] I make a point of each of the 3 sectors

2] I regions the individual triangles and join them in a single region

3] _massprop on it, and I have the exact center (and not approximate)

4] Hoop for 3 baricentres

:

 

[Fulvio Romano]

This method of sectors is wrong. At least, if I understand what we're looking for.
I think I understand that we are looking for circumference that minimizes its distance from various points. date a distribution [più di due] points there is only one circumference with this property.

If you change the sectors, even if you only rotate these 120°, it is rather simple to show that you will always find different circumferences, and this is enough to prove that the method is wrong, even if you may approach a lot to the exact answer.

I don't know anything about lisp, maybe I can write a simple metaling algorithm that someone will translate into lisp...

 

[AntonioV]

This method of sectors is wrong

I would say that the approach of antoxac is the less "wrong" among all possible empirical methods.

:

 

[Antosacca]

if you change the sectors, even only by turning these 120°,

:smile:the equation that solves such a circumference (more points and perhaps only a few jaws in the same) is unresolvable, already mentioned above.
Therefore one goes by approximation that described by antoniov that is that of the center of gravity is the only one that raginevolously approaches solution.
ps rotate the tripod produces only a shift in the center of the circumference, which is not contrary to the resolution of the problem.:36_6_6:
with love, antoxac.

 

[AntonioV]

rotating the tripod produces only a shift in the center of the circumference

true, but since the cloud of points is still in place, every shift in the center will produce a new circumference, distinct from the previous: in other words, each new tripod creates a new place of points with a minimum average distance from the cloud.

to minimize the error, you should turn away the triple of 1 degree, thus creating 60 circumferences.

Finally, we should connect among them the 60 centers by means of dye, from which to extract the center of gravity, which will be the center of the final "aurea" circumference.

:

 

[Fulvio Romano]

:smile:the equation that solves such a circumference (more points and perhaps only a few jaws in the same) is unresolvable, already mentioned above.

What what?
an equation is unresolvable only if placed badly.
If the problem admits a solution, there is a mathematical model that finds it. not being able to solve the model means just building it wrong.

to minimize the error, you should turn away the triple of 1 degree, thus creating 60 circumferences.

Finally, we should connect among them the 60 centers by means of dye, from which to extract the center of gravity, which will be the center of the final "aurea" circumference.
:

Sorry... how do you say that in this way the solution is correct?

However, I tried to approach the problem, and it is actually not simple.
I tried the method of lyapunov*, but the formulas are growing. If I find some time to continue, and I can find a solution, I can post it, just as mental exercise, because then I don't know if it will be possible to translate it into lisp.

(*)
Imagine that every point has an energy from the distance from the circumference. If with the lyapunov theorem I can find a point of stability of the system, it will coincide with the circumference we are looking for. Right?

 

[Antosacca]

Imagine that every point has an energy from the distance from the circumference. If with the lyapunov theorem I can find a point of stability of the system, it will coincide with the circumference we are looking for. Right?

found the resulting, which is a carrier, find in fact the center of the dots masses (data points) but what radius do you use? risk surrounding your center with a broken one.
the points of a circumference are scalable and are defined as all those points that are of an equal measure from a point called the center of circumference. We don't understand the problem.
the resolution should be sought in statistics and accuracy depends on the method used, you can delete the most extreme points and/or the most internal ones, etc.
The definition of circumference, the basis of research, is clear.
:3513::3513::3513:

 

[Fulvio Romano]

found the resulting, which is a carrier, find in fact the center of the dots masses (data points) but what radius do you use? risk surrounding your center with a broken one.
the points of a circumference are scalable and are defined as all those points that are of an equal measure from a point called the center of circumference. We don't understand the problem.
the resolution should be sought in statistics and accuracy depends on the method used, you can delete the most extreme points and/or the most internal ones, etc.
The definition of circumference, the basis of research, is clear.
:3513::3513::3513:

Forgive me, but apart from that in my method there is no result, but what do you mean by "precision of the result"?
Besides, the center of the points is not the center of the circumference. for no reason in the world can be.
Imagine having a cloud of points and knowing the circumference that approximates it. now add to the top left some points that have equal distance from the circumference.
Does circumference change? certainly not, but the center of gravity moves to the top left. the center and the center of the circumference are on different planets.

 

[AntonioV]

Sorry... how do you say that in this way the solution is correct?

but I didn't say this at all: I talked about "minimizing" the error, looking for an acceptable approximation.

Moreover, this is not a question of lisp, indeed, suppose that the discussion was started by a user of pro-e or medusa.

It's a fascinating problem because it's not "canonical." Me and my eponymous are trying geometrically, you with lyapunov, but all right, believe me.

:

 

[Giuseppe Mauro]

Mah, maybe I'll get too many mental pimps, but I think it's wrong to approach the problem.

Topogee said something fundamental, and what he found 18 points on a circle.
did not detect 18 points "ad canem penis" and wants to take out a perfect circle.
Now, it's assumed, if you don't have a tool that's comparable to a sarta fettuccia (which is very useful and then we'll see why), that the points detected lie on the circumference, with a deviation derived from the error of the instrument.
How much error do we want to give to a detection tool? If it's topographic (as I imagine from the nick) will we be in the order of 1 per thousand? My laser meter from a tolerance of 3mm out of 100m (I don't think I'm sure if I see it, but this is the declared value)
then I created myself in autocad a 1000 radius circle divided into 18points and randomized with maximum distance 50, then with a error (turned) of well 5% (empty to say that the instrument should lose 5cm each meter, other than meter by tailor).
I created a spline passing through all the points resulting, closed, and from that a region. I demanded the massprop of the region I obtained 2 fundamental data.
One is the centerpiece and one is the area of the symil-circular figure.
I divide the area for lazy and make it the square root. I find the radius of the equivalent area. I need the center of my circle... and voila.

starting from the basic data, 1000 circle with a monstrous error of 5%, I found myself with a radius circle 998.129 (so less than 2 per thousand error) and out of real center of 2,54 (2.5 per thousand error)

we return to the meter from tailor (or even bindella from 20m). as a control element, it is enough to wrap it along the circle (because 'topogee always has a cylindrical object that has found, therefore existing) to obtain, with all the limits of the bindella, a circumference. divided the one for 2pi gets its radius, which can compare with the method of the region.

 

[Antosacca]

But what do you mean by "precision of the result"?

I am indetermination of the solution, so I believe that we must arrive at an average solution.

imagine that every point has an energy

physical center not more geometric.
But we do not extend the discussion too much, antoniov and I have proposed a solution, Roman datti to do and "facci" sti conti to get to your solution that you had previously blinded.
I'd be happy to give you a reason.
affectionately, I apologize for too many facines, as a regulation I have only read now.

 

[Antosacca]

great mauro and this is another solution.

 

[Fulvio Romano]

I actually speak so much, but I have not posted anything yet, instead you have posted something.
However I would like to do some points. because I have not understood what precision it serves, but the methods proposed so far bring a systematic error, which I do not know if it can be tolerated.

1. what juseppe mauro says is just if two basic assumptions are satisfied. that is that the points are equally distributed, and have an average error nothing (which is not guaranteed by all instruments).

2. The fact that he's got an energy is absolutely nothing to do with the center of gravity. the method of lyapunov needs an energy-type objective function to be optimized, and until now I am trying to use the distance of points from the circumference, not from the center, therefore it has nothing to do with the center.

We observe the posted images that should clarify the situation and explain why the proposed methods are now wrong. 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:

image 1
I have a thickening of points at the top right, but these points always identify me the same circumference, I simply kept the instrument on for more time in that area. If the algorithm works well, I should always get the same circumference, instead it seems obvious that the center of the points (with which you try to find the center of the circumference) moves massively to the top left.

image 2
I have no points on the lower half of the circumference. the data to solve the problem there are, but no method proposed until now can find the circumference. Right?

image 3
the smartest method is to divide the cloud into three sectors. the centre of each sector (marked in blue) but does not lie on the circumference. It seems to me quite evident that it is closer to the center, just as the distribution of points is made. therefore this method will systematically produce smaller circumferences than the correct ones.

In short, I think, even if we are in the tolerances required by the problem, we are not really there. You think?