4 ms·

What is the iterative method for determining the area of intersection ?

logfromblammo 8y ago
I don't remember the whole thing, and I couldn't take it with me, but what I can recall is this: It is much more important to determine whether there is a real intersection at all, than it is to determine how big the area of intersection is. Calculate distance between centers. Add both major radiuses. If distance >= sum, skip this pair. Intersection area is entirely imaginary. If distance < max( minor radiuses ), the pair definitely has a real intersection. Put it on the list for later and check the next pair. Upper bound, min( ellipse areas ); lower bound zero. Find the maximum extents of each ellipse, when projected onto the segment between centers. If the sum is greater than the distance, there is a real intersection. Put it on the list and go on to the next pair. Then there was a bit of a race against time through increasingly esoteric tests that relied heavily on the calculations from previous steps. The goal was to produce a list of ellipses, sorted by decreasing real area of intersection greater than zero with a single reference ellipse. So if there was only one on the list, you didn't even need to calculate area. That was the answer, and you're done. At some point, the reference ellipse was transformed into a circle at the origin, with the center of the comparison ellipse on the x axis. Some tests only used one quadrant of an ellipse at a time. Each test refined the bounds on the fraction of the reference ellipse that could be in the intersection, so again, if those limits were enough to sort the list, the area calculation was skipped. If there were still enough ambiguous tests, then finally you calculate the points of intersection. For zero or one, the area is exactly the area of the smaller ellipse. For four, first approximation is the area of the quadrilateral, as minimum. For three, the area of the triangle, as minimum. Two was the worst case, because then you needed to pick out a third point for the triangle, which was probably one of the four where a major axis intersected an ellipse. If you needed a maximum area, it was the smallest circle enclosing the points. Each test either increased the lower bound, or decreased the upper bound, until there was no more overlap in the sorted list. After all that, if the list was still not clearly ordered, you finally calculated and added chord areas to get exact results. You couldn't really get here with real-world test data, so now you had to invent test data specifically to make it this far, to be sure that if any real-world data set ever does execute this branch, it ends up ordered correctly. But I don't think we ever got funding to bulletproof it. Customer was fine with the possibility that a tiny fraction of inputs might end up ordered incorrectly, so long as the wrong answer came out quickly. Clearly, if all the areas had to be calculated exactly, it would have been more efficient to just do that from the start. But that wasn't the problem.

I don't remember the whole thing, and I couldn't take it with me, but what I can recall is this: It is much more important to determine whether there is a real intersection at all, than it is to determine how big the area of intersection is. Calculate distance between centers. Add both major radiuses. If distance >= sum, skip this pair. Intersection area is entirely imaginary. If distance < max( minor radiuses ), the pair definitely has a real intersection. Put it on the list for later and check the next pair. Upper bound, min( ellipse areas ); lower bound zero. Find the maximum extents of each ellipse, when projected onto the segment between centers. If the sum is greater than the distance, there is a real intersection. Put it on the list and go on to the next pair. Then there was a bit of a race against time through increasingly esoteric tests that relied heavily on the calculations from previous steps. The goal was to produce a list of ellipses, sorted by decreasing real area of intersection greater than zero with a single reference ellipse. So if there was only one on the list, you didn't even need to calculate area. That was the answer, and you're done. At some point, the reference ellipse was transformed into a circle at the origin, with the center of the comparison ellipse on the x axis. Some tests only used one quadrant of an ellipse at a time. Each test refined the bounds on the fraction of the reference ellipse that could be in the intersection, so again, if those limits were enough to sort the list, the area calculation was skipped. If there were still enough ambiguous tests, then finally you calculate the points of intersection. For zero or one, the area is exactly the area of the smaller ellipse. For four, first approximation is the area of the quadrilateral, as minimum. For three, the area of the triangle, as minimum. Two was the worst case, because then you needed to pick out a third point for the triangle, which was probably one of the four where a major axis intersected an ellipse. If you needed a maximum area, it was the smallest circle enclosing the points. Each test either increased the lower bound, or decreased the upper bound, until there was no more overlap in the sorted list. After all that, if the list was still not clearly ordered, you finally calculated and added chord areas to get exact results. You couldn't really get here with real-world test data, so now you had to invent test data specifically to make it this far, to be sure that if any real-world data set ever does execute this branch, it ends up ordered correctly. But I don't think we ever got funding to bulletproof it. Customer was fine with the possibility that a tiny fraction of inputs might end up ordered incorrectly, so long as the wrong answer came out quickly. Clearly, if all the areas had to be calculated exactly, it would have been more efficient to just do that from the start. But that wasn't the problem.