Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Intersection of two Disks

Subject: Intersection of two Disks

From: kamuran turksoy

Date: 5 Oct, 2012 20:33:08

Message: 1 of 9

I have two disks:
C1: (x-a1)^2+(y-b1)^2<=r1^2
C2: (x-a2)^2+(y-b2)^2<=r2^2

These disks have non-empty intersection.

I define the third circle as:
C3: (x-a3)^2+(y-b3)^2<=r3^2 where

a3=a1*(1-t)+a2*t
b3=b1*(1-t)+b2*t
r3=sqrt(a3^2+b3^2-(a1^2+b1^2-r1^2)*(1-t)-(a2^2+b2^2-r2^2)*t)
where 0<=t<=1.

Claim: C3 contains the intersection of C1 and C3 for all values of t such that 0<=t<=1

Numerically when i substitute t values and check it the claim works. However i could not prove it. Any suggestions?

Regards

Subject: Intersection of two Disks

From: Nasser M. Abbasi

Date: 5 Oct, 2012 20:39:23

Message: 2 of 9

On 10/5/2012 3:33 PM, kamuran turksoy wrote:
> I have two disks:
> C1: (x-a1)^2+(y-b1)^2<=r1^2
> C2: (x-a2)^2+(y-b2)^2<=r2^2
>
> These disks have non-empty intersection.
>
> I define the third circle as:
> C3: (x-a3)^2+(y-b3)^2<=r3^2 where
>
> a3=a1*(1-t)+a2*t
> b3=b1*(1-t)+b2*t
> r3=sqrt(a3^2+b3^2-(a1^2+b1^2-r1^2)*(1-t)-(a2^2+b2^2-r2^2)*t)
> where 0<=t<=1.
>
> Claim: C3 contains the intersection of C1 and C3 for all values of t such that 0<=t<=1
>
> Numerically when i substitute t values and check it the claim works.
>However i could not prove it. Any suggestions?
>
> Regards
>


It looks like you got the wrong newsgroup? This is Matlab group,
not geometry. Where is the Matlab question in this?

You might want to try sci.math

--Nasser

Subject: Intersection of two Disks

From: Matt J

Date: 5 Oct, 2012 22:24:09

Message: 3 of 9

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k4ng64$647$1@newscl01ah.mathworks.com>...
>
> Claim: C3 contains the intersection of C1 and C3 for all values of t such that 0<=t<=1
=================

I assume you mean "C3 contains the intersection of C1 and C2"

Fix any x in the intersection of C1 and C2 and let p=[a2, b2]. Also, assume without loss of generality that a1=b1=0. You can always translate space so that one of the circle centers is at the origin without changing the geometry of the intersection.

Under these assumptions, your formula for r3^2 reduces to

r3^2 = |p|^2*t^2+ (r1^2-r2^2-|p|^2)*t+r2^2

and the distance of x from [a3,b3] is

 |x-t*p|^2= |p|^2*t^2 - 2*dot(x,p)*t+|x|^2

We want to show that the r3^2>= |x-t*p|^2 in the interval 0<=t<=1. Considering the above formulas, it is therefore necessary to show that

(r1^2-r2^2-|p|^2)*t+r2^2 - ( - 2*dot(x,p)*t+|x|^2) >=0

is non-negative throughout 0<=t<=1. But the LHS of this equation is linear in t, so it is a simple matter to analyze where it is non-negative.

Subject: Intersection of two Disks

From: Roger Stafford

Date: 13 Oct, 2012 06:57:11

Message: 4 of 9

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k4ng64$647$1@newscl01ah.mathworks.com>...
> I have two disks:
> C1: (x-a1)^2+(y-b1)^2<=r1^2
> C2: (x-a2)^2+(y-b2)^2<=r2^2
>
> These disks have non-empty intersection.
>
> I define the third circle as:
> C3: (x-a3)^2+(y-b3)^2<=r3^2 where
>
> a3=a1*(1-t)+a2*t
> b3=b1*(1-t)+b2*t
> r3=sqrt(a3^2+b3^2-(a1^2+b1^2-r1^2)*(1-t)-(a2^2+b2^2-r2^2)*t)
> where 0<=t<=1.
>
> Claim: C3 contains the intersection of C1 and C3 for all values of t such that 0<=t<=1
>
> Numerically when i substitute t values and check it the claim works. However i could not prove it. Any suggestions?
>
> Regards
- - - - - - - - - -
  Your claim is true, Kamuran. Here is a way to prove it.

  To begin with, if the expressions for a3 and b3 are substituted into the expression for r3^2 and simplification carried out, the result is:

 r3^2 = r1^2*(1-t)+r2^2*t-d^2*t*(1-t)

where d^2 = (a2-a1)^2+(b2-b1)^2, that is, the square of the distance between the two centers.

  This means that the proof can be carried out without reference to the coordinates of the centers. It is a problem in pure geometry. If A and B are the two disk centers with respective radii r1 and r2, and P = A*(1-t)+B*t is any point on the line segment connecting them, then we must prove that a disk with the above radius r3 and center at P will always contain the intersection of the two given disks.

  There are two cases to consider. The first is that the circular perimeters of the first two disks intersect. Call those intersection points C and D. Call E the orthogonal intersection of line CD with (possibly extended) line AB. From the cosine law applied to triangle ABC we have

 AE = (d^2+r1^2-r2^2)/(2*d)

Also

 AP = d*t

and hence

 PE^2 = (AE-d*t)^2

Furthermore since ACE is a right triangle

 CE^2 = r1^2-AE^^2

