How to find the minimum radius circle that fits around a mass?

[george seifert]

I need a few hints please. How can I find the minimum radius circle that fits around a mass? I've enclosed a picture that might help. The red, green and blue circles represent the mass. The white circle is my attempt at this. I used the IMAQ Detect Circles VI (I actually used Greyscale U8 filled black circles to do the detection). As you can see the white circle doesn't quite enclose the other circles. If the circles are closer together it seems to work better. I've played with all the settings on the detection (using NI Vision), but this is the best I can do. Any other ideas on how to go about this? I've only dabbled in this vision stuff. Maybe the vision utilities aren't the best way to do this either.

Thanks,

George

[LAVA 1.0 Content]

QUOTE(george seifert @ Mar 4 2008, 12:23 PM)

I need a few hints please. How can I find the minimum radius circle that fits around a mass? I've enclosed a picture that might help. The red, green and blue circles represent the mass. The white circle is my attempt at this. I used the IMAQ Detect Circles VI (I actually used Greyscale U8 filled black circles to do the detection). As you can see the white circle doesn't quite enclose the other circles. If the circles are closer together it seems to work better. I've played with all the settings on the detection (using NI Vision), but this is the best I can do. Any other ideas on how to go about this? I've only dabbled in this vision stuff. Maybe the vision utilities aren't the best way to do this either.

http://lavag.org/old_files/monthly_03_2008/post-2786-1204651356.jpg' target="_blank">

Thanks,

George

Hi George,

I am not that good with Vison and math is not my strong point. AS usual that will not stop me from thinking out loud.

It seems that the smallest circle would have to enclose the the two points which are farthest from each other. So if you calculat the distance between every pair of points an then locate the largest displacement, then a circle who diameter is equal to the max displacement and centered at the point that mid way between the two extemes.

That's just my non-math 2 cents,

Ben

[george seifert]

QUOTE(neB @ Mar 4 2008, 01:13 PM)

It seems that the smallest circle would have to enclose the the two points which are farthest from each other. So if you calculat the distance between every pair of points an then locate the largest displacement, then a circle who diameter is equal to the max displacement and centered at the point that mid way between the two extemes.

That's just my non-math 2 cents,

Ben

I agree on most of your points, but what exactly constitutes a pair of points? I could eyeball it and find approximately where the max displacement is, but to come up with an algorithm to find it seems rather daunting. You can't just go straight across or up and down. The max could be at any rotation. Let me know if I'm just not getting it.

George

[Francois Normandin]

The best strategy will indeed be of calculating your way through this. Since you have three circles that represent your mass, you have their centers and radii, I assume.

1- Calculate the center of mass (xc, yc) of the whole system. There must be a way to do in Vision. Else, use a ponderated way using the radius of each circle. (A smaller circle would move the center of mass less than a larger circle...)

