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.

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$

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}$

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)$

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})$

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

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

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.

• 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:

The order is totally random.

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

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

5. [Algorithms] How Spelling Correction Algorithms Work

How to Write a Spelling Corrector

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

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

17. [Python] Obfuscating “Hello world!”

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

[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);

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)/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/&#8217;
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.

[Eclipse ADT] – Not generating any source file while trying to generate an activity

Creating a new Android Application Project or a simply a new activity did not generate any source file.

Solution :
http://stackoverflow.com/a/18852984

1. Click Help > Install New Software.
2. In the Work with field, enter: https://dl-ssl.google.com/android/eclipse/
3. Select Developer Tools / Android Development Tools.
4. Click Next and complete the wizard.

[C++] Playing with references and types can be hazardous

Well, working on my own Game Engine this week-end, I lost like 5 hours of my life debugging it … and finally, I found that I played with references and types without paying enough attention at it.

inline static bool loadDouble(const QJsonObject& qJsonObject, const char* valueName, quint32& out_int) {     double d;     bool res = loadDouble(qJsonObject, valueName, d);     out_int = d;     return res; }

This resulted in writing the end of the d double outside of the out_int quint32.
Simply casting the double solved the overflow.

inline static bool loadDouble(const QJsonObject& qJsonObject, const char* valueName, quint32& out_int) {     double d;     bool res = loadDouble(qJsonObject, valueName, d);     out_int = (quint32)d;     return res; }