Calculating the intersection area of 3 or more circles(benfrederickson.com)
benfrederickson.com
Calculating the intersection area of 3 or more circles
http://www.benfrederickson.com/calculating-the-intersection-of-3-or-more-circles/
6 comments
Author here. I wrote this post a while back, but never submitted to HN. Its one of those posts that I wasn't sure if it would really resonate with anyone (like my most recent one on venn diagram layout algorithms).
Anyways, If you have any questions ask away =).
Anyways, If you have any questions ask away =).
I notice that when you're trying to calculate whether a point (p) is in a circle (c) you use euclidean distance:
Math.sqrt((p.x - c.x) ^ 2 + (p.y - c.y) ^ 2) > c.radius
(p.x - c.x) ^ 2 + (p.y - c.y) ^ 2 > c.radius ^ 2
good point! I actually used this technique recently, to speed up a numerical optimization for laying out venn diagrams: http://www.benfrederickson.com/better-venn-diagrams/
I didn't think of it when I was writing this post though =(
I didn't think of it when I was writing this post though =(
You may want to consider adding a note at the top clearly specifying the problem and challenging the reader to come up with an exact solution before proceeding on. It was actually an interesting problem for someone who has not been in high school geometry for 20 years. So simple to specify, yet very much a "whaaaaaaaa" moment there for a moment while I had to reload some stuff in my brain I had not accessed in a long time. A very nice "bite size" math challenge.
But isn't the title enough: "Calculating the intersection area of 3 or more circles"? What else do we need besides some numbers for the radius(es), x,y center coordinates etc? (I haven't visited the page and will try to see if I can find the solution on my own)
I'm currently looking at different problems - and look for papers. I'm curious: Did you research the initial papers by feeding google with potential keywords for freely accessible files or did you buy a subscription/access to these things instead? I just recently found a paper on ieee.org that seems to be 4 pages, costs > 30 Dollar to access.
Is that something you did in your research?
Is that something you did in your research?
Keep in mind that you can always ask the authors.
Personally, i'm always happy to send paper / code when someone asks.
I really like your blog and have cloned some of the code in the past. Yet, I wonder why this article was posted now (it's from 2013, no?). HN is normally so adamant about recent content, but yeah, I love this article and several of the others. Thanks again!
Not related to this specific post but just wanted to chime in and say all of your stuff is really great, love the visualizations! Thanks and keep up the good work.
My mind immediately jumped to the polygon & arc solution, but I was really impressed by how you gutted this one out. As a hiring manager, you need to know that the people you hire can work through problems that are obvious to them, but more importantly, that they can work through problems that are non-obvious to them as well. Kudos for illustrating this ability.
The method used here is quite obvious for a good-at-maths primary school student.
Agreed, though only in retrospect for me. When I first saw the problem—before I looked at any of the solutions—I found myself quickly mired down thinking about how to formulate an integral to calculate the area.
The polygon-plus-border-segments method requires no calculus. http://www.mathopenref.com/segmentarea.html
The polygon-plus-border-segments method requires no calculus. http://www.mathopenref.com/segmentarea.html
Once I figured out the solution, I was kicking myself for not figuring it our earlier =)
I think I went wrong in 2 ways. My first attempt was to solve using calculus, and though I came up with a solution for the 2 circle case - I totally failed at finding the integral for 3+ circles.
My bigger mistake was to google for papers after I failed initially. I looked for other peoples venn diagram solutions, and found that they were using approximation techniques to calculate. Since the people writing these papers have a much better math pedigree than I do, it made me think I should use an approximation too.
While I did waste a bit of extra time on this, most of the time was spent in writing javascript code. Since the whole point of the venn diagram library in the first place was to learn javascript, I can’t really say it was a total waste. Also I used the quad tree estimate to verify the exact solution.
I think I went wrong in 2 ways. My first attempt was to solve using calculus, and though I came up with a solution for the 2 circle case - I totally failed at finding the integral for 3+ circles.
My bigger mistake was to google for papers after I failed initially. I looked for other peoples venn diagram solutions, and found that they were using approximation techniques to calculate. Since the people writing these papers have a much better math pedigree than I do, it made me think I should use an approximation too.
While I did waste a bit of extra time on this, most of the time was spent in writing javascript code. Since the whole point of the venn diagram library in the first place was to learn javascript, I can’t really say it was a total waste. Also I used the quad tree estimate to verify the exact solution.
In your defense, the quadtree method is more easily generalizeable to general figures :)
But indeed I believe there's a very good generalization of the intersection method (the exact one). If you have a general curve and an algebraic description, you can find the intersections roughly using something akin to the quadtree method and then use something like Newton's method to find the precise intersections. It's root finding essentially (basic numerical analysis), you can find very general and good methods on wiki. And then once you have the intersections, you only have to compute some internal polygons and then calculate some integrals. Again, this integrals can be calculated using standard methods like Runge-Kutta. Altogether this gives a very general method with much faster convergence and lower memory (quadratic convergence versus linear convergence for quadtree, provided your boundary satisfies some not too strict conditions).
But indeed I believe there's a very good generalization of the intersection method (the exact one). If you have a general curve and an algebraic description, you can find the intersections roughly using something akin to the quadtree method and then use something like Newton's method to find the precise intersections. It's root finding essentially (basic numerical analysis), you can find very general and good methods on wiki. And then once you have the intersections, you only have to compute some internal polygons and then calculate some integrals. Again, this integrals can be calculated using standard methods like Runge-Kutta. Altogether this gives a very general method with much faster convergence and lower memory (quadratic convergence versus linear convergence for quadtree, provided your boundary satisfies some not too strict conditions).
There is a simple calculus solution that is more elegant that the primary school maths solution... That is to use Green's Theorem.
https://en.wikipedia.org/wiki/Green%27s_theorem#Area_Calcula...
In fact, the algorithm for the area of the interior polygon that you are using itself (shoelace algorithm) uses green's theorem 'in stealth mode'.
https://en.wikipedia.org/wiki/Green%27s_theorem#Area_Calcula...
In fact, the algorithm for the area of the interior polygon that you are using itself (shoelace algorithm) uses green's theorem 'in stealth mode'.
[deleted]
Where are you? Which "good" (as opposed to exceptional) primary school students know trig?
In the UK chords aren't mentioned in the maths curriculum until KS4 (late secondary school, 14-16yo) - https://www.gov.uk/government/publications/national-curricul....
In the UK chords aren't mentioned in the maths curriculum until KS4 (late secondary school, 14-16yo) - https://www.gov.uk/government/publications/national-curricul....
I actually appreciate this post, for showing that people other than myself also over-think solutions. When most of my software development work deals with managing code complexity, vs actual algorithmic work, I often feel silly when I spend too long working on a problem with a simple solution. Luckily, analysis and learning is part of the job description!
Great post! Am I the only one whom, when seeing such "simple" problems, thinks "Thank goodness I didn't have to answer this in an interview, on a white board."
there is a lesson here. think about the problem before researching it.
i've seen a lot of terrible algorithms come from people reading papers which provide solutions that are worse than they could come up with themselves. they may even assume that the bad algorithm must have some purpose to its badness... like its being done for a complicated reason they didn't think of.
The truth is that a paper might not even be written for practical implementation, but to tick some academic boxes.
reinventing wheels is bad, but copying bad wheels is considerably worse.
i've seen a lot of terrible algorithms come from people reading papers which provide solutions that are worse than they could come up with themselves. they may even assume that the bad algorithm must have some purpose to its badness... like its being done for a complicated reason they didn't think of.
The truth is that a paper might not even be written for practical implementation, but to tick some academic boxes.
reinventing wheels is bad, but copying bad wheels is considerably worse.
Pick any point in the intersection A (can be on border too). Divide the interval from 0 to 2pi into many small chunks of length delta-theta.
1/2 * Sum for n from 0 to 2pi in delta-theta chunks of min(distance from A to each circle in n angle direction)*delta-theta should be the area of intersection.