2- Find the extrema for each directions: i.e. for each circles, calculate the point furthest in each direction. (You need only the four cardinal directions if you're dealing with circles.)

For example:

center of circle1 = (x1, y1) and radius = r1

then left bound = (x1-r1, y1), low bound = (x1, y1-r1), etc.

Calculate for each circles and keep the maximum in each directions.

3-Your minimum radius circle that encompasses all circles will be of the same radius as the maximum distance between the center of mass and any of those bounds.

4- Draw your circle from (xc, yc) with a radius rc = distance between (xc, yc) & largest (xn±rn, yn±rn).

I hope this doesn't sound too complicated...

[eaolson]

QUOTE(normandinf @ Mar 4 2008, 03:22 PM)

The best strategy will indeed be of calculating your way through this. Since you have three circles that represent your mass, you have their centers and radii, I assume.

I don't think normandinf's solution will work, exactly. If you consider the case where R2 is smaller and entirely contained within R1, then the containing circle is obviously centered at (x1,y1) with radius r1. But (xc, yc) != (x1, y1). So you get a circle of the right radius at the wrong location.

If the red and blue circles are indeed known and are actual circles (not thresholded outlines from some measured image, for example), you can also calculate the containing circle directly:

1. Find the line that passes through the centers of both circles.

2. Find the two points where that line passes through the outer edge of the circles. (Did that make sense? There will be four points of intersection with that line, since there are two circles; you want the two that are farthest apart.)

3. Those two points define the diameter of the containing circle.

Easy to do geometrically, but there's some algebra to do for a numerical solution.

[Francois Normandin]

QUOTE(eaolson @ Mar 4 2008, 04:47 PM)

I don't think normandinf's solution will work, exactly. If you consider the case where R2 is smaller and entirely contained within R1, then the containing circle is obviously centered at (x1,y1) with radius r1. But (xc, yc) != (x1, y1). So you get a circle of the right radius at the wrong location.

I somewhat agree with this, except that it was my understanding that the circles are representing the irregular-shaped mass. In such a scenario, Vision will not give a circle completely inscribed in the others...

***EDIT***

Hummm, I think I made an other mistake... Maybe I should rethink again. It seems there's also a problem using cardinal points...

[LAVA 1.0 Content]

My idea fleshd-out a bit.Put all XY pairs describing all points in an array.Delete the first and in a for loop get the distance to the next point. save that distance and taht pair in SR'sCheck distance from first point to the next , compare with previous distance and save set if larger.Continue processing as above until you have found the two point farthest from each other.Use the two extreme points to define a line that they both lie on.Find the point that is half the max distance (found earlier) that lies on the connecting line. That is your center point.I think all of the above is just pethagoreum (sp?) theory and algebra.BenQUOTE(neB @ Mar 5 2008, 06:52 AM)

.See here

Ben

QUOTE(neB @ Mar 5 2008, 06:57 AM)

My idea fleshd-out a bit.Put all XY pairs describing all points in an array.Delete the first and in a for loop get the distance to the next point. save that distance and taht pair in SR'sCheck distance from first point to the next , compare with previous distance and save set if larger.Continue processing as above until you have found the two point farthest from each other.Use the two extreme points to define a line that they both lie on.Find the point that is half the max distance (found earlier) that lies on the connecting line. That is your center point.I think all of the above is just pethagoreum (sp?) theory and algebra.Ben

[LAVA 1.0 Content]

RE: my previous outline...

You will need two nested For loops to get the distance between every possible set of points.

Ben

[rpursley]

How about this.

1. Find Xmin, Ymin, Xmax, Ymax for each smaller circles (Xmin = Xcenter-radius, Ymin=Ycenter-radius, Xmax=Xcenter+radius, Ymax=Ycenter+radius).

2. Use the smallest min values and the largest max values of all of the smaller circles to define a rectangle.

3. Find the center of this rectangle (Ax, Ay). This should be the center of the circle that would encompass all of your circles.

4. Measure the distance from this center (Ax, Ay) to the farthest edge of each circle relative to this point (magnitude of distance from center to center plus radius of each smaller circle.

5. The largest of these measures should be the radius of your encompassing circle.

[LAVA 1.0 Content]

QUOTE(rpursley @ Mar 5 2008, 01:14 PM)

How about this.

1. Find Xmin, Ymin, Xmax, Ymax for each smaller circles (Xmin = Xcenter-radius, Ymin=Ycenter-radius, Xmax=Xcenter+radius, Ymax=Ycenter+radius).

2. Use the smallest min values and the largest max values of all of the smaller circles to define a rectangle.

3. Find the center of this rectangle (Ax, Ay). This should be the center of the circle that would encompass all of your circles.

4. Measure the distance from this center (Ax, Ay) to the farthest edge of each circle relative to this point (magnitude of distance from center to center plus radius of each smaller circle.

5. The largest of these measures should be the radius of your encompassing circle.

I just manually executed those steps and it lloks like that will work. :thumbup:

Ben

[george seifert]

Thanks all for the ideas. I'm busy evaluating them.

I found something that so far looks promising. I used the IMAQ Find Circular Edge VI to define the encompasing circle.Sometimes it seems to hit it right on, other times not quite. In that case I found that if I subtract the mass from the circle found it gives the area that's not covered. I slowly increment the radius of the encompasing circle until the area is 0. I don't know if it's perfect, but visually it looks pretty good.

I'd like to evaluate at least one other method to see if they match.

George

[eaolson]

QUOTE(rpursley @ Mar 5 2008, 12:14 PM)

1. Find Xmin, Ymin, Xmax, Ymax for each smaller circles (Xmin = Xcenter-radius, Ymin=Ycenter-radius, Xmax=Xcenter+radius, Ymax=Ycenter+radius).

2. Use the smallest min values and the largest max values of all of the smaller circles to define a rectangle.

3. Find the center of this rectangle (Ax, Ay). This should be the center of the circle that would encompass all of your circles.

4. Measure the distance from this center (Ax, Ay) to the farthest edge of each circle relative to this point (magnitude of distance from center to center plus radius of each smaller circle.

5. The largest of these measures should be the radius of your encompassing circle.

I think that's close, but not exact. If I understand your description correctly, I don't think the center of that box is guaranteed to be the center of your circle. See attached sketch. Sorry for the poor quality.

I also attached a sketch of what I think will define the minimum containing circle.

[george seifert]

QUOTE(eaolson @ Mar 5 2008, 01:10 PM)

I think that's close, but not exact. If I understand your description correctly, I don't think the center of that box is guaranteed to be the center of your circle. See attached sketch. Sorry for the poor quality.

I also attached a sketch of what I think will define the minimum containing circle.

I think I see how your sketch works with two circles. The center of the encompassing circle has to lie along the line between the two circles, right? I have three circles that I have to encompass and I'm not sure how your method would work in that case.

George

[Francois Normandin]

QUOTE(george seifert @ Mar 5 2008, 02:47 PM)

I think I see how your sketch works with two circles. The center of the encompassing circle has to lie along the line between the two circles, right? I have three circles that I have to encompass and I'm not sure how your method would work in that case.

George

I guess you could iterate eaolsen's solution. Select any two circles of yours and find the circle that encompasses them both. Then repeat using this intermediary solution with your third circle should give a final circle encompassing the three circles. It could even work with "n" circles.

[eaolson]

QUOTE(george seifert @ Mar 5 2008, 01:47 PM)

I think I see how your sketch works with two circles. The center of the encompassing circle has to lie along the line between the two circles, right? I have three circles that I have to encompass and I'm not sure how your method would work in that case.

Oooh, three circles is much harder. If you want an exact solution, it's not straightforward. It sounds like you're talking about http://mathworld.wolfram.com/ApolloniusProblem.html' target="_blank">Apollonius' Problem.

[george seifert]

QUOTE(eaolson @ Mar 6 2008, 09:16 AM)

Oooh, three circles is much harder. If you want an exact solution, it's not straightforward. It sounds like you're talking about http://mathworld.wolfram.com/ApolloniusProblem.html' target="_blank">Apollonius' Problem.

There you go. I figured this problem must have come up somewhere in the math world.

George

[Francois Normandin]

QUOTE(eaolson @ Mar 6 2008, 10:16 AM)

Oooh, three circles is much harder. If you want an exact solution, it's not straightforward. It sounds like you're talking about http://mathworld.wolfram.com/ApolloniusProblem.html' target="_blank">Apollonius' Problem.

:worship: I think I'm not worthy!