5 ms·

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 ca

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.

deleted 11y ago
[deleted]
darkmighty 11y ago
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).
dnautics 11y ago
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_Calculation 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 11y ago

[deleted]

darkmighty 11y ago

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

dnautics 11y ago

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_Calculation 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'.