Area of intersection of two circles

The problem is to compute the area of the intersection of two circles of arbitrary radius.

In this post, the trivial cases (no intersection and one circle completely inside the other) are not discussed.

 

Let A be the center of the circle (x0,y0) of radius r0 and B be the center of the other circle (x1,y1) of radius r1.
We want to calculate the area of the green area in the figure 1.

fig1.png
Figure 1: Area to compute

Let’s add two points at the intersections between the two circles, C and D.
The area can therefore be decomposed in two sub-areas A1 and A2 being the left and the right parts of the intersection.
Area = A1 + A2

fig2.png
Figure 2: Sub-areas A1 and A2

The area of each sub-area can be calculated as the difference of the area of the pie and the triangle.
A1 = A_Pie(DAC) - A_{DAC}
A2 = A_Pie(CBD) - A_{CBD}

fig3.png
Figure 3: How to calculate one sub-area

First, A_{Pie}(DAC) and A_{Pie}(CBD).

The area of the pie is proportionnal to the area of the whole circle
and therefore with alpha the angle of the pie you have the following relation:
A_{Pie} * 2\pi = \alpha * A_{circle}
A_{Pie} = \alpha * A_{circle} / {2\pi}
A_{Pie} = \alpha * \pi r^2 / {2\pi}
A_{Pie} = \alpha * r^2 / 2
A_{Pie} = 0.5 * \alpha * r^2

A_{Pie}(DAC) = 0.5 * \widehat{DAC} * r_0^2
A_{Pie}(CBD) = 0.5 * \widehat{CBD} * r_1^2