Also CPE is a right triangle and we finally get

 PC^2 = PE^2+CE^2 = (AE-d*t)^2+r1^2-AE^2 =
 r1^2*(1-t)+r2^2*t-d^2*t*(1-t) = r3^2

The circle of radius r3 passes through both intersection points of the first two circles. This clearly implies that the third disk must contain the intersection of the first two disks.

  In the second case one of the first two disks contains the entire second disk and their perimeters do not intersect. Suppose that the disk of radius r2 contains that of radius r1. Then we must show that for all t in 0<=t<=1 we have r3 >= r1 + d*t. We must have r2 >= r1 + d and therefore

 r3^2-(r1+d*t)^2 = r1^2*(1-t)+r2^2*t-d^2*t*(1-t)-(r1+d*t)^2 =
 (r2^2-(r1+d)^2)*t >= 0.

With the r1 disk containing the r2 disk the proof would be analogous.

Roger Stafford

Subject: Intersection of two Disks

From: Roger Stafford

Date: 15 Oct, 2012 06:55:07

Message: 5 of 9

"Roger Stafford" wrote in message <k5b3c7$gcm$1@newscl01ah.mathworks.com>...
> "kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k4ng64$647$1@newscl01ah.mathworks.com>...
> > I have two disks:
> > C1: (x-a1)^2+(y-b1)^2<=r1^2
> > C2: (x-a2)^2+(y-b2)^2<=r2^2
> >
> > These disks have non-empty intersection.
> >
> > I define the third circle as:
> > C3: (x-a3)^2+(y-b3)^2<=r3^2 where
> >
> > a3=a1*(1-t)+a2*t
> > b3=b1*(1-t)+b2*t
> > r3=sqrt(a3^2+b3^2-(a1^2+b1^2-r1^2)*(1-t)-(a2^2+b2^2-r2^2)*t)
> > where 0<=t<=1.
> >
> > Claim: C3 contains the intersection of C1 and C3 for all values of t such that 0<=t<=1
- - - - - - - - - - - -
  I just realized there is a much simpler proof of your claim than I gave previously. Given your definitions

 a3=a1*(1-t)+a2*t
 b3=b1*(1-t)+b2*t
 r3=sqrt(a3^2+b3^2-(a1^2+b1^2-r1^2)*(1-t)-(a2^2+b2^2-r2^2)*t)

where 0<=t<=1, one can fairly easily establish the algebraic identity

 r3^2-(x-a3)^2-(y-b3)^2 =
 (r1^2-(x-a1)^2-(y-b1)^2)*(1-t) + (r2^2-(x-a2)^2-(y-b2)^2)*t

for all x and y, and there's your proof! If the right side is non-negative then so must be the left side.

Roger Stafford

Subject: Intersection of two Disks

From: Matt J

Date: 15 Oct, 2012 08:08:06

Message: 6 of 9

"Roger Stafford" wrote in message <k5gc0b$imr$1@newscl01ah.mathworks.com>...
>
> I just realized there is a much simpler proof of your claim than I gave previously. Given your definitions
>
> a3=a1*(1-t)+a2*t
> b3=b1*(1-t)+b2*t
> r3=sqrt(a3^2+b3^2-(a1^2+b1^2-r1^2)*(1-t)-(a2^2+b2^2-r2^2)*t)
>
> where 0<=t<=1, one can fairly easily establish the algebraic identity
>
> r3^2-(x-a3)^2-(y-b3)^2 =
> (r1^2-(x-a1)^2-(y-b1)^2)*(1-t) + (r2^2-(x-a2)^2-(y-b2)^2)*t
>
> for all x and y, and there's your proof! If the right side is non-negative then so must be the left side.
==============

That's great, Roger. But it's pretty much the same proof as what I gave on Oct 5.

Subject: Intersection of two Disks

From: Roger Stafford

Date: 15 Oct, 2012 19:21:09

Message: 7 of 9

"Matt J" wrote in message <k5gg96$30k$1@newscl01ah.mathworks.com>...
> That's great, Roger. But it's pretty much the same proof as what I gave on Oct 5.
- - - - - - - - - -
  My apologies, Matt. I did see your reply of Oct. 5 but the roles of your r1 and r2 were, in effect, interchanged with your two disks being defined by:

 (x-a1)^2+(y-b1)^2 <= r2^2 (where a1 = b1 = 0 in your case)
 (x-a2)^2+(y-b2)^2 <= r1^2

as opposed to those of Kamuran and I thought your derivation would therefore turn out to be erroneous, so I gave up studying your explanation. I should have looked at it more carefully. In any case Kamuran should be happy that he now has a plurality of proofs to choose from.

Roger Stafford

Subject: Intersection of two Disks

From: kamuran turksoy

Date: 15 Oct, 2012 19:33:09

Message: 8 of 9

"Roger Stafford" wrote in message <k5hnn5$4bi$1@newscl01ah.mathworks.com>...
> Roger Stafford

As Roger stated, i appreciate for reply of Matt and Roger.

Subject: Intersection of two Disks

From: Matt J

Date: 15 Oct, 2012 19:51:08

Message: 9 of 9

"Roger Stafford" wrote in message <k5hnn5$4bi$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <k5gg96$30k$1@newscl01ah.mathworks.com>...
> > That's great, Roger. But it's pretty much the same proof as what I gave on Oct 5.
> - - - - - - - - - -
> My apologies, Matt. I did see your reply of Oct. 5 but the roles of your r1 and r2 were, in effect, interchanged with your two disks being defined by:
>
===========

No apologies necessary, Roger. Just curious about where I'd failed to convince :-)

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us