19 Replies Latest reply on Feb 12, 2007 2:01 PM by kglad

# calculating the minimal diameter of a circle engulfing a number of randomply positioned dots

There are a number of dots randomly scattered across the screen. The
coordinates of each dot are known.
What would be the algorithm to calculate the minimal diameter of a circle
engulfing all the dots and the coordinates of its center?

• ###### 1. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
that's not an easy problem unless there are 1,2 or 3 dots.
• ###### 2. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
That's why I am seeking avdice
1 or 2 is trivial, but even 3 is far from trivial.
I wonder if anybody tried to do that to calculate shots group size on
scanned targets - perhaps someone can recommend another Forum?
news:eqnn4f\$5u4\$1@forums.macromedia.com...
> that's not an easy problem unless there are 1,2 or 3 dots.

• ###### 3. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
the solution for 3 dots was known to the ancient greeks and is trivial mathematically. for more dots i would use a min-max algorithm. because the dots are not related to some underlying function but are randomly placed i don't know of any other way to solve this than brute force.

that said the number of calculations required would be on the order of w*h*numDots where w is the width of the allowed region, h is the height and numDots is the number of randomly placed dots.

even flash can handle that number of calculations as long as numDots is not greater than say 10,000.
• ###### 4. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
here's a brute force method:

• ###### 5. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
thanks, I'll try it
news:eqo8l2\$p1b\$1@forums.macromedia.com...
> here's a brute force method:
>
>
>
> numDots = 5;
> xMin = 200;
> xMax = 400;
> yMin = 200;
> yMax = 400;
> tl = this;
> dotA = [];
> centerPt = [];
> minD = 1.5*Math.max(xMax-xMin, yMax-yMin);
> for (var i = 1; i<=numDots; i++) {
> dot = tl.attachMovie("dot", "dot"+i, i);
> dot._x = Math.random()*(xMax-xMin)+xMin;
> dot._y = Math.random()*(yMax-yMin)+yMin;
> dotA.push(dot);
> }
> for (var x = xMin; x<=xMax; x++) {
> for (var y = yMin; y<=yMax; y++) {
> maxD = 0;
> for (var i = 0; i<dotA.length; i++) {
> maxD = Math.max(D(x, y, dotA ._x, dotA._y), maxD);
> }
> if (maxD<minD) {
> minD = maxD;
> centerPt = [x, y];
> }
> }
> }
> function D(x1, y1, x2, y2) {
> return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
> }
>

• ###### 6. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots

news:eqo31f\$iom\$1@forums.macromedia.com...
the solution for 3 dots was known to the ancient greeks and is trivial
mathematically.

If you mean drwing a circle across the three dots, it is indeed well
documented by Pifagor, but it does not solve the problem. If you meant
something else, what is it?

• ###### 7. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
finding the circle with smallest diameter that intersects 3 points was solved in antiquity.
• ###### 8. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots

news:eqq2fb\$s66\$1@forums.macromedia.com...
> finding the circle with smallest diameter that intersects 3 points was
solved in antiquity.
Yes, but the snag is that I need smallest diameter ENCLOSING 3 dots which
often is smaller then smallest diameter that intersects these 3 dots.

• ###### 9. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots

news:eqo8l2\$p1b\$1@forums.macromedia.com...
> here's a brute force method:
>
>
>
> numDots = 5;
> xMin = 200;
> xMax = 400;
> yMin = 200;
> yMax = 400;
> tl = this;
> dotA = [];
> centerPt = [];
> minD = 1.5*Math.max(xMax-xMin, yMax-yMin);
> for (var i = 1; i<=numDots; i++) {
> dot = tl.attachMovie("dot", "dot"+i, i);
> dot._x = Math.random()*(xMax-xMin)+xMin;
> dot._y = Math.random()*(yMax-yMin)+yMin;
> dotA.push(dot);
> }
> for (var x = xMin; x<=xMax; x++) {
> for (var y = yMin; y<=yMax; y++) {
> maxD = 0;
> for (var i = 0; i<dotA.length; i++) {
> maxD = Math.max(D(x, y, dotA ._x, dotA._y), maxD);
> }
> if (maxD<minD) {
> minD = maxD;
> centerPt = [x, y];
> }
> }
> }
> function D(x1, y1, x2, y2) {
> return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
> }
>

