14
\$\begingroup\$

Description :

Given x and y positions of two circles along with their radii, output the area of intersection of the two circle.


Input :

You will be given following input :

array 1 = x and y positions of circle a
array 2 = x and y positions of circle b
radius  = radii of the two congruent circles

Input method :

([12 , 20] , [20 , 18] , 12)     ---> two array and number
([12 , 20 , 20 , 18] , 12)       ---> array and a number
(12 , 20 , 20 , 18 , 12)         ---> all five numbers
('12 20' , '20 18' , 12)         ---> 2 strings and a number
('12 20 20 18' , 12)             ---> string and a number
('12 20 20 18 12')               ---> one string

Output :

  • A non-negative integer (no decimal) equal to area of intersection of two circles.

  • A string equal to the above mentioned integer.

Note :

  • Output must be >= 0, since area can't be negative.
  • In case of decimal round down to nearest integer

Examples :

([0, 0], [7, 0], 5)                   ---> 14

([0, 0], [0, 10], 10)                 ---> 122

([5, 6], [5, 6], 3)                   ---> 28

([-5, 0], [5, 0], 3)                  ---> 0

([10, 20], [-5, -15], 20)             ---> 15

([-7, 13], [-25, -5], 17)             ---> 132

([-12, 20], [43, -49], 23)            ---> 0

Winning criteria :

This is so shortest code in bytes for each language wins.


Suggestions :

  • Provide a TIO link so it can be tested.
  • Provide an explanation so others can understand your code

These are only suggestions and are not mandatory.

\$\endgroup\$
  • 4
    \$\begingroup\$ Ravioli, ravioli... \$\endgroup\$ – FrownyFrog Apr 15 '18 at 14:08
  • 2
    \$\begingroup\$ @FrownyFrog: Excuse me ? I am not aware of what you are talking about? nvm check on internet and I am sorry to report that is part of the problem. see the tag that says math and geometry. It is a good excuse to brush up on your math. What do you think. But if you disagree I think I will update the question and add formula. \$\endgroup\$ – Muhammad Salman Apr 15 '18 at 14:11
  • \$\begingroup\$ @MuhammadSalman Change answer must be positive to answer must be >= 0 - If the circles don't intersect (as in examples 4, 7, 10) then the correct answer is 0, which last I checked is not positive. \$\endgroup\$ – manassehkatz Apr 20 '18 at 20:46
  • \$\begingroup\$ @manassehkatz : Ok , sure. Done \$\endgroup\$ – Muhammad Salman Apr 20 '18 at 21:08

12 Answers 12

3
\$\begingroup\$

Jelly,  27 25 24  22 bytes

×,²I½
÷ÆAײ}_çHḞ
ạ/çḤ}

A full program accepting a list of the two centres as complex co-ordinates and the radius which prints the result (as a dyadic link it returns a list of length 1).

Try it online!

To take the two co-ordinates as pairs add Uḅı to the main link, like this.

How?

×,²I½ - Link 1, get [√(s²d² - s⁴)]: separation of centres, s; diameter, d
 ,    - pair = [s, d]
×     - multiply (vectorises) = [s², sd]
  ²   - square (vectorises) = [s⁴, s²d²]
   I  - incremental differences = [s²d² - s⁴]
    ½ - square root (vectorises) = [√(s²d² - s⁴)]

÷ÆAײ}_çHḞ - Link 2, get intersection area: separation of centres, s; diameter, d
÷          - divide = s/d
 ÆA        - arccos = acos(s/d)
    ²}     - square right = d²
   ×       - multiply = acos(s/d)d²
       ç   - call last Link (1) as a dyad (f(s,d)) = [√(s²d² - s⁴)]
      _    - subtract (vectorises) = [acos(s/d)d² - √(s²d² - s⁴)]
        H  - halve (vectorises) = [(acos(s/d)d² - √(s²d² - s⁴))/2]
         Ḟ - floor = [⌊(acos(s/d)d² - √(s²d² - s⁴))/2⌋]
           -  ...Note: Jelly's Ḟ takes the real part of a complex input so when
           -           the circles are non-overlapping the result is 0 as required

