This content has been marked as final.
Show 19 replies

1. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
kglad Feb 11, 2007 10:26 AM (in response to Newsgroup_User)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
Newsgroup_User Feb 11, 2007 11:08 AM (in response to Newsgroup_User)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?
"kglad" <webforumsuser@macromedia.com> wrote in message
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
kglad Feb 11, 2007 1:49 PM (in response to Newsgroup_User)the solution for 3 dots was known to the ancient greeks and is trivial mathematically. for more dots i would use a minmax 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
kglad Feb 11, 2007 3:25 PM (in response to kglad)here's a brute force method:

5. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
Newsgroup_User Feb 12, 2007 12:36 AM (in response to kglad)thanks, I'll try it
"kglad" <webforumsuser@macromedia.com> wrote in message
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(xMaxxMin, yMaxyMin);
> for (var i = 1; i<=numDots; i++) {
> dot = tl.attachMovie("dot", "dot"+i, i);
> dot._x = Math.random()*(xMaxxMin)+xMin;
> dot._y = Math.random()*(yMaxyMin)+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((x1x2)*(x1x2)+(y1y2)*(y1y2));
> }
>

6. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
Newsgroup_User Feb 12, 2007 12:39 AM (in response to Newsgroup_User)
"kglad" <webforumsuser@macromedia.com> wrote in message
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
kglad Feb 12, 2007 7:52 AM (in response to Newsgroup_User)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
Newsgroup_User Feb 12, 2007 9:39 AM (in response to Newsgroup_User)
"kglad" <webforumsuser@macromedia.com> wrote in message
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
Newsgroup_User Feb 12, 2007 12:00 PM (in response to kglad)
"kglad" <webforumsuser@macromedia.com> wrote in message
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(xMaxxMin, yMaxyMin);
> for (var i = 1; i<=numDots; i++) {
> dot = tl.attachMovie("dot", "dot"+i, i);
> dot._x = Math.random()*(xMaxxMin)+xMin;
> dot._y = Math.random()*(yMaxyMin)+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((x1x2)*(x1x2)+(y1y2)*(y1y2));
> }
>
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(xMaxxMin, yMaxyMin);
for (var i = 1; i<=numDots; i++)
{
dot = tl.attachMovie("dot", "dot"+i, i);
dot._xscale =dot._yscale =50
dot._x = Math.random()*(xMaxxMin)+xMin;
dot._y = Math.random()*(yMaxyMin)+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((x1x2)*(x1x2)+(y1y2)*(y1y2));
}
PS. What is 1.5 in minD = 1.5*Math.max(xMaxxMin, yMaxyMin) ?

10. calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
macdaddy256 Feb 12, 2007 12:05 PM (in response to Newsgroup_User)sorry.. double post edited to nothing 
11. calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
macdaddy256 Feb 12, 2007 12:05 PM (in response to Newsgroup_User)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
kglad Feb 12, 2007 12:23 PM (in response to Newsgroup_User)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
kglad Feb 12, 2007 12:33 PM (in response to Newsgroup_User)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
Newsgroup_User Feb 12, 2007 12:38 PM (in response to Newsgroup_User)If your code is correct (and I sincerely want it to be) please will you add
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.
"kglad" <webforumsuser@macromedia.com> wrote in message
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
Newsgroup_User Feb 12, 2007 12:51 PM (in response to Newsgroup_User)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.
"kglad" <webforumsuser@macromedia.com> wrote in message
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
kglad Feb 12, 2007 1:23 PM (in response to Newsgroup_User)you're welcome. 
17. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
Newsgroup_User Feb 12, 2007 1:24 PM (in response to Newsgroup_User)
"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
macdaddy256 Feb 12, 2007 1:28 PM (in response to kglad)quote:
Originally posted by: kglad
proving that such points exist requires more than hand waving. but that's pretty straight forward and easy to see with a diagram.
Okay  I'm not waving then, but drowning.
My code needs a constant multiplier to guarantee an encompassing circle.
Sorry to interrupt people... I'll get my coat. 
19. Re: calculating the minimal diameter of a circle engulfing a number of randomply positioned dots
kglad Feb 12, 2007 2:01 PM (in response to Newsgroup_User)lol, flat.