Thread Subject:

How to constrain disks that intersection of them is inside unit circle

I have two disks (x?a1)^2+(y?b1)^2?r1^2 and (x?a2)^2+(y?b2)^2?r2^2, where a1, b1, r1, a2, b2, r2 are all known. What kind of constraint can I put on ai, bi and ri that the intersection of two disks is inside unit circle? The question is for intersection of two disks, but the generalization for n disks would be even better.

Regards

===============

Sorry for missing symbols, the question is corrected as:

I have two disks (x-a1)^2+(y-b1)^2<=r1^2 and (x-a2)^2+(y-b2)^2<=r2^2, where a1, b1, r1, a2, b2, r2 are all known. What kind of constraint can I put on ai, bi and ri that the intersection of two disks is inside unit circle? The question is for intersection of two disks, but the generalization for n disks would be even better.

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k1uot5$sqq$1@newscl01ah.mathworks.com>...
> ===============
>
> Sorry for missing symbols, the question is corrected as:
>
> I have two disks (x-a1)^2+(y-b1)^2<=r1^2 and (x-a2)^2+(y-b2)^2<=r2^2, where a1, b1, r1, a2, b2, r2 are all known. What kind of constraint can I put on ai, bi and ri that the intersection of two disks is inside unit circle? The question is for intersection of two disks, but the generalization for n disks would be even better.
===============

If ai,bi, ri are known and given, I don't see what kind of constraints you can place on them.
However, if we treat them as variables, one way would be to force all of these disks to lie completely inside the unit circle:

0<=ri<=1
norm([ai,bi])^2<=(1-ri)^2

"Matt J" wrote in message <k1vl6q$scl$1@newscl01ah.mathworks.com>...
>
> 0<=ri<=1
> norm([ai,bi])^2<=(1-ri)^2

=============================

You are write i shouldn't wrote that they are known. As you said they are variable. However the solution that you are saying is too conservative. I do not need all disks lie inside unit circle. Only intersection are would be sufficient for me.

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k1vvmf$2nl$1@newscl01ah.mathworks.com>...
>
> You are write i shouldn't wrote that they are known. As you said they are variable. However the solution that you are saying is too conservative. I do not need all disks lie inside unit circle. Only intersection are would be sufficient for me.
===============

Finding the minimum conditions for that would be much harder. I don't think you're going to be able to do that tractably. Maybe if you describe the problem a bit more, the NG can assess whether it's something you really need.

"Matt J" wrote in message <k20fb3$mhq$1@newscl01ah.mathworks.com>...
>
> Finding the minimum conditions for that would be much harder. I don't think you're going to be able to do that tractably. Maybe if you describe the problem a bit more, the NG can assess whether it's something you really need.

Actually i already described the big part of the problem. Let me explain with more details.
 I have an objective function that function of ai, bi and ri. I want to minimize this objective function such that the intersection of disks that i wrote above, is inside unit circle. It is a constrained optimization problem.

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k20hk7$em$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <k20fb3$mhq$1@newscl01ah.mathworks.com>...
> >
> > Finding the minimum conditions for that would be much harder. I don't think you're going to be able to do that tractably. Maybe if you describe the problem a bit more, the NG can assess whether it's something you really need.
>
> Actually i already described the big part of the problem. Let me explain with more details.
> I have an objective function that function of ai, bi and ri. I want to minimize this objective function such that the intersection of disks that i wrote above, is inside unit circle. It is a constrained optimization problem.
==============

Yes, but why do you want to do this? What motivates this problem? What is the application behind it? Maybe the thing you want to do is unnecessarily difficult.

"Matt J" wrote in message <k2287r$ojm$1@newscl01ah.mathworks.com>...
>
> Yes, but why do you want to do this? What motivates this problem? What is the application behind it? Maybe the thing you want to do is unnecessarily difficult.