ạ/çḤ} - Main link: centres, a pair of complex numbers, c; radius, r
 /    - reduce c by:
ạ     -   absolute difference = separation of centres, s
      -   ...Note: Jelly's ạ finds the Euclidean distance when inputs are complex
      -            i.e. the norm of the difference
   Ḥ} - double right = 2r = diameter, d
  ç   - call last Link (2) as a dyad (f(s,d))
      - implicit print
\$\endgroup\$
  • \$\begingroup\$ numbers only. And what is that [-7+13j,-25+-5j] ? I don't have that example. You might have to explain what you did ? \$\endgroup\$ – Muhammad Salman Apr 15 '18 at 16:18
  • \$\begingroup\$ I explained it in the answer already... they are co-ordinates on the complex plane... I can do [[x1,y1],[x2,y2]] instead but it costs 3 bytes. (Note also that -7+13j is a number :)) -- the [-7+13j,-25+-5j] corresponds to the example that returns 132, [-7, 13], [-25, -5], 17 \$\endgroup\$ – Jonathan Allan Apr 15 '18 at 16:21
  • \$\begingroup\$ I don't know Jelly so I am lost on that. Also I sent the message before the explanation. But yeah , sure this works (I guess?) \$\endgroup\$ – Muhammad Salman Apr 15 '18 at 16:30
  • \$\begingroup\$ It's nothing to do with Jelly per-se, it's just mathematics. A point in 2-space is the same as a complex number. \$\endgroup\$ – Jonathan Allan Apr 15 '18 at 16:36
  • \$\begingroup\$ Not what I meant. Normal languages I would be able to read and tell what is going on. Jelly and other such languages are a pain to read. \$\endgroup\$ – Muhammad Salman Apr 15 '18 at 16:39
3
\$\begingroup\$

Mathematica 66 57 bytes