If I understood your idea correctly, minD is the mimimal diameter in
question and centerPt are x and y coordinates if the center of the circle.
To see it graphically I added the 6th dot with its width set to minimal
diameter and its coordinates to centerPt[0] and centerPt[1]. The four dots
are OK but the fifth tends to get outside the circle:
numDots = 5;
xMin = 200;
xMax = 400;
yMin = 100;
yMax = 300;
tl = this;
dotA = [];
centerPt = [];
minD = 1.5*Math.max(xMax-xMin, yMax-yMin);

for (var i = 1; i<=numDots; i++)
{
dot = tl.attachMovie("dot", "dot"+i, i);
dot._xscale =dot._yscale =50
dot._x = Math.random()*(xMax-xMin)+xMin;
dot._y = Math.random()*(yMax-yMin)+yMin;
dotA.push(dot);
}

for (var x = xMin; x<=xMax; x++)
{
for (var y = yMin; y<=yMax; y++)
{
maxD = 0;
for (var i = 0; i<dotA.length; i++)
{
maxD = Math.max(D(x, y, dotA ._x, dotA._y), maxD);
}
if (maxD<minD)
{
minD = maxD;
centerPt = [x, y];
}
}
}

circle = tl.attachMovie("dot", "circle", 10);
circle._x=centerPt[0];
circle._y=centerPt[1];
circle._width= circle._height=minD*2;
circle._alpha=50;

function D(x1, y1, x2, y2)
{
return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
PS. What is 1.5 in minD = 1.5*Math.max(xMax-xMin, yMax-yMin) ?

• ###### 10. calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
sorry.. double post edited to nothing
• ###### 11. calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
If follow this correctly (which is by no means guaranteed) you just need to find the largest distance between two of your random dots for the circle diameter, and then find the point between them to get the centre of the circle?

Supply the function with an array of your corrdinates as points
Haven't tested this code, so there may be syntax probs...

• ###### 12. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
you didn't understand it correctly, flatcoat: consider the two points that are separated by maximum distance d. draw your circle.

now draw a circle with RADIUS d centered around each of those points. now pick any point that's within the interior of both large circles and outside the your circle. that point is a counter example to your proposition that all points would lie within your circle.

proving that such points exist requires more than hand waving. but that's pretty straight forward and easy to see with a diagram.
• ###### 13. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
aa, does your dot have registration point at its center?

p.s. 1.5 is larger than sqrt(2) which is a factor that guarantees a circumscribing circle.
• ###### 14. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
just 4 lines of code attaching another dot of right diameter and positioning
it into right place demonstrating your idea?
This is much better proof then a thousand of words.

news:eqqic3\$hsg\$1@forums.macromedia.com...
> you didn't understand it correctly, flatcoat: consider the two points
that are
> separated by maximum distance d. draw your circle.
>
> now draw a circle with RADIUS d centered around each of those points.
now
> pick any point that's within the interior of both large circles and
outside the
> your circle. that point is a counter example to your proposition that all
> points would lie within your circle.
>
> proving that such points exist requires more than hand waving. but
that's
> pretty straight forward and easy to see with a diagram.
>

• ###### 15. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
The most valid point, kglad. I did a tiny dot clip and did not much care
about it's center for it was tiny. But when I used the same clip to blow it
up to big circle, it caused the error. Thanks a lot for being patient.

news:eqqiuf\$igm\$1@forums.macromedia.com...
> aa, does your dot have registration point at its center?

• ###### 16. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
you're welcome.
• ###### 17. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots

"flatcoat99" <webforumsuser@macromedia.com> wrote in message
news:eqqhb2\$goc\$1@forums.macromedia.com...
> If follow this correctly (which is by no means guaranteed) you just need
to
> find the largest distance between two of your random dots for the circle
> diameter, and then find the point between them to get the centre of the
circle?
Not exactly. As kglad pointed out with three circles, there might be dots
outside a circle defined like this. Imagine this Circle with these two most
separated dots one of the left and the other on the right. Then Dot 3
positioned at the top slightly outside the circle. The distance between 3
and 2 or 1 is less than that between 1 and 2, but 3 is not covered by the
Circle.

• ###### 18. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
quote: