# ISO Algorithm to Apply Smallest Circle Problem

jjweimer

Sat, 06/06/2020 - 03:07 pm

Does anyone have an algorithm for the smallest circle problem?

https://en.wikipedia.org/wiki/Smallest-circle_problem

I am trying to improve my analysis for radial profiles. For one case, I want to use an objectively determined (and thereby consistently set) "smallest circle" to fit around any given blob.

I can pre-generate anything that might be using the ImageAnalyzeParticles operation.

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

June 8, 2020 at 05:37 am - Permalink

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.

June 8, 2020 at 05:58 am - Permalink

In reply to Indeed I can find the CoM… by jjweimer

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.

June 8, 2020 at 07:07 am - Permalink

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

June 8, 2020 at 07:17 am - Permalink

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...

June 8, 2020 at 08:02 am - Permalink

In reply to Couldn't you calculate the… by olelytken

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).

June 8, 2020 at 08:23 am - Permalink

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

June 8, 2020 at 08:25 am - Permalink

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.

June 8, 2020 at 08:46 am - Permalink

In reply to olelytken wrote: Couldn… by KurtB

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

June 8, 2020 at 09:31 am - Permalink

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

June 8, 2020 at 10:20 am - Permalink

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.

June 8, 2020 at 10:22 am - Permalink

> 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

June 8, 2020 at 10:39 am - Permalink

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

(sigh)

June 8, 2020 at 12:16 pm - Permalink

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

June 8, 2020 at 12:39 pm - Permalink

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

June 8, 2020 at 01:13 pm - Permalink