ISO Algorithm to Apply Smallest Circle Problem

JJ,

I admit to not reading the article referenced... but does it make sense to find the "center of mass" of the distribution and set the radius as the farthest point away form the CoM?  Sounds simple like this, but probably not in practice.

Jeff

Indeed I can find the CoM values rather nicely.

As near as I can now tell, the smallest radius values require meeting two constraints. One is that the circle cannot cross inside the boundary and the other is that it must touch at least two outermost points on the boundary, with the two points being separated by a line segment through the body.

I keep hoping for an insight in some other frame that might collapse the two constraints into one.

I can't give you any formal mathematics, but just thinking about it I think there are two types of solution.

1. The solution is a circle that touches just two points, the line joining these points being a diameter of the circle.

2. The solution is a circle that touches three (or more, but more is unnecessary) points. These three points define a single solution, the centre of the circle being the intersection of the bisectors of the lines joining two pairs of these points.

So, for an algorithm, if there are many points I would first try to remove those that lie inside triangles formed from joining any three points. One would then (hopefully) be left with a small set of points to test all combinations of 1 and 2 to arrive at a solution.

I have no doubt that there is a far more elegant (efficient) solution out there, but this is one (I think) I can understand. 

Yes. I think this two or three point trial and error approach is where I will eventually land.

Couldn't you calculate the distance between all the points as an NxN matrix. The two points that are the furthest apart will be touching the circle. Now you just need to figure out if a third point is needed to define the circle... How to figure that out.... Something involving the distance of the other points to those two points...

olelytken wrote:

Couldn't you calculate the distance between all the points as an NxN matrix. The two points that are the furthest apart will be touching the circle. Now you just need to figure out if a third point is needed to define the circle... How to figure that out.... Something involving the distance of the other points to those two points...

I'm not sure that works...

Imagine three points forming an equilateral triangle. These define a circle. Now start at one of these points and head across the diameter of the circle but stop just before you touch the opposite side. The distance between these points is just under 2 x r (where r is the radius), whereas the separation between each the three points that sit on the circle (that formed the equilateral triangle) are sqrt(3).r (=1.732 x r) apart (if my math is correct).

What about altering find the maximum pair distance as above, you then find the third point by looking at the sum of the distance of the remaining points to the maximum pair and inspect that one.

Take the idea for what's it worth with the caveat I have had only one coffee thus far.

Andy

I have the code to get the three points on the triangle (and will post later once it is fully operational).

I'm onward to the problem to obtain the bisectors to two line segments.

KurtB wrote:

 

olelytken wrote:

 

Couldn't you calculate the distance between all the points as an NxN matrix. The two points that are the furthest apart will be touching the circle. Now you just need to figure out if a third point is needed to define the circle... How to figure that out.... Something involving the distance of the other points to those two points...

 

 

I'm not sure that works...

Imagine three points forming an equilateral triangle. These define a circle. Now start at one of these points and head across the diameter of the circle but stop just before you touch the opposite side. The distance between these points is just under 2 x r (where r is the radius), whereas the separation between each the three points that sit on the circle (that formed the equilateral triangle) are sqrt(3).r (=1.732 x r) apart (if my math is correct).

You're right. My idea doesn't work.

@KurtB -- The math for an non-equilateral triangle is a bit more complicated.

I scanned that link (that means, I didn't read it for understanding of the O(N) algorithm). But one thing is clear- obvious algorithms (is there something "obvious" about this problem?) will tend to be O(N^3). For a small number of points, that's not really a problem. But for image-sized numbers of points, it can build up very quickly. Be careful.

> Be careful. ...

Yes. I quickly realized that searching for three (opposing) largest-separation points over an entire particle boundary could be exceptionally time consuming. So to be careful also in this case means to be clever or, to be specific, to thank goodness for Resample/DOWN and MultiThread.

Now if I can just get the algorithm to obtain the circumcenter of three points, I have my answer.

https://www.varsitytutors.com/hotmath/hotmath_help/topics/bisectors-in-…

EDIT ... BINGO!

https://www.ics.uci.edu/~eppstein/junkyard/circumcenter.html

So, after all this work, I discover the BoundingBall operation.

(sigh)

Hi,

I know that feeling. Searching is great only when you can phrase the query with enough precision and specificity.  On a side note, I am working on tools and methods for improved R&D (mostly around materials) and one of things I have come to believe is that we need ways to browse our data in addition to search.  I am working on those problems at the moment.

Andy

Even I forgot about BoundingBall! You might have found it if it were BoundingCircle, but then what if you really want the sphere?