minimum circel (sphere) enclosing some points lazarus / 21-General ---------------------------------------------------------------------- Paolo · 2021-02-07 17:45 Dear all, we are looking for a code that allows to calculate the minimum radius sphere enclosing some given points. here a link for a solution for the case of smallest radius circle to start the discussion. http://delphiforfun.org/Programs/circle_covering_points.htm ---------------------------------------------------------------------- 440bx · 2021-02-07 18:16 At first blush, it would seem the method in the link you provided could be extended to 3D.  The how is not obvious but, it intuitively seems possible. I'll be giving that some thought. ---------------------------------------------------------------------- Paolo · 2021-02-07 20:08 @jamie, no, this time is for real application. ---------------------------------------------------------------------- speter · 2021-02-08 01:44 G'Day Folks, I am sticking to 2D (rather than 3d), since I don't think working in 2D really changes the problem. Quote from: speter on February 07, 2021, 11:39:29 amQuote from: Paolo on February 07, 2021, 11:29:11 am... find the minimum sphere enclosing some given points ...Easy (famous last words ) calculate the "extents" (min/max enclosing cube(?)) that gives you the centre; calculate the dist from the centre to each of the points and the max-dist is your radius. I can now tell you (surprise! ) that my earlier thoughts were way off the mark! As you can see from my screenshot, while the circle does enclose the points; it is not minimal. I've attached my project. If it's helpful, please feel free to use it to demonstrate _your_ method. To use it, simply replace all the contents of TForm1.Button1Click(Sender: TObject);  (except the lines below): Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i begin  midpt.setv(0.0,0.0);  maxradius := 0; ...   // set the circle  circle.setv(midpt, maxradius);  circle.cen.canv := paintbox1.canvas;   // show some output :)  memo1.append(circle.tostring);  paintbox1.invalidate;end; If you do this; simply set midpt and maxradius: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   midpt.setv(calcX, calcY);     // <<< where calcX, calcY & calcR are your results  maxradius := calcR;         FYI, my project uses 10 random coord pairs (ranging from 0 to 1): Code: [Select]  coords : array [1..10,1..2] of double = (     (0.88, 0.23),     (0.75, 0.63),     (0.85, 0.92),     (0.92, 0.98),     (0.50, 0.05),     (0.38, 0.58),     (0.83, 0.43),     (0.31, 0.21),     (0.69, 0.23),     (0.22, 0.42) ); These might be useful, so we can compare results. cheers S. ---------------------------------------------------------------------- speter · 2021-02-08 02:46 Here is a "brute-force" method: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure TForm1.Button1Click(Sender: TObject);var  a,b,c,d : tdpt;  cc : tcircle;  ok : boolean;begin  // initialise  circle.setv(0.0,0.0, 1000.0, paintbox1.canvas);   for a in pts do    for b in pts do      for c in pts do        if not a.SameAs(b) and not a.SameAs(c) and not b.SameAs(c) then          begin            cc.setv(a,b,c, paintbox1.canvas);            if cc.r < circle.r then              begin                ok := true;                for d in pts do                if not d.SameAs(a) and not d.SameAs(b) and not d.SameAs(c) then                    if not cc.inside(d) then                      begin                        ok := false;                        break;                      end;                 if ok then                begin                    circle.cen.x := cc.cen.x;                  circle.cen.y := cc.cen.y;                    circle.r := cc.r;                end;              end;          end;   // show some output :)  memo1.append(circle.tostring);  paintbox1.invalidate;end; I added two three methods to my utility units:   function tcircle.inside(p : tdpt) : boolean and   function tdpt.DistTo(p : tdpt) : double   function tdpt.SameAs(p : tdpt) : boolean I think the result is the minimal enclosing circle. The results = centre: (0.72, 0.51), radius: 0.51 (using the 10 points I posted before). I'll be interested to see whether anyone finds a 'better' way... cheers S. ---------------------------------------------------------------------- winni · 2021-02-08 10:30 Hi! Make it simple. Compute the radius of all given points assuming that the center is 0/0/0: R1^2 = X1^2 +y1^2 +z1^2; R2^2 = x2^2 + y1^2 + z2^2; .... The maximimum of R1, R2, ..... is the solution. Done. Winni ---------------------------------------------------------------------- MathMan · 2021-02-08 11:35 @Paolo "bounding ball", "bounding sphere", "bounding volume" have been studied to some larger extend for some time now. Unfortunately the algorithms for exact solutions are not polynomial with rising dimensionality d. For d=3 they may still suffice. There have also been some (1+epsilon) approximating algorithms developed (latest seems to be from 2008). Take a look at wikipedia under "bounding sphere" and you'll find a short historic summary plus links to research and papers. You can then take it up from there. @440bx Transition from 2D to 3D is unfortunately not as trivial as it seems in this case. MathMan ---------------------------------------------------------------------- 440bx · 2021-02-08 17:36 Quote from: MathMan on February 08, 2021, 12:35:30 pm@440bx Transition from 2D to 3D is unfortunately not as trivial as it seems in this case. MathMan I agree with that, I don't think it's trivial at all.  Wikipedia references a number of solutions that may be interesting to @Paolo at https://en.wikipedia.org/wiki/Bounding_sphere I think they are definitely worth a look. ---------------------------------------------------------------------- VTwin · 2021-02-08 20:09 Quote from: winni on February 08, 2021, 11:30:10 amassuming that the center is 0/0/0: Unfortunately, that is not a valid assumption. ---------------------------------------------------------------------- speter · 2021-02-09 01:33 I've extended my 2D solution into 3D; mainly because I realised I didn't have any code to calculate the centre of a sphere given 3 points - so I wanted to work that out. The program has no graphics, so is much simpler than the 2D version. I check the result by calculating the distance from each point to the centre. Once again, this is a brute force approach (basically identical to my 2D version); there are probably more efficient algorithms, but (given the speed of current computers) the answer comes along quickly. cheers S. ---------------------------------------------------------------------- Paolo · 2021-02-09 16:06 @mathMan, yes I know, my topic was a littel provocative. This kind of search for optimal solution was needed for my application, but my fortune, at that time,  was that, due to the physics of the HW, the points are well aligned in one directi, let me say X-direction, so the minmal sphere was extremly close to the sphere with diameter = max-X-min-X value in such direction. But, for curiosity still looking for "real" optimal solution, or viable sub-optimal solution... ---------------------------------------------------------------------- winni · 2021-02-09 21:51 Hi! Not even midnight and I got a solution: We use 3 random points P1,P2,P3 in the universe. The three points should fit into a minimum sphere. Here we go: We define our base Z  plane with z1,z2,z3 Now we can drop the z dimesnsion You can look at it like we use one of the ∞ Great Circles Now we can reduce the problem to a 2D triangle To get the minimum radius we want the 3 points to reside on a circle which is the GREAT circle of the sphere We connect the 3 points and build the center of the lines The perpendicular bisectors cross at the 2D center point Compute the distance between the center and a point: The RADIUS - 2D and 3D Back to 3D: We connect the 3 3D points and build the center of the lines The perpendicular 3D bisectors cross at the 3D center point Done Winni ---------------------------------------------------------------------- VTwin · 2021-02-10 16:20 Nice, but the 2D algorithm does not check for circles defined by two points. The attached shows an example were it fails. For 3D, you need to check for spheres defined by 2, 3, and 4 points. Using the convex hull instead of the full data set would speed things up. There are a number of implementations of algorithms in the Wikipedia link, such as: https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html (C++) https://github.com/marmakoide/miniball (Python) https://github.com/AntonSemechko/Bounding-Spheres-And-Circles (MATLAB) This reference compares some algorithms, both exact and approximate: https://ep.liu.se/ecp/034/009/ecp083409.pdf ---------------------------------------------------------------------- Paolo · 2021-02-10 16:28 Thank you VTwin, for the links ---------------------------------------------------------------------- Paolo · 2021-02-10 16:37 @440bx in the link you give me there is the idea I had, thanks for this link. ---------------------------------------------------------------------- winni · 2021-02-10 17:47 Quote from: VTwin on February 10, 2021, 05:20:30 pmNice, but the 2D algorithm does not check for circles defined by two points. The attached shows an example @VTwin ????? Are you trying to be funny? For two points the algorithm is really simple: Take the mid of the two points for all three dimensions. That is the center point. The distance from the center to one point is the radius. Done. Winni ---------------------------------------------------------------------- VTwin · 2021-02-10 18:41 I do not mean 2 data points, for that the solution is trivial as you say. speter's example has 10 data points. His 2D algorithm examines all circles defined by 3 points. As the image I posted shows, sometimes the solution will be a circle defined by 2 points. His algorithm does not look for them. ---------------------------------------------------------------------- 440bx · 2021-02-10 21:45 Quote from: Paolo on February 10, 2021, 05:37:30 pm@440bx in the link you give me there is the idea I had, thanks for this link. My pleasure.  @Mathman deserves credit too because he mentioned there were solutions out there ---------------------------------------------------------------------- VTwin · 2021-02-10 22:46 Quote from: winni on February 09, 2021, 10:51:53 pmNow we can drop the z dimesnsion You can look at it like we use one of the ∞ Great Circles If you drop the Z dimension that gives an orthographic projection. An orthographic projection onto the XY plane of a 3D circle is only a circle if all the Z coordinates are equal, otherwise it is an ellipse. However, perhaps I misunderstand you. Can you write some code to illustrate your method? ---------------------------------------------------------------------- speter · 2021-02-10 23:01 Quote from: VTwin on February 10, 2021, 07:41:30 pm... speter's example has 10 data points. His 2D algorithm examines all circles defined by 3 points. As the image I posted shows, sometimes the solution will be a circle defined by 2 points. His algorithm does not look for them. Nice work! ---------------------------------------------------------------------- VTwin · 2021-02-10 23:10 Quote from: speter on February 11, 2021, 12:01:45 amQuote from: VTwin on February 10, 2021, 07:41:30 pm... speter's example has 10 data points. His 2D algorithm examines all circles defined by 3 points. As the image I posted shows, sometimes the solution will be a circle defined by 2 points. His algorithm does not look for them. Nice work! Thanks, I enjoyed looking at your solution. You can surely patch your code to expand the search and fix this. However, I would probably translate one of the algorithms available on the web, probably the MATLAB one following Welzl. It is an interesting problem. The paper I linked shows how much speed can be gained by  accepting an approximate solution. ---------------------------------------------------------------------- winni · 2021-02-10 23:12 Quote from: VTwin on February 10, 2021, 11:46:57 pmQuote from: winni on February 09, 2021, 10:51:53 pmNow we can drop the z dimesnsion You can look at it like we use one of the ∞ Great Circles If you drop the Z dimension that gives an orthographic projection. An orthographic projection onto the XY plane of a 3D circle is only a circle if all the Z coordinates are equal, otherwise it is an ellipse. However, perhaps I misunderstand you. Can you write some code to illustrate your method? Hi VTwin! No, we do no projection at all in this moment. That is our first step. We have not calculated a circle in this moment. We "cut" the  universe in that way, that all 3 points reside exact on this plane. Now the Z value of all three points is zero and you can neglect it. As I said: You can look at it like you cut those three points exact along a great circle. There are enough of them. Around ∞. Now we go on the hunt for the circle. The Z axis comes only again in the last step into the game. Got it? Winni ---------------------------------------------------------------------- VTwin · 2021-02-10 23:38 Winni, Quote from: winni on February 11, 2021, 12:12:04 amWe "cut" the  universe in that way, that all 3 points reside exact on this plane. Now the Z value of all three points is zero and you can neglect it. If you want to get all Z to zero, you have to rotate the points so they are. Ignoring Z does not work. Quote from: winni on February 11, 2021, 12:12:04 amGot it? Sorry, no. Please post some working code. Thanks, VTwin ---------------------------------------------------------------------- winni · 2021-02-10 23:43 Hi VTwin! Just a simple 2-point example: If you put 0/0/0 in th middle of the earth for a x/y/z system, then it is obvious that for one axis both Northpole and Southple are zero. That is our  agreement, but it is totaly arbitrary. If you look from the sun to the earth with 0/0/0 in the middle of the sun, you say: Northpole and Southpole of the earth are never at zero for one axis. And indeed you have to change the cordinate system for 23.4....° degrees - the ecliptic (Changes every day). Now you got it again: Both poles with the value of zero for one axis. So the position and the angle of the three axis is just man made und you can put it everywhere. (If it makes sense). Winni ---------------------------------------------------------------------- VTwin · 2021-02-11 00:08 @winni The north pole, assuming a spherical Earth, is in direction cosines (0, 0, 1). The south pole is (0, 0, -1). What does this have to do with the problem at hand? Please post some code. ---------------------------------------------------------------------- speter · 2021-02-11 00:16 Following from VTwin's post, I've rewritten my 3D algorithm to check spheres based on 2 points (and then spheres based on 3 points); and am using 10 points based on VTwin's set of 2D points. Still no graphics! I am tempted to add a "export scene" button to export a 3d scene compatible with the Perspective program I posted last year https://forum.lazarus.freepascal.org/index.php/topic,52526.m sg387685.html#msg387685); but have other things to do. cheers S.  EDIT: LoL I have a typo in the screenshot (readius means radius) ---------------------------------------------------------------------- ArtLogi · 2021-02-11 09:11 Nice. Nothing new I assume follows, I'm just office bounded waiting that IT- device will get the work done. So something needs to be done for personal boredom. I'm not sure, but doesn't this problem can be split to two or three different steps. 1. Pattern recognition of the given nodes 2. Boundary rules (min. radius / tightness) for given group of nodes 3. Sphere fit (by rules or heuristic) IIRC. The minimum radius (for circle and sphere is) the distance of two furthest nodes divided by 2. This is the minimum condition / tightness. On this line there is the origin, if used. -> Most Vertexes are found perpenticularly of this line there is most possibly vertexes? For three points the minimum radius would be discovered by fitting isoscele right triangle. -> Lenght of the cathetus would be the maximum distance possible for two points (outer most points are only ones interest is in). -> Always the distance closest to cathetus lenght is desired between given two points. For four points the minimum radius would be discovered by fitting square. For five points the minimum radius would be discovered by fitting pentagon ... What was my brains after, dunno it got lost. Rules for nodes of interest I think.  How the rule for origin offset would go in worst case with three notes, hmmm...  ...Ok this is rather boring and repetitive. More interesting question would be how to fit as many dots as possible to circle in one cloud if the dots can be outside or inside of the circle. ---------------------------------------------------------------------- Paolo · 2021-02-11 13:34 Tanks to all for the links and suggestions. In the attached doc my propsed strategy that up to now i hadn't time to try to code (but it seems in line with Fischer approach). Any comment is appreciated,  even counter example demonstrating tha cannot work properly. ---------------------------------------------------------------------- olly · 2021-02-12 18:03 Some pascal(ish) code here. Shouldn't be too hard to convert to FPC. TCircle is record X,Y,Radius: Int32; end; https://github.com/SRL/SRL/blob/master/shared/types/TPointArray.simba# L833 ---------------------------------------------------------------------- Paolo · 2021-02-12 18:18 Thanks, is there a "demo" of this code to see how it works ? ---------------------------------------------------------------------- olly · 2021-02-13 08:10 Your lucky day! See attachment. ---------------------------------------------------------------------- Paolo · 2021-02-13 16:53 thanks.