IntegerPart@Area@RegionIntersection[#~Disk~#3,#2~Disk~#3]&

A Disk[{x,y},r]refers to the region circumscribed by the circle centered at {x,y} with a radius of r.

RegionIntersection[a,b] returns the intersection of regions a, b. Area takes the area. IntegerPart rounds down to the nearest integer.

\$\endgroup\$
  • \$\begingroup\$ For the record, I didn't see alephalpha's submission as I was doing my own. His is a shorter (hence a more successful) entry, but I left mine in anyway. \$\endgroup\$ – DavidC Apr 18 '18 at 17:21
3
\$\begingroup\$

JavaScript (ES6), 72 bytes

Alternate formula suggested by @ceilingcat

Takes input as 5 distinct parameters (x0, y0, x1, y1, r).

with(Math)f=(x,y,X,Y,r)=>-(sin(d=2*acos(hypot(x-X,y-Y)/r/2))-d)*r*r*2>>1

Try it online!


JavaScript (ES7), 81 80 77 bytes

Saved 3 bytes thanks to @Neil

Takes input as 5 distinct parameters (x0, y0, x1, y1, r).

(x,y,X,Y,r,d=Math.hypot(x-X,y-Y))=>(r*=2)*r*Math.acos(d/r)-d*(r*r-d*d)**.5>>1

Try it online!

How?

This is based on a generic formula from MathWorld for non-congruent circles:

A = r².arccos((d² + r² - R²) / 2dr) +
    R².arccos((d² + R² - r²) / 2dR) -
    sqrt((-d + r + R)(d + r - R)(d -r + R)(d + r + R)) / 2

where d is the distance between the two centers and r and R are the radii.

With R = r, this is simplified to:

A = 2r².arccos(d / 2r) + d.sqrt((2r - d) * (2r + d)) / 2

And with r' = 2r:

A = (r'².arccos(d / r') + d.sqrt(r'² - d²)) / 2

Note: If d is greater than 2r, Math.acos() will return NaN, which is coerced to 0 when the right-shift is applied. This is the expected result, because d > 2r means that there's no intersection at all.

\$\endgroup\$
  • \$\begingroup\$ d*(r*r-d*d)**.5 saves 3 bytes. \$\endgroup\$ – Neil Apr 15 '18 at 15:31
  • \$\begingroup\$ @ceilingcat Thanks! Using with(Math) and moving the definition of d saves 2 more bytes. \$\endgroup\$ – Arnauld Apr 17 '18 at 6:20
2
\$\begingroup\$

Wolfram Language (Mathematica), 50 bytes

Floor@Area@RegionIntersection[#~Disk~#3,Disk@##2]&

Try it online!

\$\endgroup\$
  • \$\begingroup\$ +1 Floor. Of course! \$\endgroup\$ – DavidC Apr 16 '18 at 9:37
2
\$\begingroup\$

C (gcc), 83 79 71 66 bytes

f(a,b,c,d,e){float g=cacos(hypot(a-c,b-d)/e/2)*2;e*=(g-sin(g))*e;}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 83 bytes

(k!l)m n r|d<-sqrt$(k-m)^2+(l-n)^2=floor$2*r^2*acos(d/2/r)-d/2*sqrt(4*r*r-d*d)::Int

Just the formula, really. Type has to be declared as Int for NaN to map to 0 with floor.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 69 bytes

with(Math)f=(a,b,c,d,r)=>(-sin(x=2*acos(hypot(a-c,b-d)/2/r))+x)*r*r|0

Try it online!

Short not sure if it can be golfed any further. Any suggestions are welcome

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 56 bytes

{{1>$_&&{$_-.sin}(2*.acos)}(abs($^p-$^q)/2/$^r)*$r²+|0}

Try it online!

Takes circle coordinates as complex numbers.

\$\endgroup\$
0
\$\begingroup\$

Excel, 119 bytes

=INT(IFERROR(2*E1^2*ACOS(((C1-A1)^2+(D1-B1)^2)^.5/2/E1)-((4*E1^2-((C1-A1)^2+(D1-B1)^2))*((C1-A1)^2+(D1-B1)^2))^.5/2,0))

Input taken as 5 separate variables:

x-coordinate    y-coordinate    x-coordinate    y-coordinate    radius
     A1              B1             C1                D1          E1
\$\endgroup\$
0
\$\begingroup\$

Python 2, 109 bytes

from math import*
a,b,x,y,r=input()
d,R=hypot(x-a,y-b),2*r
print int(d<R and R*r*acos(d/R)-d*sqrt(R*R-d*d)/2)

Try it online!

Pretty straightforward. Get the distance between circles, and use R=2r as a substituite in the equation. d<R and to short-circuit if circles don't overlap.

\$\endgroup\$
0
\$\begingroup\$

Pyth, 63 bytes

J@+^-hhQh@Q1 2^-ehQe@Q1 2 2K*2eQs&<JK-**KeQ.tcJK4c*J@-*KK*JJ2 2

Test suite

Takes input as a triple consisting of two doubles and a number.

\$\endgroup\$
0
\$\begingroup\$

T-SQL, 122 bytes

SELECT FLOOR(Geometry::Parse('POINT'+a).STBuffer(r).STIntersection(
             Geometry::Parse('POINT'+b).STBuffer(r)).STArea())FROM t

(line break for readability only).

Uses MS SQL's support of spatial geometry.

Per our IO standards, SQL can take input from a pre-existing table t with int field r and varchar fields a and b containing coordinates in the format (x y).

My statement parses the coordinates as POINT geometry objects expanded by the radius using the function STBuffer(), then taking the STIntersection() followed by the STArea().

If I am allowed to input the actual geometry objects in the table instead, then my code becomes almost trivial (48 bytes):

SELECT FLOOR(a.STIntersection(b).STArea())FROM t
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.