Ellipses generate accurate area-proportional Euler diagrams for more data than is possible with circles. However, computing the region areas is di cult as ellipses have various degrees of freedom. Numerical methods could be used, but approximation errors are introduced. Current analytic methods are limited to computing the area of only two overlapping ellipses, but area-proportional Euler diagrams in diverse application areas often have three curves. This paper provides an overview of di erent methods that could be used to compute the region areas of Euler diagrams drawn with ellipses. We also detail two novel analytic algorithms to instantaneously compute the exact region areas of three general overlapping ellipses. One of the algorithms decomposes the region of interest into ellipse segments, while the other uses integral calculus. Both methods perform equally well with respect to accuracy and time.
Area-proportional Euler diagrams are used in various areas, such as genetics [24] and information search [8], to represent both the set relations (by the intersecting closed curves) and their cardinalities (by the area of the regions) [5]. Often these diagrams are drawn for data with two or three sets and are Venn diagrams, like those in Fig. 1, such that all the possible curve intersections are depicted [28].
Euler diagrams drawn with circles facilitate user comprehension due to their smoothness, symmetry and good continuation that make the curves easily distinguishable even at intersections [3]. Most area-proportional Euler diagrams are thus drawn with circles [28]. However, circles have limited degrees of freedom (i.e., a centre and a radius) and draw accurate diagrams for any data with two sets [5] but not three [6]. Polygons are more exible and draw accurate diagrams for any 3-set data [6], but their non-smooth curves impede comprehension [2].
Ellipses have more degrees of freedom (i.e., a centre, a semi-minor axis, a semi-major axis, and an angle of rotation) than circles, but like circles are symmetric and smooth. Their helpful features have been long noted [5], but due to di culties in computing the region areas of the diagram, a drawing method that uses ellipses (known as eulerAPE) was only recently devised [19].
Approximate methods could be used to compute the region areas of Euler diagrams. However, these methods introduce error [15] that could distort the diagram and thus violate Tufte's graphical integrity principle that \representation of numbers, as physically measured on the surface of the graphic itself, should be directly proportional to the numerical quantities represented" [27]. Though humans are biased to area judgement [7], such accuracy and integrity is still important. Firstly, it is still unclear how areas in such diagrams are perceived and what inaccuracies are not noticeable. Secondly, it is highly unlikely for an area to be perceived in a same way by di erent individuals [18]. Tufte emphasized that \graphical excellence begins with telling the truth about the data" [27] and for this reason, he highly criticized metrics that scale objects (e.g., on maps [21]) based on how they could be perceived.
Analytic methods can compute the exact region areas of Euler diagrams, but none of the current methods are appropriate for three general ellipses. Drawing methods for area-proportional Euler diagrams use optimization search techniques [6] and so, analytic methods that compute the region areas should be computationally e cient to allow for the generation of accurate diagrams in a time that maintains user's attention.
In this paper, we discuss current methods to compute the region areas of Euler diagrams with ellipses (Section 3) and we describe our two novel analytic methods to instantaneously (in 10 milliseconds) compute the region areas of Euler diagrams with three general ellipses (Section 4). Using one of our analytic methods, eulerAPE (http://www.eulerdiagrams.org/eulerAPE) [19] draws accurate area-proportional Venn diagrams with ellipses for a large majority of random 3-set data (86%, N =10,000) in a relatively fast time (97% of the diagrams within 1 second). The two analytic methods for computing the region areas of three intersecting ellipses have not been previously detailed. Hence, this forms the research contribution of this paper.
We start by introducing basic concepts and de nitions in relation to ellipses.
An ellipse is a simple closed curve characterized by (Fig. 2A): a centre, (
d'
2cos2' +
(
C
The value returned by (
An ellipse segment (−⌢) is the space bounded by an ellipse arc and a chord
that share the same endpoints (e.g., −⌢MN in Fig. 3C). An ellipse sector (ÂMNO )
is composed of an ellipse segment (−⌢MN ) with the same ellipse arc as the sector
and a triangle (△MNO ). Thus, the area of an ellipse segment can be de ned as
Area of ⌢MN = Area of ÂMNO − Area of △ MNO :
−
(
The polar coordinates representation of an ellipse curve in (
The curve of a general ellipse can be de ned parametrically as
x(t) = 1 +
y(t) = 2 +
cos cos t −
sin cos t +
sin sin t
cos sin t
where t is the parameter and 0 ≤ t ≤ 2 and (x(t); y(t))
are the Cartesian coordinates of a point on the ellipse curve :
(
In (
P (x,y)
Alternatively, the curve of a general ellipse can be de ned by the set of points
(x, y ) on the Cartesian plane that satisfy the implicit polynomial equation
((x − 1) cos
+ (y − 2) sin )
2
2
+
((y − 2) cos
− (x − 1) sin )
2
2
= 1 :
(
We now discuss available methods, after which we introduce our novel analytic methods.
3.1
A numerical quadrature method can be used to compute the region areas of any number of intersecting curves irrespective of their shape. The drawing method venneuler [28] uses this method to draw area-proportional Euler diagrams with circles. In venneuler, each circle is drawn on a 200 × 200 pixel plane and each pixel on each plane is set to 1 if it is in the circle or 0 if not. The area of each region in the diagram is the sum of the value of all the pixels on all the planes that are located in that region.
Such numerical approximation introduce errors in the calculation of the region areas, as shown in Fig. 5 for an Euler diagram drawn with ellipses. In Fig. 5A and Fig. 5B, the same diagram is drawn on two identical 200 × 200 grids with a di erence in the placement of the diagrams on the grids. The magni ed views of regions ab, ac, bc and abc indicate that according to Fig. 5A there are 0 grid squares or pixels that are only in region bc, while according to Fig. 5B there are 3. Similar di erences can be noted for the other regions due to a di erence in the positioning of the diagrams on the grids. Using a larger grid and thinner outlines for the curves could reduce inaccuracies, but such issues will still be inevitable. Also, small regions (e.g., region bc in Fig. 5) could be considered missing even though they are depicted. This could impede the drawing method from handling diagrams with small regions and impede its optimization process from taking a path that could lead to an improved solution. If, like venneuler, the drawing method uses a steepest descent optimization approach, the analytic gradient cannot be computed and the generated diagram is less likely to be accurate.
Checking whether a point is in a closed curve could be computationally
complex and expensive. With circles, venneuler takes the Cartesian coordinates of
the pixel's location on the plane and applies them to the implicit polynomial
equation of the circle to verify whether the distance between the circle's centre
and the pixel is less than the circle's radius. If the latter is true, the pixel is in
the circle. However, checking if such a pixel is in a general ellipse and conducting
this check for all the pixels on all the planes is computationally expensive, as
ellipses have more degrees of freedom than circles and the implicit polynomial
equation of the curve of a general ellipse (
Alternatively, the ellipses could be represented using regular convex polygons and a standard polygon intersection algorithm could be used to compute the region areas. For instance, the drawing method VennMaster computes the region areas of its Euler diagrams with polygons by applying the Gaussian integration theorem [17]. However, the region areas are not computed accurately and small regions are often considered missing. The polygons should have numerous vertices and small edges otherwise the curves would be highly non-smooth, leading to unreliable approximations of the region areas. Polygon intersection algorithms for polygons with numerous vertices are also more computationally expensive than the numerical quadrature method [25].
Monte Carlo methods could also be used to approximate the region areas, but due to repeated random sampling, they could be computationally expensive. 3.2
Analytic methods to compute the region areas of two [4] or three [5] intersecting circles are available. For more circles, approximation methods are often used. For ellipses, only two analytic methods are available: one by Eberly [9] and another by Hughes and Chraibi [14].
Both methods are restricted to two ellipses. Eberly's method is further restricted to ellipses in canonical form. Hughes and Chraibi's method can handle any two general ellipses with any centre and angle of rotation. Both methods compute the area of the overlapping region by rst obtaining the area of the two ellipse segments making up the region (as shown later in Fig. 6B). The area of each ellipse segment is obtained by computing the area of an ellipse sector and then subtracting the area of a triangle, as discussed in Section 2. The derivation of the area of a sector of an ellipse in canonical form is obtained using integral calculus. The representation of the ellipse curve is de ned in polar coordinates by Eberly and parametrically by Hughes and Chraibi. To handle general ellipses, Hughes and Chraibi rst translate and rotate the general ellipses so they are transformed into canonical form, and then compute the area of the required ellipse segment using the same equation as that of ellipses in canonical form.
Though an analytic method might seem computationally expensive due to the various degrees of freedom of ellipses, Hughes and Chraibi's method has been e cient enough to compute the area of two overlapping ellipses for simulations of dynamic systems, such as an orbiting satellite with a solar calibrator [16].
We devised two general analytic methods for three ellipses, both of which can handle ellipses that are not necessarily in canonical form. These include: M1. Decomposition into ellipse segments;
M2. Using integral calculus.
These methods di er in the way they compute the area of the overlapping region between two ellipses and that of an ellipse segment. Similar to Eberly's [9] and Hughes and Chraibi's [14] methods, M1 decomposes the region of interest into ellipse segments and uses an equation of the segment area of an ellipse in canonical form. M2 uses integral calculus to directly derive the equation of the required enclosed region area without the need of any geometric transformations. M1 and M2 are discussed later.
The general algorithm for computing the region areas of three intersecting ellipses in a Venn diagram using either M1 or M2 is as follows: Algorithm 1: ComputeRegionAreasOfThreeIntersectingEllipses (d) Input: A Venn diagram d with three ellipses.
Output: regionAreas, a set of areas one for every region in d.
1. for each ellipse e in d do
2. ellipseAreas [e] ← area of e by (
Algorithm 1 has been implemented for both M1 and M2 and for any possible representation of a Venn diagram with three ellipses that are not necessarily in canonical form and that intersect pairwise exactly twice. M1 and M2 as well as the chosen method to compute the intersection points of the ellipses are discussed in the next sections.
If the general intersecting ellipses do not always intersect each other exactly
twice, an extended version of Algorithm 1 would have to be implemented, so that
the various ways in which the ellipses can intersect would be handled (there can
be from zero up to four intersection points between two ellipses [9]). The method
we have chosen to compute the intersection points [13] returns all the intersection
points (i.e., zero up to four) between any two general ellipses. So the algorithm
can easily be extended by: (i) identifying the way each pair of ellipses intersect
from the number of intersection points between the two ellipses; (ii) decomposing
the relevant regions into ellipse segments and basic geometry shapes like triangles
or rectangles whenever necessary; (iii) using either M1 or M2 to nd the area of
the overlapping region between two ellipses and the area of ellipse segments; (iv)
using (
Equations de ning the area of a segment of an ellipse in canonical form can easily be derived and could be less complex than the ones for a general ellipse. Such equations are already available. For example, Eberly [9] and Hughes and Chraibi [14] provide two di erent equations based on the area of a sector of an ellipse in canonical form. Eberly's equation uses the polar coordinates representation of the ellipse curve, while that of Hughes and Chraibi uses the parametric representation of the ellipse curve.
M1 uses (
M2 derives an equation of the area of the required enclosed region from de nite integrals that compute the area under an ellipse curve (or line) between two given points. The equation of the curve of a general ellipse is used and so, M2 does not require any of the geometric transformations used in M1 to get the ellipse in canonical form.
Let e1 and e2 be two ellipses that intersect at points i1 and i2, such that the
overlapping region is enclosed by an ellipse arc from i1 and i2 in an anticlockwise
direction along e1 and an ellipse arc from i1 and i2 in an anticlockwise direction
along e2. In M2, the area of the overlapping region between e1 and e2 is
Area under curve e1 from i1 to i2 + Area under curve e2 from i2 to i1 :
(
To compute the area of the region located in all three ellipses, M2 decomposes the region into ellipse segments and a triangle, as in M1 and as shown in Fig. 6D, where the arc endpoints of the ellipse segments and the vertices of the triangle are de ned by the intersection points of the three overlapping ellipses. Given a segment of an ellipse e with an arc from i1 and i2 in an anticlockwise direction along e and a secant line l intersecting e at i1 and i2, M2 de nes the area of the ellipse segment as
Area under curve e from i1 to i2 + Area under line l from i2 to i1 :
(
The area under a curve between two given points is de ned by a de nite
integral. The curve of a general ellipse can be de ned in di erent ways (Section 2).
However, it is not always so straightforward to handle some representations. For
instance, the implicit polynomial in (
If y = F (x) is the explicit de nition of e as a function of x and x(t1)= x1 and x(t2)= x2, the area under the curve e from (x1, y1) to (x2, y2) is sin cos t + cos sin t) (− cos sin t − sin cos t) dt = x2 t2 t2 ∫ F (x)dx = ∫ F (x(t))x′(t)dt = ∫ y(t)x′(t)dt = x1 t1 t1 t2 t∫1 ( 2 + K1 sin 2t + K2 sin t + K3 cos 2t + K4 cos t + K5t]tt12
cos 2 where K1 = 4 ; K2 = − 2 sin ;
K3 =
K4 = 2 cos ; K5 = − 2 : Else (i.e., Sx1 − x2S ≤ Sy1 − y2S)
If x = F (y) is the explicit de nition of e as a function of y and y(t1)= y1 and y(t2)= y2, the area under the curve e from (x1, 1) to (x2, y2) is 2 + 2 sin 2 8 ;
(
cos 2 where K1 = 4 ; K2 = 1 cos ;
K3 = K4 = 1 sin ; K5 = 2 : cos cos t − sin sin t) (− sin sin t +
cos cos t) dt =
The value of t1 and t2 corresponding to (x1, y1) and (x2, y2) respectively is
computed as discussed in Section 2 in relation to (
Similarly, the area under a line l from (x1, y1) to (x2, y2) on l where m and c are respectively the gradient and y-intercept of l is de ned as: Else (i.e., Sx1 − x2S ≤ Sy1 − y2S)
If x = ym− c explicitly de nes l as a function of y, the area under l from (x1, y1) to (x2, y2) is
y2
However, to compute the region area of the overlapping ellipses, the intersection points of the ellipses are required.
All the intersection points of the ellipses in a diagram can be obtained by computing the intersection points of every ellipse pair.
An ellipse is a curve and so, the various methods of computing the intersection points of two curves [11, 25] can be adapted for the intersection points of two ellipses. Numerical methods, such as Bezier and internal subdivision [29], Bezier clipping [26] and the Newton-Raphson method, could also be used. However, as explained earlier, numerical approximation methods introduce error and can distort the diagram.
The most common analytic methods include: (i) the resultant-based method using for instance Bezout's resultant [9, 10]; (ii) the Grobner basis method [11]; (iii) the matrix-based method [13]. These methods have been used for various areas (e.g., the resultant-based method [14]; the Grobner basis method [23]; the matrix-based method [1]).
Methods (i) and (ii) are more complex than (iii) as the roots of a quartic polynomial have to be solved using Ferrari's solution or other methods [12]. For example, Hughes and Chraibi's [14] analytic method for the region areas of two intersecting ellipses uses a numerical implementation of Ferrari's solution [22] to nd the roots of the quartic polynomial. However, we only require the real roots and so, nding all the roots of a quartic polynomial is a waste of computational resources [12].
Using the matrix representation of conic sections and homogeneous transformation matrices, method (iii) can compute the intersection points of the two ellipses without referring to any quartic polynomials. This method has now been extended to e ciently identify whether two solid ellipsoid intersect [1]. Thus, for our analytic methods, we use Hill's method [13] to compute the ellipses' intersection points. 5
M1, M2 and an approximate method were used to compute the region areas of 8000 Venn diagrams with three ellipses whose properties were randomly generated and which intersect exactly twice pairwise. Some of these randomly generated diagrams had very small region areas that are barely visible like regions c and bc in Fig. 1B. The computed areas were then compared. The approximate method represented the ellipses as regular convex polygons and used a standard polygon intersection algorithm to nd the area of the regions and to compute the intersection points.
The same areas were obtained by our analytic methods, M1 and M2 (with an occasional insigni cant di erence of less than 10−4). The average percentage error of the areas provided by the approximate method with respect to any one of our analytic methods was 1.04%. M1 and M2 returned the same area for small regions like those in Fig. 1B, but the approximate method disregarded these regions as if they were missing and the represented set relations were nonexistent.
M1 and M2 computed the areas in around 10 milliseconds on an Intel Core i7 CPU @2GHz with 8GB RAM, OS X 10.8.4 and Java Platform 1.6.0 51. This response time is 10 times less than the 0.1 second limit for an instantaneous response [20], and similar to that of numerical methods (e.g., venneuler's [28] response time is 1 millisecond using a numerical quadrature method on a MacBook Pro @2.5Ghz with 2GB RAM and Java Platform 1.5). Thus, our analytic methods can also be used for any other application, including simulations of dynamic systems, where both accuracy and e ciency is important. 6
We have discussed methods to compute the region areas of Euler diagrams drawn with ellipses. We rst reviewed current available methods, namely approximate and analytic methods, and we then described our two novel analytic methods to compute the region areas of three general intersecting ellipses.
Methods that automatically draw area-proportional Euler diagrams with three curves require a mechanism to compute the region areas of diagrams in relatively fast time. A recent drawing method eulerAPE [19] demonstrated the bene ts of ellipses in drawing such diagrams accurately and with smooth curves. However, the region areas must rst be computed accurately and an analytic method is thus required. Current analytic methods are restricted to two ellipses and so our methods are the rst to calculate region areas for three ellipses. One method decomposes the regions into ellipse segments and the other uses integral calculus, but both return accurate region areas instantaneously (in 10 milliseconds), even when the diagram has very small regions as in Fig. 1B.
We implemented Algorithm 1 that measures the region areas of Venn diagrams with three curves and ellipses that intersect exactly twice pairwise. We describe how to handle other Euler diagrams with three curves, but this extended version is not yet implemented.
The regions of an Euler diagram with any number of ellipses can be decomposed into ellipse segments and possibly a polygon (e.g., a triangle or a quadrilateral). The area of the overlapping region between two ellipses and that of an ellipse segment can be computed with our methods, while the area of an ellipse and that of a polygon can be computed using standard geometry formula. Thus, our methods can easily be extended to instantaneously compute the region areas of Euler diagrams with any number of ellipses. Methods that draw area-proportional Euler diagrams with more than three ellipses can then be devised.