It is a part of a research problem. There is nothing unnecessary here. This is the exact condition that i am looking for.I am not allowed to give more details about the application behind it. Thanks for your concern.

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k22q00$mbq$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <k2287r$ojm$1@newscl01ah.mathworks.com>...
> >
> > Yes, but why do you want to do this? What motivates this problem? What is the application behind it? Maybe the thing you want to do is unnecessarily difficult.
>
> It is a part of a research problem. There is nothing unnecessary here. This is the exact condition that i am looking for.
================

That's unlikely. It's the inevitable nature of research that the approach you chose is typically sub-optimal. Otherwise, no one would typically ever be able to improve upon another's research.

Anyway, here's a weaker condition than what I gave before: constrain only 1 of the ai,bi,ri to lie inside the unit circle. If only of the circles is completely contained in the unit circle, its intersection with other circles must be as well.

 

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k1uo8k$qjd$1@newscl01ah.mathworks.com>...
> I have two disks (x?a1)^2+(y?b1)^2?r1^2 and (x?a2)^2+(y?b2)^2?r2^2, where a1, b1, r1, a2, b2, r2 are all known. What kind of constraint can I put on ai, bi and ri that the intersection of two disks is inside unit circle?

Define D1 and D2 as two discs, and C1 and C2 the associated circles
D1 := { X : |X-Y1| <= r1 }
D2 := { X : |X-Y2| <= r2 }
C1 := { X : |X-Y1| = r1 } = boundary of D1
C2 := { X : |X-Y2| = r2 } = boundary of D2.

Let (Y1) and (Y2) are the centers of D1 and D2 and (E1) and (E2) are extreme points

Y1 has coordinates [a1,b1]'
Y2 has coordinates [a2,b2]'
E1 := Y1 * (1+r1/|Y1|)
E2 := Y2 * (1+r2/|Y2|).

It is easy to see |E1| = |C1|+r1 and |E2| = |C2|+r2.

Define A := D1 intersects D2.
We want to know if A is included in B(0,1) the unit disc. Let denote this constraint as (c).

Let compute the intersection of the 2 circles C := C1 intersects C2.

If there is no intersection ( C is empty), then either of these 3 cases:
  a) D1 is included in D2. In this case, (c) is true if and only if |E1| <= 1;
  b) Similarly, if D2 is included in D1, (c) is true if and only if |E2| <= 1;
  c) otherwise D1 and D2 are disjoint, then (c) is always true.

If there is are two intersections P1 and P2 then consider case d).
  d) C = { P1, P2 }. Let define the set of points S as:
     S := C union E, where E := { E1, E2 } intersect A.
S is a discrete set having 2 to 4 points. It can be enumerated by simple calculation.

I claim that (c) is true if and only of S is includes in the unit disc. The later is the constraint that can be easily written by Matlab. Indeed, compute P1 and P2 is relatively easy (see below), and check if E1 and E2 belong to A by simple test.

So here is the code for constraint of two discs:

Y1 = [a1; b1];
Y2 = [a2; b2];
E1 = Y1 * (1+r1/norm(Y1));
E2 = Y2 * (1+r2/norm(Y2));

dY= Y2-Y1;
N = [-dY(2); dY(1)];
d = norm(dY);
dr2 = (r1^2-r2^2);
d1 = 0.5*(dr2/d+d);
d2 = 0.5*(-dr2/d+d);
h2 = r1^2-d1^2;
h = sqrt(h2);
P1 = Y1 + d1/d*dY + h/d*N;
P2 = Y1 + d1/d*dY - h/d*N;

inside = (h2>0 && ( norm(P1)<=1 && norm(P2)<=1 && ...
                    (norm(E1)<=1 || norm(E1-Y2)>r2) && ...
                    (norm(E2)<=1 || norm(E2-Y1)>r1))) || ... % case d
         (h2<0 && d>r1+r2) || ... % case c
         (h2<0 && d<r1+r2 && r1<r2 && norm(E1)<=1) || ... % case a
         (h2<0 && d<r1+r2 && r2<r1 && norm(E2)<=1) % case b

Horrible, isn't it? And that happens already with just 2 discs.

Bruno