We have to find the angles now.
\widehat{DAC} = 2 * \widehat{BAC} so we just have to find BAC.
We know all the lengths of the edges of the triangle ABC and therefore
we can calculate its angles with the cosine rule (https://en.wikipedia.org/wiki/Law_of_cosines).

r_0^2 = r_1^2 + AB^2 - 2*r_1*AB*cos(CBA)

The length AB can be calculated simply from the coordinates of A and B
AB = sqrt{(x_1-x_0)^2 + (y_1-y_0)^2}

cos(BAC) = {r_0^2 + AB^2 - r_1^2}/{2*r_0*AB}

\widehat{BAC} = acos({r_0^2 + AB^2 - r_1^2}/{2*r_0*AB})
Similarly,
\widehat{ABD} = acos({r_1^2 + AB^2 - r_0^2}/{2*r_1*AB})

Now we juste have to calculate the area of the triangles and we are done.
Since we already have the length of two sides of the triangle and the angle in-between,
we can use that
A_{DAC} = 0.5 * r_0^2 * sin(\widehat{DAC}) = 0.5 * r_0^2 * sin(\widehat{DAC})
Same for A_{CBD} = 0.5 * r_0^2 * sin(\widehat{CBD})

The demonstration is easy:
Area of a triangle is 0.5 * base * height
here base = 2*r_0*sin(BAC), height = r_0*cos(BAC)
A_{DAC} = 0.5 * 2*r_0*sin(BAC) * r_0*cos(BAC)
A_{DAC} = 0.5 * r_0^2 * 2*sin(BAC)*cos(BAC)
and 2 sin(a) cos(a) = sin(2a) so we finally get the expected result A_{DAC} = 0.5 * r_0^2 * sin(DAC)

fig4
Figure 4: Area of the triangle DAC

We finally have:
A = A1 + A2
A = A_{Pie}(DAC) - A_{DAC} + A_{Pie}(CBD) - A_{CBD}
A = 0.5 * \widehat{DAC} * r_0^2 - 0.5 * r_0^2 * sin(\widehat{DAC}) + 0.5 * \widehat{CBD} * r_1^2 - 0.5 * r_0^2 * sin(\widehat{CBD})

with
\widehat{DAC} = 2 * acos({r_0^2 + AB^2 - r_1^2}/{2*r_0*AB})
\widehat{CBD} = 2 * acos({r_1^2 + AB^2 - r_0^2}/{2*r_1*AB})

Links:
https://stackoverflow.com/questions/4247889/area-of-intersection-between-two-circles
http://mathforum.org/library/drmath/view/54785.html
http://mathworld.wolfram.com/Circle-CircleIntersection.html
This article is mostly inspeared of the explanation on mathforum.

The figures were done with https://www.geogebra.org

Advertisements

A better QTabBar

I had to work with Qt’s QTabBar and found that a few features were missing. So I worked on a reimplementation of it to provide these functionalities.

Added Features:

  • Tabs closable with the mouse middle button.
  • Scrollable tabs to reorder them.
  • Menu to list up the tabs instead of the default ugly arrow buttons.

Results:

Scroll

Menu

Github link

20 interesting links I’ve read in 2014 or that I have to read

The order is totally random.

1. [C, ASM] From Switch Statement Down to Machine Code – This one is really good.

2. [js] Progress bars out of your tab favicons

3. [Maths] Newton, The Ultimate: One Weird Trick To Make You A Mathematical Superhero, which is basically about Newton’s algorithm.

4. [Git] Git In Two Minutes (For A Solo Developer)

5. [Algorithms] How Spelling Correction Algorithms Work

How to Write a Spelling Corrector

6. [Maths] 0x5f3759df – About the Quake Fast inverse square root and similar approximations

7. [Qt, Visual Studio] Qt debug helpers and QString and QByteArray in VisualStudio 2013 Debugger

8. [Python] PEP8 and a nice link about underscores.

9. Let’s build a browser engine!

10. Interesting write-up about singletons

11. [UI] 7 Rules for Creating Gorgeous UI

12. [C++] List of C++ resources

13. [Python, Algorithms] The complete guide to building an image search engine with Python and OpenCV

14. [Algorithms] Damn Cool Algorithms: Levenshtein Automata

15. Hidden Costs of Memory Allocation

16. [CG] A trip through the Graphics Pipeline 2011

17. [Python] Obfuscating “Hello world!”

18. About 2D visibility

19. Important Programming Concepts (Even on Embedded Systems) Part V: State Machines

20. UX CHECK

[Visual Studio 2013] Removing the Source Control

The Microsoft Git Provider may make Visual Studio 2013 slow and consume a lot of CPU.
As the Source Control resets itself to Microsoft Git Provider every time you reboot, a solution is to remove/rename this file:

C:\Program Files (x86)\Microsoft Visual Studio 12.0\Common7\IDE\CommonExtensions\Microsoft\TeamFoundation\Team Explorer\Microsoft.TeamFoundation.Git.Provider.dll

Source: http://www.pavelvasek.com/is-visual-studio-2013-too-slow/

[OpenGL] An understandable explanation of glBlendFunc

I had to use glBlendFunc recently and found the official documentation really hard to understand immediately.
A coworker explained it in a much more understandable way.

So, the signature of glBlendFunc is:

void glBlendFunc(GLenum sfactor, GLenum dfactor);

Let S be the source color (color of one pixel in the source buffer).
Let D be the destination color (color of the corresponding pixel already in the destination buffer).
And let R be the resulting color (color to write in the destination buffer).

Then, we have the simple following equation:

R = sfactor * S + dfactor * D

This equation may become a bit more complex regarding the glBlendFunc parameters, but here is the principle.

Example: glBlendFunc(GL_ONE, GL_ONE_MINUS_SRC_ALPHA);

R = GL_ONE * S + GL_ONE_MINUS_SRC_ALPHA * D

Xy being the y component of the X color,
R = S + (1 – Sa) * D

Rr = Sr + (1 – Sa) * Dr
Rg = Sg + (1 – Sa) * Dg
Rb = Sb + (1 – Sa) * Db
Ra = Sa + (1 – Sa) * Da

Let’s see the case I was working on.
I had to convert an RGBA8 source to an RGBA8 PREMULTIPLIED destination.

Sa * S gives the premultiplied source.
(1 – Sa) * D gives allows alpha blending to the previous value in the destination buffer.

Therefore, R = Sa * S + (1 – Sa) * D
finally giving glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

See also:
glBlendFuncSeparate in order to set a different factor for the RGB and the A components.
glBlendEquation in order to use another equation to compute the resulting color value (R = sfactor * S – dfactor * D for instance).

[GitExtensions] git extensions–syntax error near unexpected token

Original post from : http://mahingupta.com/git-extensionssyntax-error-near-unexpected-token/

Copy just in case.

Problem :

Whenever you use newly installed GitExtensions to pull a repo from remote repo you may face the error below.

Syntax error near unexpected token ‘(‘

Below is the full error log :

“C:\Program Files (x86)\Git\bin\git.exe” push –recurse-submodules=check –progress “origin” refs/heads/master:refs/heads/master
\”C:/Program Files (x86)/GitExtensions/GitCredentialWinStore/git-credential-winstore.exe\” get: -c: line 0: syntax error near unexpected token `(‘
\”C:/Program Files (x86)/GitExtensions/GitCredentialWinStore/git-credential-winstore.exe\” get: -c: line 0: `\”C:/Program Files (x86)/GitExtensions/GitCredentialWinStore/git-credential-winstore.exe\” get’
\”C:/Program Files (x86)/GitExtensions/GitCredentialWinStore/git-credential-winstore.exe\” erase: -c: line 0: syntax error near unexpected token `(‘
\”C:/Program Files (x86)/GitExtensions/GitCredentialWinStore/git-credential-winstore.exe\” erase: -c: line 0: `\”C:/Program Files (x86)/GitExtensions/GitCredentialWinStore/git-credential-winstore.exe\” erase’
fatal: Authentication failed for ‘https://@bitbucket.org//.git/’
Done

Solution :
The problem is syntax error in default gitconfig file. You can find default config file in C:\Users\\gitconfig
Try to find entry below for [credential] section. It looks like below
[credential]
helper = !\\\”C:/Program Files (x86)/GitExtensions/GitCredentialWinStore/git-credential-winstore.exe\\\”

Notice the 3 slashes after ! at the beginning and the 3 slashes at the end of the entry. Remove two unnecessary slashes so it will look like this :

[credential]
helper = !\”C:/Program Files (x86)/GitExtensions/GitCredentialWinStore/git-credential-winstore.exe\”

Go and run your command again, it should work.